기록창고

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

HTML 삽입 미리보기할 수 없는 소스 다이나믹 프로그래밍 문제를 풀면서 느낀 것이 있다. 문제 풀이의 유형이 크게 재귀 함수를 이용하는 방법과 반복문을 이용하는 방법으로 나뉜다는 것이었다. 물론 모든 문제가 이런 것은 아니며, 또 문제를 푸는 사람에 따라 다른 방식을 이용할 수도 있을 것이다. 어쨌든 내가 문제를 풀 때에는 크게 두 가지 유형으로 나뉘는 느낌이었다. 그래서 이 두 유형의 차이점을 간단하게 기록하려고 한다. 1. 재귀함수 큰 문제를 작은 문제로 나누어 해결하는 방식 복잡한 문제에서 시작해 딱 필요한 하위 문제만을 해결하기 위함 스택 오버플로우같은 문제가 발생할 위험이 있음 피보나치 수열, 최소 편집 거리 등, 재귀적 구조가 명확한 문제에 적합 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/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제는 n에 대한 피보나치 수를 구하는 문제인데, 이 때 n이 음수일 수도 있다. 음수의 피보나치 수를 어떻게 구하는지에 대한 예시가 문제에 주어져 있다. 예를 들어 -1에 대한 피보나치 수, F(-1)을 구해보자. 이를 위해 잠시 1에 대한 피보나치 수 F(1)을 구하는 식을 생각해보자. F(1) = F(0) + F(-1..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 이번 문제는 숫자의 길이 N이 주어졌을 때, 길이가 N인 오르막 수의 개수를 구하는 문제이다. 즉, 각 자리의 숫자가 비내림차순이 되어야 한다. 그리고 주의해야할 점이 있다. 문제의 조건에 '수는 0으로 시작할 수 있다.'라는 말이 있다. 즉, N이 4일 때, 0000도 가능하다는 뜻이다. 이 문제는 다이나믹 프로그래밍으로..

HTML 삽입 미리보기할 수 없는 소스 https://school.programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 도시의 도로 상태가 주어졌을 때, 문제의 조건에 따른 전체 경로 수를 구하는 문제이다. 자동차는 오른쪽, 밑으로만 움직일 수 있다. 그리고 도로의 상태는 0(제한 없음), 1(갈 수 없음), 2(이전 방향과 같은 방향으로만 이동 가능)로 구성된다. 이 문제를 처음 접했던 시기가 대략 1년 전이었던 것 같다. 처음에는 도착 지점부터 위, 왼쪽으로 역..