취업 준비 및 일상

백준 13459번: 구슬 탈출 백준 13460번: 구슬 탈출 2 백준 15644번: 구슬 탈출 3 백준 15653번: 구슬 탈출 4 3달 전 즈음에 구슬 탈출 2를 풀었습니다. 당시 구현에 급급하여 간신히 풀었고, 풀고 나서 '어휴 이런 문제는 꼴도 보기 싫다~' 하고 눈 앞에서 치워버린 기억이 납니다. 다시 풀어보니, 구현이 적당히 많고 까다로우며, 시간 커팅할 부분이 많은 흥미로운 문제라 느껴집니다. 풀이 '백준 13459번: 구슬 탈출'을 기준으로 설명합니다. 기본 구현 0) 기울일 때마다 움직이는 건 구슬 2개뿐이므로, 각 구슬의 좌표를 따로 저장하여 관리합시다. 그리고 구멍 좌표도 따로 저장해둡니다. 1) 방향과 빨간 구슬, 파란 구슬 위치에 따라 어느 구슬을 먼저 움직일 지 결정합니다. 2) ..

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/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 안 되는 풀이: 그리디 왠지 '왼쪽 위에서 부터 시작하여, 큰 사각형이 가능한대로 붙이면 될 거 같다'라는 생각이 들기도 합니다. 반례) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 출력값: 8 정답: 3 -> 잘못된 배치를 했을 경우, 이를 무르는 방법이 있어야 할 거 같습니다. 올바른 풀이..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 삼성 스타일의 구현 문제이나, 한 단위의 시뮬레이션마다 여러 경우가 있어 백트래킹으로 모든 경우를 체크해줄 필요가 있습니다. 한 단위의 시뮬레이션마다 배열의 값이 바뀌므로, 배열을 전역으로 관리하거나, 각 경우마다 call by reference로 넘긴다면 이전의 모든 동작이 기록되므로 이를 방지하기 위해, 각 경우마다 배열을 복사하여 사용해야 합니다. 나머지 구현은 크게 ..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이 는 딱히 할 말이 없네요. 문제에서 주어진 조건대로 구현을 하면 됩니다. 자잘한 팁 예시의 4x5 지도에서 주사위가 1000번 구르는 상황을 생각해보면, 같은 위치에 대해 여러 번 점수를 구할 겁니다(비둘기집 원리: 50번 이상 점수를 계산하게 되는 칸이 존재함). 이를 전처리로 구해두면 실행 속도가 빨라집니다. 아래 코드에서는 scoreMap이라는 이차원 int 배열에 각..

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 방향으로 움직일 때 ..