취업 준비 및 일상

https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 풀이 한 번의 과정은 5단계로 나뉩니다. 1) 온풍기에서 바람이 나감 - 가장 어려운 부분이었습니다. - 각 칸마다 바람이 퍼질 수 있는지 bfs/dfs로 판정하면 됩니다. - 저는 가로벽을 해당칸에 1, 세로벽을 해당칸에 2로 나타내어 비트처리해줬습니다. - 4방향을 다 한꺼번에 처리할 수도 있겠으나, 생각이 잘 안나서 저는 하드코딩 했습니다. - 그리고 여기서 오타나서 고생했습니다. 이게 방향..

https://www.acmicpc.net/problem/18235 18235번: 지금 만나러 갑니다 첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B) www.acmicpc.net 풀이 풀이를 쓸 생각이 없었는데, 1) 왠지 모르겠는데 난이도가 골드 3이나 되길래 인터넷에 검색해보니 2) 다들 이차원 dp로 풀이를 적길래 풀이를 작성합니다. 1. BFS 처음 Queue에 시작점, 도착점을 넣고, 각 단계마다 visited 배열을 초기화하여 한 단계 내에서 특정 지점을 두 번 방문하면 그 단계를 정답으로 출력하면 됩니다. 이진수의 특성 상 특정 점 s에서 x단계에 e로 가는 경우의 수는 (존재한다면) 유일하기에 가능한 풀이입니다. 2. ..

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으로 찾아야 한다는 사실을 발견할 수 있습..