시간 날 때, 끄적끄적

문제 설명 배추가 심어진 위치는 1, 심어지지 않은 위치는 0으로 표시되어 주어진 map에서 서로 인접한 배추들의 집합이 몇 개 있는지 확인하는 flood fill 문제 고민한 부분 flood fill 문제는 어떤 칸에 연결된 영역을 탐색하는 알고리즘이다. 구현은 BFS나 DFS 등 그래프 탐색 알고리즘을 반복 사용해 풀이하는 것이 많은 것 같다. 이 문제에서는 배열에서 연결된 배추들의 영역의 수를 세야 한다. 이를 위해 배열을 차례로 탐색하며 배추가 심어진 위치에 도달했을 때 BFS 알고리즘으로 인접한 영역을 탐색하고 BFS 실행 횟수를 반환하도록 구현했다. 이미 탐색한 영역을 중복 count하는 것을 방지하기 위해 어떤 표시를 해야했다. 배추 밭과 같은 크기의 배열을 만들어 표시를 할 수도 있지만 배..

문제 링크 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 설명 일정한 규칙에 따라 이동하는 주사위가 획득하는 점수를 계산하는 문제 주사위 방향을 전환하는 규칙과 주사위의 숫자를 바꾸는 규칙만 이해하면 어렵지 않게 풀 수 있는 문제 고민한 부분 주사위의 상태를 나타내기 위한 방법을 고민했다. 다른 분들의 풀이를 보면 길이 6의 list로 만들어 index별로 의미를 부여해 문제를 해결했는데 나는 헷갈려서 각각의 위치에 해당하는 6개의 변수를..

문제 링크 문제 설명 얼룩 덜룩한 색종이를 절반씩 잘라가며 한가지 색으로만 이뤄진 정사각형 모양의 색종이가 나올 때 까지 계속해서 자른 후 흰색과 파란색 색종이의 수를 각각 구하는 것 고민한 부분 반복문을 중첩해 풀이하려고 시도를 했으나 전체 종이의 크기에 따라 반복 횟수가 달라지기 때문에 반복문으로 풀이하는 것이 어렵다고 판단했다. 지금까지 공부한 내용 안에서 정해지지 않은 횟수의 중첩 반복문제를 해결하는 방법은 $^{1)}$재귀와 $^{2)}$그래프 탐색 알고리즘(BFS, DFS)가 있다. 문제를 분석해 보았을 때 DFS나 BFS로 탐색할 수 있는 그래프 형태로 만들 수 있는 방법을 떠올리지 못했다. 반복되는 부분을 찾아 재귀 함수로 문제를 구현하기로 생각했다. 나는 재귀 함수를 구현할 때는 종료 조..

문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 입력으로 받는 수 x에 대해 세 가지 종류의 연산을 반복해 1로 만들 수 있는 방법 중 연산 횟수가 가장 작은 방법의 연산 수를 찾는 문제 연산의 종류는 다음과 같다. x가 3으로 나누어 떨어지면, 3으로 나눈다. x가 2로 나누어 떨어지면, 2로 나눈다. 모두 해당 없으면 1을 뺀다. 고민한 부분 단순하게 생각해 숫자를 가장 빠르게 줄일 수 있는 연산 순서로 조건을 확인하도록 구현했다가 틀렸다. 연산 횟수의 수열이 증가하는 수열이 아니기 때문에 어떤 연산을 적용하는 것이 가장 좋은지 알 수 없다. 1부터 x까지 거꾸로 거슬러 올라가며 그 사이에 있는 값..

문제 링크 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제 설명 일정한 규칙에 따라 이동하는 주사위가 획득하는 점수를 계산하는 문제 주사위 방향을 전환하는 규칙, 점수를 계산하는 규칙을 꼼꼼하게 읽고 풀이하면 어렵지 않게 풀 수 있는 문제 고민한 부분 주사위의 상태를 나타내기 위한 방법을 고민했다. 다른 분들의 풀이를 보면 길이 6의 list로 만들어 index별로 의미를 부여해 문제를 해결했는데 나는 헷갈려서 각각의 위치에 해당하는 6개의 변수를 만들어 주사위를 modeling하는 것이..

