[백준 / C++] 14002번: 가장 긴 증가하는 부분 수열 4 (dp)

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 일반적인 dp를 이용한 N^2짜리 LIS 풀이로 가장 긴 부분 수열의 길이를 구하고 추가적인 코드를 통해 O(N)에 경로를 추적할 수 있다. 일단 LIS의 길이를 구하는 for문을 마치고 나면 len[i]에는 A[i]를 부분 수열의 마지막 원소로 썼을 때의 LIS 길이가..

• format_list_bulleted PS/백준
• · 2023. 7. 27.
• textsms

[백준 / C++] 2638번: 치즈 (BFS, 구현)

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 구현, 그래프 탐색 (BFS) 접근 방법 및 구현 DFS로도 풀리겠지만 나는 BFS로 풀었다. 이 문제에서 핵심은 외부 공기와 내부 공기다. 내부 공기(구멍)는 공기로 취급 안 해서 닿아있는 공기의 개수에 포함하지 않는다. 외부 공기와 내부 공기를 파악하기 위해 우선 0인 곳을 찾아주었다. 하나의 visited 배열을 공기를 탐색하는데..

• format_list_bulleted PS/백준
• · 2023. 7. 27.
• textsms

[백준 / C++] 15686번: 치킨 배달 (삼성 SW 역량테스트 기출)

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 구현, 브루트포스 알고리즘, 백트래킹 접근 방법 입력으로 받은 치킨집에서 M개를 고르는 모든 경우의 수를 다 따져보며 치킨 거리를 구한다. 구현 c++의 STL에 있는 next_permutation을 이용해 치킨집 중 M개를 고르는 조합을 만든다. 입력으로 들어오는 치킨집의 개수가 x개라고 하면, x개의 원소 중 M개가 1, ..

• format_list_bulleted PS/백준
• · 2023. 7. 26.
• textsms

[백준 / C++] 2193번: 이친수 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 0은 여러개 이어져도 상관없다. 1은 2개 이상 연속되면 안 된다. 따라서 0 이전의 숫자는 0 또는 1이 가능하고, 1 이전의 숫자는 0만 가능하다. 그럼 점화식은 아래와 같이 나타낼 수 있다. n번째 숫자가 0인 경우의 수: dp[n][0] = dp[n-1][0] + dp[n-1][1] n번째 ..

• format_list_bulleted PS/백준
• · 2023. 7. 26.
• textsms

[백준 / C++] 11057번: 오르막 수 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 이어지는 숫자는 각 자리의 숫자보다 크거나 같아야 한다. 따라서 다음과 같은 규칙을 발견할 수 있다. 0으로 끝나려면 앞의 숫자는 0이어야 한다. 1로 끝나려면 앞의 숫자는 0 또는 1이어야 한다. 2로 끝나려면 앞의 숫자는 0 또는 1 또는 2여야 한다. ... 이를 점화..

• format_list_bulleted PS/백준
• · 2023. 7. 26.
• textsms

[백준 / C++] 7569번: 토마토 (BFS, 3차원 배열)

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 난이도: solved.ac 골드 5 box라는 3차원 배열을 만들고, 해당 배열에 입력을 받았다. 그리고 먼저 box[i][j][k] = 1인 곳을 큐에 담고, 큐에서 하나씩 꺼내 주위 위, 아래, 오른쪽, 왼쪽, 앞, 뒤 중 0인 곳은 값을 1씩 증가시켜 저장하였다. 0일차를 1로 시작했으므로 box[i][j][k]가 가장 큰 곳에서 1을 뺀 값을 출력하도록 해주었다. 그..

• format_list_bulleted PS/백준
• · 2023. 7. 22.
• textsms