본문 바로가기

분류 전체보기

 (201)
[BOJ 11060] 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다. 재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해 www.acmicpc.net 다이나믹 프로그래밍의 본질은 기본 문제를, 여러 작은 문제들로 나눠서 해결하는 것이다. i번째 칸까지 점프하는 최소의 값을 생각해보..
[BOJ 2302] 극장 좌석(접근법 및 시행착오 공유) https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 N; dp[0] = 1; dp[1] = 1; dp[2] = 2; for(int i = 3; i > M; for(int i = 1; i > v..
[BOJ 1495] 기타리스트 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 문제이다. 다이나믹 프로그래밍의 본질은, 복잡한 문제를 간단한 여러 문제로 나누어서 해결하는 것이다! 이 문제는, 마지막 곡의 볼륨의 최댓값을 나타내는 것이다. 다이나믹 프로그래밍에서는 점화식을 찾는 것이 중요하다. 그 점화식은 항상 성립해야 한다. 점화식을 찾는 것이 간단한 여러 문제로 나누어서 푸는 것의 핵심이다. i번째 곡의..
[BOJ 2098] 외판원 순회(비트마스크, 자세한 설명) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 분류이다. 다이나믹 프로그래밍의 본질은 소문제의 해결 방법을 이용해서 대문제를 해결하는 것이다. i번째에 방문되는 도시들과 i + 1번째 방문되는 도시들간의 관계를 정의해보자. i번째 방문되는 도시들의 집합을 A, i + 1번째 방문되는 도시들의 집합을..
[BOJ 10164] 격자상의 경로 https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 이번에 다룰 문제도, 다이나믹 프로그래밍 문제입니다. 꼭 지나야 하는 지점을 통해서, 최종 목적지(N, M)까지 도달하는 경우의 수를 찾아야 합니다. 위의 조건을 만족하는 경우의 수를 찾기 이전에, 임의의 (i, j)의 지점에 도달하는 문..
[BOJ 5557] 1학년(메모리 초과 발생 이유) https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 문제이다. 다이나믹 프로그래밍의 본질은, 큰 문제를 작은 문제를 통해서 해결한다라는 것을 잊지말자! i번까지의..
[BOJ 10942] 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍의 단골 소재인 팰린드롬이다. 다이나믹 프로그래밍의 핵심은, 큰 문제들을 해결하기 위해서 작은 문제들의 값을 이용하는 것이 핵심이다. 그렇다면, 팰린드롬을 분석해보자. 인덱스 i ~ j의 숫자들이 팰린드롬인지 확인해야 한다. 다이나믹 프로그래밍의 본질, 큰 문제를 해결하기 위해서 작은 문제들의 값을 이용해보자. DP[i][j]를 인덱스 i부터 j까지 펠린드롬 여부라고 정한다. DP[i][j]를 큰 문제라고 했을 때, ..
코딩테스트 실전 감각 키우기, 온라인 컴파일러 추천, BOJ 이번 글은 코딩테스트 실전 감각을 키우기 좋은 방법을 알려주겠습니다! 라인, 카카오, 네이버 등 IT기업들은 온라인 컴파일러를 통해서 코딩 테스트를 진행합니다. 이 말이 무슨 말이냐면, 삼성은 이클립스, 비쥬얼 스튜디오 등으로 실제 컴파일러를 통해서 코드를 작성한 후에 복사 붙여넣기가 가능하지만, 라인, 카카오, 네이버와 같은 회사들은 온라인 컴파일러에서 코드를 구현하도록 유도하고 있습니다. 왜냐하면, 부정행위 방지를 위해서 코드 복사 붙여넣기가 안되고 있기 때문에... 그래서 평소 공부를 하면서 실전 감각을 키울 수 있는, 온라인 컴파일러 사이트를 추천하려고 합니다. https://ideone.com/ Ideone.com Ideone is something more than a pastebin; it'..

티스토리툴바