취업 준비 및 일상

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개를 채운다고 생..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 섬이 떨어져있고, 이를 최소 길이의 다리를 연결하여 하나로 만든다... -> MST가 떠오릅니다. MST를 찾는 알고리즘에는 크루스칼(유니온 파인드로 V-1개 연결), 프림(우선순위 큐 이용) 알고리즘이 있는데, 본 풀이에서는 크루스칼을 활용합니다. 1. 섬의 개수를 세준 후, 각각의 섬을 1, 2, 3, ... 으로 칠해줍니다. 저는 BFS로 했습니다. 2. 가능한 모..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 문자열에 대해서 for문을 돌면서, 1) 문자가 오는 경우: 문자는 입력 순서 그대로 문자열에 넣어주면 됩니다. 2) 연산자가 오는 경우: 연산자는 기본적으로 스택에 저장해두었다가, 필요한 시기가 오면 스택에서 꺼내 문자열에 붙입니다. 1. 덧셈, 뺄셈이 오는 경우 - 이전에 있는 덧셈, 뺄셈, 곱셈, 나눗셈은 현재 연산자보다 먼저 계산되어야 합니다. 스택에 저장한 연산을 꺼내 문자열에 ..

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/25201 25201번: 보드 뒤집기 게임 첫 번째 줄에는 현재 격자판 상태에서의 빨간색으로 칠해진 칸의 좌표의 개수 $N$, 곰곰이가 원하는 격자판 상태에서의 빨간색으로 칠해진 칸의 좌표의 개수 $M$ 이 공백을 사이에 두고 주어진다 www.acmicpc.net 풀이 인터넷 서핑하다가 우연히 1줄 풀이를 보고, '그냥 구현만 해서 날로 먹을까?' 했는데 그러기엔 양심이 찔려서 정리했습니다. 곰곰컵 공식 풀이가 있습니다만, bijection 부분부터 모르겠어서 이와 유사한 문제인 Codeforces Global Round 2 C번 문제의 Editorial을 보고 이해했습니다. 다음 명제는 참입니다: '곰곰이가 뒤집기 마법을 사용하여 현재 격자판에서..

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

이전 글 2022년 현대모비스 알고리즘 경진대회 - 예선 후기 준비 여러모로 열약한 시험환경 덕분(?)에, 본선에 진출했습니다. 운 좋게 진출한 본선인 만큼 성의를 보이기 위해 대회 알고리즘을 살짝 공부했습니다. 물론 3일동안 여러 알고리즘을 다 볼 순 없으니, 예선에 나온 알고리즘 정도만 복습한다는 마인드로 익혔습니다. 그리고 이는 좋은 선택이었습니다. 테스트 환경 예선에서 무수한 항의를 받아서인지, 많~~이 좋아졌습니다. 내부 테스트케이스에 대해 채점도 해주며, IDE도 사용가능하며, 복붙도 가능해졌습니다. 다만 '테스트케이스별로 채점' 및 '동점자는 시험 종료 시간이 빠른 순' 기준은 아직도 살짝 물음표가 붙긴 합니다만, 기존의 불편함에 비하면 이 정도는 '시험의 개성'이라고 볼 수 있는 수준이지 ..

https://www.acmicpc.net/problem/14622 14622번: 소수 게임 인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있 www.acmicpc.net 풀이 에라토스테네스를 이용하여 500만 미만의 소수를 저장합니다. 또한, 특정 소수를 방문했는지 기록할 boolean 배열도 하나 선언해줍시다. 대웅이와 규성이가 번갈아가면서, 1) 소수가 아닌 수를 불렀는지, 2) 이미 부른 소수를 불렀는지, 3) 한 번도 안 부른 소수를 불렀는지를 체크하여 문제 조건대로 처리해줍니다. N은 최대 10만이기에, 3번째로 큰 소수를 배열같은 곳에 저장하면 당연히 시간초과..

https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 풀이 지문 길이를 보는 순간 한숨이 나옵니다. '아니, 이런 거 까지 풀어야 하나?' 하는 생각이 들지만, 마음을 가다듬고 지문을 읽어보면 생각보다 요구하는 바가 명확하며, 구현도 생각보다 쉽습니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..