취업 준비 및 일상

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/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 N은 최대 100이므로, 모든 경우를 탐색하는 브루트포스 풀이는 시간초과가 발생합니다. 따라서, 다른 알고리즘을 생각해봐야 합니다... 생각을 하다보면, (i번째 원소까지의 합이 sum이 되는 경우의 수) = (i-1번째 원소까지의 합이 sum - i번째 원소가 되는 경우의 수) + (i-1번째 원소까지의 합이 sum + i번째 원소가 되는 경우의 수)임을 알 수 있습니다. 다만 문제..

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 ..

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