기록창고

Jürgen from Pixabay">Image by Jürgen from Pixabay  https://www.acmicpc.net/problem/3197 1. 개요 이 문제는 2차원 배열의 호수가 주어진다. 호수의 각 요소는 물('.'), 얼음('X'), 백조('L') 중 하나이고 백조는 총 2마리가 존재한다. 그리고 물과 상하좌우 중 한 곳이라도 접촉한 얼음은 하루가 지나면 녹아서 물이 된다. 이 때, 상하좌우로만 이동할 수 있는 백조는 며칠 후 서로 만날 수 있는지를 구하는 문제이다. 이 문제의 알고리즘 분류에서도 알 수 있듯, 너비 우선 탐색(BFS)을 이용하여 문제를 풀었다. 처음에는 두 백조가 서로 만날 수 있는지 구하는 코드는 항상 하던 것처럼 큐를 이용하면 될 것이라 생각했다. 그리고 얼..

Pixabay로부터 입수된 Lukas Kurth님의 이미지 입니다.">Pixabay로부터 입수된 Lukas Kurth님의 이미지 입니다. 1. 개요 이번에 배낭 문제(KnapSack Problem)를 포함한 DP 문제를 위주로 풀어보았다. 배낭 문제를 풀 때 중요한 점을 간단히 요약하자면 다음과 같다.만약 가방에 담을 수 있는 경우현재 물건 순서에서 현재 가방 용량에서 최대 만족도 = 현재 물건 안 담은 경우, 현재 물건 담은 경우 중 더 큰 값예: dp[물건 index][가방 용량] = max(dp[물건 index - 1][가방 용량], dp[물건 index - 1][가방 용량 - 현재 물건 무게] + 현재 물건 가치)만약 가방에 담을 수 없는 경우현재 물건 순서에서 현재 가방 용량에서 최대 만족도 =..

Pixabay로부터 입수된 eommina님의 이미지 입니다.">Pixabay로부터 입수된 eommina님의 이미지 입니다.  링크: https://www.acmicpc.net/problem/21736  이 문제는캠퍼스 지도의 가로, 세로 길이가 주어지고, 지도의 빈 공간과 벽 등이 문자 혹은 문자열로 주어진다. 그리고 'I'에서 시작해서 몇 명의 친구('P')를 찾을 수 있는지 알아내는 문제이다. 이 문제는 가장 기본적인 형태의 DFS(혹은 BFS) 문제이기에 아래의 절차대로 진행되게 코드를 작성하였다. N, M, N x M 크기의 캠퍼스 값을 입력 받는다. 캠퍼스에서 'I'의 위치를 저장한다.(n, m) 좌표를 인자로 받는 DFS 함수를, 2번 과정의 위치 좌표를 기준으로 실행한다.만약 (n, m)를 ..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이번 문제는 주어진 조건에 따라 계단을 끝까지 올라갔을 때, 점수의 최대값을 구하는 문제이다. 이 문제는 2년 전에 처음 접했다가 다른 분의 풀이를 보고 그대로 적용했었던 문제라 다시 한 번 복습할 겸 풀어 보았다. 처음에는 재귀함수처럼 문제를 풀었지만 제대로 풀리지가 않았다. 그래서 다시 한 번 생각해보니 계단을 처음부터 올라가는 문제, 즉 처음부터 점진적으로 답을 찾..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이번 문제는 n이 주어졌을 때, 1, 2, 3만을 이용하여 n을 만들 수 있는 가지수를 구하는 문제이다. 그리고 주의할 점이 있는데, 만약 n이 4일 경우, 1 + 3과 3 + 1은 서로 다른 경우로 취급한다는 것이다. 이 점 때문에 처음에는 어떻게 접근해야 할지 도저히 감이 잡히지 않았다. 하지만 가만히 생각해보니 생각보다 쉬운 문제였다. 예를 들어, n이 4일 경우, dp[4]를 생각해보자. 1, 2, 3만을 이용하여야 하기에 n - 1, n - 2, n - 3까지 고려해야 한다. 우선 3이..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이번 문제는 숫자가 하나 주어질 때, 이 숫자를 1로 만드는데 필요한 횟수 중, 가장 작은 값을 구하는 문제이다. 숫자에 이용할 수 있는 연산은 아래의 3가지이다. 숫자가 3으로 나누어 떨어지면 3으로 나눈다. 숫자가 2로 나누어 떨어지면 2로 나눈다. 숫자에서 1을 뺀다. 이 문제는 각 숫자마다 도달할 수 있는 최소한의 횟수를 저장하면서 진행하면 답을 구할 수 있는, 전형적은 다이나믹 프로그래밍 문제라 할 수 있다. 예를 들어, 현재 숫자가 12이고 각 숫자마다의 최소 ..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 이번 문제는 N이 주어질 때, 주어진 조건에 따라 N개의 타일로 구성된 직사각형의 둘레를 구하는 문제이다. 처음에는 규칙을 알아내려 했지만, 잡힐듯 말듯 한 것이 너무 아리송했다. 하지만 자세히 보니 규칙이 있었다. 문제의 그림을 기준으로, 우선, N이 1일 경우는 정사각형이라 가로, 세로 길이가 각각 1이다. 그리고 N이 2일 때는 가로, 세로가 각각 1, ..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 이번 문제는 운동 일수 N, 운동 키트 개수 K, 그리고 K개의 (운동 키드 별) 중량 증가량이 주어졌을 때, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 구하는 문제이다. 이 문제의 알고리즘 분류에서도 확인할 수 있듯, 모든 경우를 검사해야 하는 문제이다. 그리고 예제의 그림(표)에서도 확인할 수 있듯, 만약 운동 키트가 3..