문제 링크 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 2 차원 배열로 높이가 주어지는 지도에서 높이 차이가 1이고 길이가 L인 경사로를 놓아 지나갈 수 있는 경로의 수를 구하는 문제 배열의 크기가 $N \times N$일 때, 행 방향의 N개의 경로가 있고, 열 방향의 N개의 경로가 있어 행 방향과 열 방향 두번 탐색을 해주어야함 고민한 부분 경사로를 놓아야 하는 경우는 높이가 낮아지는 경우와 높아지는 경우로 나누어 생각할 수 있고 경사로의 높이는 1로 고정되어 있기 때문에 만약 높이 차이가 1보다 크다면 경로 확인을..

문제링크 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제 설명 일정한 규칙에 따라 세대를 거듭해 성장하는 드레곤 커브를 구현하면 되는 구현 문제 드래곤 커브가 성장하는 규칙을 어떻게 구현할 지 생각해내는 것이 어려운 문제 고민한 부분 드래곤 커브가 성장하는 규칙은 K 세대의 커브의 끝 점을 기준으로 K 세대의 커브 전체를 시계 방향으로 90도 회전시켜 붙인 것이다. 이전 세대의 마지막 점부터 시작점까지 역순으로 이동해 온 경로의 역순으로 이동한 방향을 반시계 방향으로 90도 회전..

문제링크 문제 설명 N+1일째 퇴사를 하기로 하고 N일까지 상담을 할 수 있을 때 최대로 받을 수 있는 수익을 계산하는 문제 매일 다른 상담을 선택할 수 있지만 상담에 소요되는 시간과 상담 비용은 모두 다르다 고민한 부분 단순히 loop를 순회하며 풀이할 수 있을 것이라고 생각했지만 해결하지 못해 다른 분들의 풀이를 공부했다. dynamic programming이라는 방법으로 풀 수 있었는데 dynamic programming은 프로그램 중간에 계산된 결과를 다른 공간에 저장해두고 이후에 참조해 사용하는 방식이다 Lesson learned dynamic programming이라는 개념을 알고는 있었지만 관련된 문제를 해결해 본 적은 없었다. 이번 문제는 다른 분들의 풀이를 보고 이해했지만 비슷한 문제가 ..

문제 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 설명 짝수 N명의 사람들을 두개의 팀으로 나누어 각 팀의 능력치를 계산해 비교해 차이가 최소인 팀 구성을 구하는 문제 팀이 구성되면 구성원 끼리 순서가 없기 때문에 조합을 찾는 문제로 생각해 풀 수 있음 고민한 부분 python의 내장 라이브러리인 itertools의 combinations함수를 사용할 수 있을지 확인해보고 싶었다 백트래킹 문제가 조금 까다롭게 나오는 경우 중간에 탐색할 필요 없는 조건을 찾아 가지치기를 해주어야 하는데 이 문제에서는 가지치기 할 필요 ..

문제링크 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 설명 직렬로 연결 된 4개의 톱니 바퀴 중 하나를 골라 돌리는 작업을 K번 반복했을 때 톱니의 상태를 찾는 문제 각 톱니는 자석처럼 S와 N로 구분되는데, 처음 상태에서 다른 극끼리 맞닿은 경우 회전이 전파된다 고민한 부분 회전하는 톱니를 구현할 방법을 고민했는데, list로 만들 수 있지만 파이썬 내장 함수인 deque를 사용하면 rotate 메소드로 쉽게 구현할 수 있다 그 외 어려운 부분은 없었지만, 문제를 꼼꼼하게 읽지 않아 회전한 후에 ..