Hailey

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net | 문제 해결방법 개인적으로 굉장히 쉬운 문제였다. 단지별로 단지 번호, count만 잘 처리해주면 인접리스트 + bfs로 쉽게 해결 관련 알고리즘 : 인접리스트 + bfs [JAVA] 해설 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arra..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net | 문제 해결방법 관련 알고리즘 : bfs (dfs로 시간초과가 난 후 방법을 bfs로 변경) 인접행렬 * O(V^2) 인접리스트 * O(V+E) 처음에 인접행렬 + dfs로 풀 방법은 시간초과 이후 인접리스트 + bfs로 방법을 바꾸어 풀어서 해결했다. [JAVA] 해설 코드 1. 인접행렬 + dfs (시간초과) package graph; import java.io.BufferedReade..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net | 문제 해결방법 관련 알고리즘 : DP 규칙 찾기 나의 풀이 방법은 n이 홀수인 경우와 짝수인 경우를 나누어 계산한다. n=1인 경우는 단 한 가지 n=2인 경우는 세 가지 n=3인 경우 n이 홀수일 경우의 규칙은 바로 전에 구한, n=2일때의 타일들에 맨 앞, 맨 뒤에 하나의 타일을 붙여주는 것이다. 이 경우 2x1 타일로만 이루어진 경우가 중복해서 나오기 때문에 -1을 해준다. f(3) = f(2) * 2 - 1 n=4인..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net | 문제 해결방법 이 문제를 푸는데 약 두 시간이 걸렸다. 최대한 힌트를 참고하지 않고 풀어보려고 노력했더니 더 공부가 많이 되었다. 그리고 DP문제는 어떤 값을 메모제이션 할 것인지를 결정하는 것이 굉장히 중요한 것 같다. 1. 첫 번째로 고려할 점 처음에는 dp배열에 계단수의 시작되는 수가 index인 위치에 각 경우의 수를 넣어주었다. f(1) 인 경우, 0으로 시작되는 수만 제외하면 1부터 9까지 각각 자신의 수로 수를 만들 수 있다. 그래서 경우의 수는 f(1) 0 1 2 3 4 5 6 7 8 9 0 ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net | 문제 해결방법 이 문제는 백준의 DP문제인 2579번_계단 오르기 문제와 거의 동일하다. 고려해야할 조건은 3번 연속으로 포도주를 마시면 안되는 것으로 계단 오르기 문제와 동일하고, 이 문제에서 추가해준 조건은 해당 위치의 포도주를 마신 경우와 마시지 않은 경우의 포도주량을 비교해 더 큰 값을 메모제이션 해주는 것이다. 계단오르기는 수의 크기가 오름차순으로 이루어져 있었기 때문에 이를 고려해줄 ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net | 문제 해결방법 2차원 배열에서 목표지점까지 갈 수 있는 경로의 개수를 구하는 문제이다. 관련 알고리즘 : DFS + DP 핵심 아이디어는 방문했던 길을 한번 더 방문하지 않는 것 방문하지 않은 길을 한번 탐색하면, 결과는 두 가지가 나올 수 있다. 1. goal까지 갈 수 있는 경우 2. 사방으로 더이상 갈 길이 없는 경우 알고리즘 순서 1. 처음에 2차원 dp배열을 만든 후 -1로 초기화 해준다 ..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 이 문제는 백준 11053번 가장 긴 증가하는 부분 수열을 풀고 for문 조건만 수정해서 제출했다. 11053_가장 긴 증가하는 부분 수열 해설법 https://hailey-v.tistory.com/9 [JAVA]백준 11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/110..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 요즘엔 DP를 중점적으로 공부하고 있기 때문에, DP관련 문제들만 찾아서 풀고 있다. 오늘은 그 중에서 '11053_가장 긴 증가하는 부분 수열'과 '11722_가장 긴 감소하는 부분 수열' 두 문제를 풀어보았다. | 문제 해결방법 관련 알고리즘 : 최장 증가 부분 수열(LIS) + DP 주어진 요소들 중에서 조건에 맞..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제만 이해하면 해결방법은 단순한 조합문제로 아주 쉬운 문제이다. 조합의 식을 nCr 이라고 할 때, 강 동쪽을 n 강 서쪽을 r로 생각하면 된다. 동쪽에서 r개의 사이트를 고르는 경우의 수(순서가 없고 중복도 없다.) r개의 조합을 고르면, 서쪽 사이트와 순서대로 선을 그으면 되기 때문에 겹칠 일이 없다. 따라서, 우리는 0< N, M

[JAVA] 백준 5904번: Moo 게임 백준 5904번 https://www.acmicpc.net/problem/5904 문제 문제는 이해하기 쉽다. moo 들의 조합으로 이루어진 문자열의 규칙을 찾아서, 입력되는 N번째의 문자가 어떤 문자('m' 또는 'o')인지 출력하면 된다. 보면 규칙적으로 m은 단어의 첫 번째에서만 나온다. 규칙 찾고, 첫 번째 단어인지 체크 → 맞으면 'm', 아니면 'o'를 출력하면 끝 이제 규칙을 찾아보자 규칙 문자열이 길어지는 규칙을 보면 S[k] = S[k-1] + moo+o(k) + S[k-1]* 이다. 즉, 가운데를 기준으로 앞, 뒤에 이전 값이 붙는다. 이를 토대로 입력된 숫자(N)가 10 정도 된다고 가정했을 경우, 수많은 moo 들을 크게 왼쪽 moo(Lef..