취업 준비 및 일상

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://www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 풀이 특별할 거 없는 구현입니다. 다만, 행, 열 표기법이 익숙하지 않은 방식으로 제시되니 잘 변환하도록 합니다. 배운 점 이동을 한 후 벽 or 로봇에 부딪히는지 움직임 처리를 반복문을 쓰지 않고 한번에 이동을 시킨 후 체크를 하니 틀렸다. 유사한 문제가 있었는데, 그 때 그런 식으로 풀었던 경험이 독이 되었다. 역시 구현은 한번 집중 흐트러지면 디버깅이 지옥이 된다.. ..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 일반적인 구간 DP 문제입니다. dp[i][j]를 'i번째 파일부터 j번째 파일까지 합치는 최소 비용'이라고 하면, dp[i][i+k] = min(dp[i][i+j]+ dp[i+j+1][i+k] + 'i번째 파일부터 j번째 파일의 용량')(for j in range(1, k))이 됩니다. 여기서 'i번째 파일부터 j번째 파일의 용량'은 누적합을 구하여 처리하면 됩니다. 배운 점 당연..

https://www.acmicpc.net/problem/17106 17106번: 빙고 한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과 www.acmicpc.net 풀이 1) 직접 경우를 따져가며 문제를 푸는 방법, 2) 가지수가 2^25 밖에(?) 안 되니 브루트포스 코드를 작성하여 푼 후 제출하는 방법이 있습니다. 저는 2번으로 문제를 풀었습니다. 2번 풀이가 어떻게 보면 '머리가 나빠서 몸이 고생하는' 풀이처럼 보이지만, 관점을 바꾸어 1번 풀이가 '몸이 나빠서 머리가 고생하는' 풀이라고 생각합시다. 참고로, 1번 풀이는 에디토리얼이 ..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 장애물이 있는 범위를 누적합을 통해 구하면 됩니다: 가령, H=7이고 석순의 길이가 3이라면, 1, 2, 3이 영향을 받으므로, '석순 배열'의 3번째 index에 1을 넣고, H에서부터 1까지 누적합을 구하면 높이가 3인 석순이 1, 2, 3에 영향을 끼친다는 것을 구현할 수 있습니다. 반대로, 종유석의 길이가 3이라면 이는 7, 6, 5에 영향을 미치기에, '종유석 배열'의 5(=H+1-종유..

https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 솔직히 누적합 유형 문제는 껌이라고 생각했는데, O(N^2) 브루트포스 풀이말고 생각이 전혀 안 나더라... 내가 껌이였고 풀이 1. 누적합(sum[i]: 0번째 index부터 i번째 index까지의 합)을 구한다. 2. value는 Integer, key는 long으로 하는 map을 선언한 후, (0, 1)을 넣어준다. 이는 0..