취업 준비 및 일상

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로 넘긴다면 이전의 모든 동작이 기록되므로 이를 방지하기 위해, 각 경우마다 배열을 복사하여 사용해야 합니다. 나머지 구현은 크게 ..

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 배열에 각..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 풀이 다들 2차원 배열로 잘 풀던데, 저는 머리가 그렇게는 안 돌아가서 3차원 배열을 만들었습니다. 1~N번째 수열의 값을 각각 arr[i]에 담아둡니다. 3차원 int 배열 dp[i][j][k]: 1~i번째 수를 j개의 구간을 이용하여 합하였을 때 최대값(k==0: i번째 수 미포함, k==1: i번째 수 포함) 그러면, dp[i][j][0] = max(dp[i-1][j..

https://www.acmicpc.net/contest/view/833 2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 Open Contest www.acmicpc.net 문제가 그리 어렵지 않아서 나도 다 풀 수 있었다. 풀이 A. 영수증 다 더한 값이 주어진 X랑 같은지 확인하면 된다. B. 커트라인 정렬한 후 K번째로 큰 원소의 값을 출력하면 된다. 동점자 처리는 안 해줘도 되는 듯하다. C. 연속 XOR 브루트포스로 하면 B

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