취업 준비 및 일상

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 개념 최단 경로 알고리즘 중 다익스트라는 음의 가중치를 갖는 간선, 플로이드는 음의 사이클을 가지면 제대로 된 답을 내지 않을 수 습니다. 구체적으로, 다익스트라는 '음의 가중치를 갖는 간선이 있을 경우 현재 갈 수 있는 정점 중에서 가장 가까운 정점까지의 거리를 확정지을 수 없기'에, 1) 음의 사이클이 있을 경우 무한 루프가 발생하며..

https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 1. 물고기를 저장하는 방법이 제일 중요해 보입니다. 1) 물고기를 배열에 저장할 경우 - 물고기의 수를 F라 한다면, 대략 O(FS)입니다. 문제 조건에서 '격자 위의 물고기 수는 항상 백만 이하인 조건만 들어온다'를 믿고 F

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이 처음에는 별 생각없이 DP 식으로 접근했다가, 메모리 초과가 나왔습니다. 그래서 다른 방식으로 풀었습니다. 저울추를 오름차순으로 정렬합니다. 저울추가 0개일 때에는 잴 수 없는 최소 무게가 1이므로, 1에서 시작합니다. 저울추에 대해 for문을 돌면서, 만약 현재 저울추의 무게가 현재 잴 수 없는 최소 무게보다 클 경우 현재 잴 수 없는 최소 무게는 앞으로도 잴 수 없습니다. 반대로, 현재 저울추의 무..

https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 길이 구부정하게 있으므로 큐로 구현하면 각 method 구현이 간단합니다(머리를 싸매지 않아도 됩니다.). 다만, 속도도 빠를 줄 알았는데 그렇진 않네요. 다른 코드를 보니, 1차원 배열로 구현한게 더 빠릅니다. 제 풀이가 꽤 유니크한 편일 겁니다..ㅎㅎ 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 1. 블록 기록 빈 칸은 -2로 표현하였습니다. 2. 블록 그룹 Blocks 라는 class를 만들어 (블록의 수, 무지개 블록의 수, 행, 열)을 저장하였으며, 블록의 수 -> 무지개 블록의 수 -> 행 -> 열 크기로 비교할 수 있게 Comparable을 implement했습니다. 3. 시뮬레이션 3-1. 가장 큰 블록 그룹 찾기 - 블록 그룹의 위치값은 '일반 블록의 가장 위/왼쪽 ..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 preorder는 VLR 순으로 트리의 노드를 출력하므로, 우리는 V를 찾고, L을 찾아 L에서 V를 찾고.... R에서 V를 찾으면 됩니다. inorder가 LVR, postorder는 LRV 순으로 트리의 노드를 출력하므로, 일단 postorder 배열의 끝 값은 노드가 됩니다. 모든 노드의 값은 중복이 없으므로, inorder 배열에서 V를 찾아준 후, 해당 위치를 기준으로 L, R을 나누어 재귀적으로 V를 찾으..

https://www.acmicpc.net/problem/15898 15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~ "피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타 www.acmicpc.net 풀이 속칭 '빡구현'이라는 말이 가장 잘 어울리는 문제입니다. 구현 문제에서 흔히 쓰이는 BFS 정도도 쓰이지 않으며, 모든 경우를 무수한 for문으로 탐색하면 됩니다. 1. 재료 관리 각 칸이든 재료든 '품질'과 '색깔'이라는 두 변수를 갖고 있으니, 같은 class(Status로 정의함)로 관리하면 됩니다. 가마의 상태는 Status[5][5], n개의 재료는 ..

https://www.acmicpc.net/problem/17451 17451번: 평행 우주 행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다. www.acmicpc.net 풀이 1. 이분 탐색 지구에서 올리는 속도 v를 이분 탐색을 통해 최솟값을 찾는 풀이입니다. 최소 속도의 최댓값이 얼마나 될지 살짝 감이 안 잡히나, 9억이 넘는 서로 다른 세 소수 a, b, c (a (int의 max 범위) 이므로 int 범위를 벗어납니다. 따라서, 일단 long으로 찾아야 한다는 사실을 발견할 수 있습..

https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 풀이 각 위치에서 주어진 방향대로 이동해서 탈출할 수 있는지 구현해야 합니다. 다만, M=N=500(총 25만개의 칸)이고, 모든 칸의 경로가 하나로 연결되어 탈출하는 시나리오를 생각해봅시다. 이 경우, 각 칸에서 탈출할 수 있을 지 여부를 계산하는 횟수는 1, 2, 3, ... , 25만번인, O(M^2N^2) 시간 복잡도를 가져 시간초과가 발생하게 됩니다. 생각을 해보면, 연결..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 풀이 주어진 책의 위치를 양수와 음수로 나눕니다(0은 입력으로 주어지지 않으니 고려하지 않아도 됩니다.). 양수의 개수를 a개, 음수의 개수를 b개라고 하면, 세준이는 모든 책을 갖다놓기 위해서 양수 쪽의 위치로는 math.ceil(a/m)번, 음수 쪽의 위치로는 math.ceil(b/m)번 이동해야 합니다. 한 번의 이동에 최대 M개의 책을 가져다 놓을 수 있는데, 끝 위치에서부터 M개를 채운다고 생..