자료구조 & 알고리즘/BOJ 문제풀이
-
[ 백준 4963] 섬의 개수 (Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 3. 8. 01:07
1.문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 2. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 3. 출력 각 테스트 케이스에 대해서, 섬의 ..
-
[ 백준 2579 ] 계단 오르기 (+ 2165: 포도주 시식) (Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 2. 3. 01:07
1.문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 2. 입력 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이..
-
[ 백준 9465] 스티커 (Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 2. 1. 15:32
1.문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 2. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고..
-
[ 백준 11054 ] 가장 긴 바이토닉 부분 수열 (Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 2. 1. 15:11
1.문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ ..
-
[ 백준 10844 ] 쉬운 계단수 (Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 1. 22. 23:55
1.문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 2. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 3. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 4. 포인트 동적계획법을 떠올려야하며 2차원 배열을 통해 풀어야한다. 점화식을 세울 수 있어야한다 [자리값 0] DP[ i ][ j ] = DP[ i-1 ][ 1 ] [자리값 9] -> DP[ i ][ j ] = DP[ i-1 ][ 8 ] 나머지 DP[ i ][ j ] = DP[ i-1 ][ j-1 ] + D..
-
[백준 11726] 2xn 타일링 (Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 1. 19. 22:29
1.문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 2. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 3. 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 4. 포인트 점화식을 세울 수 있어야한다 dp[ n+2 ] = (dp[ n+1 ] + dp[ n ]) / 10007 10007 로 나눔 다는 의미를 파악한다. 4. 문제 풀이 그림을 그려가며 규칙 찾아 점화식을 세울 수 있엇다. 어떤 원리인지는 파악하지 못했지만 규칙을 찾아 낼 수 있었다. 문제는 10007 로 나눈다는 의미를 파악하지 못해 조금 헤매었다. 문제에..
-
[백준 1463] 1로 만들기(Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 1. 19. 21:36
1.문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 2. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 3. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 4. 포인트 동적프로그래밍을 이용해 풀어야한다. 점화식을 세울 수 있어야한다 dp[ i ] = min(dp[ i/3 ] , dp[ i/2 ] , dp[ i-1 ] ) +1 top-down 과 bottom-up 의 풀이를 생각할 수 있으며 장단점을 알아야한다...
-
[백준 10757] 큰 수 A+B(Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 1. 11. 22:43
1.문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 A와 B가 주어진다. (0 < A,B < 1010000) 3. 출력 첫째 줄에 A+B를 출력한다. 4. 포인트 자료형에 대한 이해 구현 4. 문제 풀이 BigInteger 를 통한 간단한 풀이도 있지만 연습하는 과정이기에 함수를 사용하지 않고 풀어보았다. 처음에는 수를 직접 잘라 가는 풀이를 구성했다. 추후 다른 풀이들을 참고 한 결과 길이를 통해 접근하는 방법을 참고하여 고쳐보았고 결과적으로 메모리 와 시간을 줄일 수 있었다. 아마도 String을 직접 잘라서 사용해 객체를 많이 생성한 탓인 것 같다. // 처음 풀이 - string을 잘라가면 진행 import java.io.BufferedRea..