취업 준비 및 일상

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 풀이 다들 2차원 배열로 잘 풀던데, 저는 머리가 그렇게는 안 돌아가서 3차원 배열을 만들었습니다. 1~N번째 수열의 값을 각각 arr[i]에 담아둡니다. 3차원 int 배열 dp[i][j][k]: 1~i번째 수를 j개의 구간을 이용하여 합하였을 때 최대값(k==0: i번째 수 미포함, k==1: i번째 수 포함) 그러면, dp[i][j][0] = max(dp[i-1][j..

https://hyundaimobis.goorm.io/assessment/31303/22-%ED%98%84%EB%8C%80%EB%AA%A8%EB%B9%84%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B2%BD%EC%A7%84%EB%8C%80%ED%9A%8C `22 현대모비스 알고리즘 경진대회 - 구름DEVTH 구름EDU는 모두를 위한 맞춤형 IT교육 플랫폼입니다. 개인/학교/기업 및 기관 별 최적화된 IT교육 솔루션을 경험해보세요. 기초부터 실무 프로그래밍 교육, 전국 초중고/대학교 온라인 강의, 기업/ hyundaimobis.goorm.io 매일 그냥 백준 문제를 풀면 좀 무료하기도 하니, 환기삼아 경진대회를 봤습니다. 진행 방식 구름이라는 사이트에서 진행..

https://www.acmicpc.net/contest/view/833 2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 Open Contest www.acmicpc.net 문제가 그리 어렵지 않아서 나도 다 풀 수 있었다. 풀이 A. 영수증 다 더한 값이 주어진 X랑 같은지 확인하면 된다. B. 커트라인 정렬한 후 K번째로 큰 원소의 값을 출력하면 된다. 동점자 처리는 안 해줘도 되는 듯하다. C. 연속 XOR 브루트포스로 하면 B

https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 풀이 '상어별 이동 방향 결정' -> '이동' -> 냄새 뿌리기 및 상어 겹치는 거 처리 -> 냄새 감소 를 1번 상어만 남을 때까지 반복하면 됩니다. 1) 상어별 이동 방향 결정 - 각 상어 별로 방향 우선순위별로 순회하면서, 냄새가 0인 경우 > 냄새가 자기 자신인 경우 > 나머지인 경우를 찾습니다. 저는 i번째 상어가 현재 j 방향으로 움직일 때 ..

https://www.acmicpc.net/problem/3080 3080번: 아름다운 이름 상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 한다. www.acmicpc.net 풀이 "A, AB, AC, B, C"를 배열하는 경우의 수를 생각해봅시다. 이렇게 5개의 이름이 있는 경우, 앞이 "A"로 시작하는 3개의 단어끼리 배열하고, 이후 앞이 "A"로 시작하는 3개의 이름을 하나의 이름을 보아 "A 모음", "B", "C" 3개의 이름을 배열할 수 있습니다. 총 36가지의 경우가 있습니다. 이를 계산하기 위해 트라이 구조를 이용해보도록 합시다. 트라이에서 첫 번째 단계에 "..

https://www.acmicpc.net/problem/7616 7616번: 교실로 가는 길 각 테스트 케이스마다 "Case #:" 형식으로 케이스 번호를 출력한다. 그 다음, K개의 겹치지 않는 경로 (1번에서 출발해 2번으로 도착하는 경로)가 존재하면 K개 줄에 각 경로를 출력한다. 없는 경우 www.acmicpc.net 풀이 백준 2316번처럼 간선 뿐만 아니라 정점도 최대 한 번만 방문할 수 있으므로, '정점 분할'을 해 줍니다. 에드몬드-카프로 유량이 K 이상인지(==경로가 K개 이상인지) 확인하여, K개 이상일 경우 경로를 출력해줍니다. 유의할 점으로는, 에드몬드-카프에서 찾은 K개 증가 경로를 역추적하여 출력할 경우 제대로 된 결과가 나오지 않을 수 있습니다. 2 6 3 5 4 6 1 4 ..

https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 풀이 라이님 블로그를 참고했습니다. 점을 한 번만 표현하기 위해, '정점 분할'을 해줍니다: 점 U를 점 U, U'으로 나누어, 점 U와 U' 사이 유량이 1인 단방향 간선으로 연결합니다. 점 U에서 점 V로 가는 양방향 간선을 다음과 같이 표현합니다: U'->V 단방향 간선, V'->U 단방향 간선 이후 에드몬드-카프 알고리즘을 수행하면 됩니다. 코드 1 2 3 4 5 6 7 8 9 ..

개요 당연하게도, 코테를 준비하는데 있어서 네트워크 플로우는 '투머치'합니다. 코테를 준비하는데 있어서 바킹독 선생님이 다루는 범위도 과분하다고 할 정도로 충분하고(해당 문제집에는 위상 정렬, MST, 수학 등 출제 빈도가 낮은 알고리즘도 있습니다), 카카오와 같은 코테가 '빡센' 곳을 생각해도 트라이, 세그먼트 트리, KMP 정도만 추가하여 준비하는 것이 최선입니다. 그러나, 1) 최근에 본 현대모비스 알고리즘 경진대회, 그리고 네이버 코테(확실하지 않음: 시간이 없어서 문제 자체를 못 봤음...ㅠ)에 나왔으며, 2) 궁금하며 3) 솔브닥 티어좀 올리고 싶어서 흐름 네트워크에서의 최대 유량을 구하는 알고리즘을 공부, 정리하였습니다. 기본 개념 Everenew님 글: 대부분의 블로그 포스트가 종만북을 기..

https://www.acmicpc.net/problem/3663 3663번: 고득점 현수는 조이스틱을 이용해 지렁이를 미로에서 탈출시키는 게임을 하고 있다. 최고 점수를 얻은 경우에는 조이스틱을 이용해서 이름을 입력해야 한다. 이름을 입력하는 과정은 다음과 같다. 가 www.acmicpc.net or https://programmers.co.kr/learn/courses/30/lessons/42860# 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 풀이 0) 글자 바꾸는건 별로 안 어렵..

https://programmers.co.kr/learn/courses/30/lessons/42627# 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 (요청 시간, 소요 시간)을 갖는 class Job을 만듭니다. 우선순위 큐 2개(pq1, pq2)를 선언하는데, pq1은 요청 시간이 작은 순, pq2는 소요 시간이 작은 순으로 배열하도록 합니다. pq1은 현재 시간 t보다 요청 시간이 큰(==현재 할 수 없는) 일, pq2는 현재 시간보다 요청 시간이 작거나 같은(==현재 할 수 있는) 일을 담..