취업 준비 및 일상

https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 한 번에 시행동안 1) 가장 적은 물고기를 가지고 있는 어항에 물고기 넣어주기 - putFish() 2) 첫 번째 마법 - magic1() 3) 물고기 수 조절 - spread() 4) 다시 일자로 펴주기 - badak() 5) 두 번째 마법 - magic2() 6) 물고기 수 조절 - spread() 7) 다시 일자로 펴주기 - badak() 8) 최대 물고기 수 어항 - 최소 물고기 수 어항

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/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) 시간 복잡도를 가져 시간초과가 발생하게 됩니다. 생각을 해보면, 연결..