https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 풀이방법 1. 리스트를 생성해 연결 정보를 담는다. 2. dp[N+1][2] 배열을 생성한다. => dp[N][0] : N번째 마을이 우수마을이 아닌 경우, dp[N][1] : N번째 마을이 우수마을인 경우 3. dfs를 진행한다. => dp[N][0] : 이전마을 포함된경우 , 안된경우 중 큰 값 => dp[N][1] : 이전마을 포함 안된 경우 dfs 진행 경로 (문제에 있는 테스트케..
https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이방법 1. visited[][] == 0 이라면 index를 가지고 탐색 진행 2. index 를 이용해서 사이클을 체크한다. (탐색 중 같은 인덱스를 가지고 있다면 count++) 3. 다른 index를 만난다면, 다른 사이클에 합류 되는 것 //example 3 4 DLLL DRUU RRRU 소스코드 import java.io.BufferedReader;..
https://www.acmicpc.net/problem/24337 24337번: 가희와 탑 일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다. www.acmicpc.net 풀이방법 예시(N : 9, A : 4, B : 3) 1. A의 값을 먼저 채워준다. (N-B 부터 차례로) 2. B의 값을 채워준다.(A값이 차있을 시, 비교 해서 더 큰 값으로 둔다) 3. A,B 가 1인 경우 예외가 있기 때문에 처리 해 줘야한다. A가 1인 경우 -> N-B 칸(제일 큰 값이 들어있는 칸)을 제거 한 후, 제일 앞 (building[0]) 에 MAX값을 넣는다. ex) N : 9..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이방법 열쇠를 먹으면 다시 BFS 를 돌아야 한다는 점을 Flag(isD) 를 이용해서 while문을 돌려서 진행 1. 입력을 받으면서, 가장자리 벽이 아닌 부분들을 리스트에 저장한다. !주의점 : 가장자리가 빈공간(.) 으로 시작한다는 보장이 없음 -> 문서이거나, 열쇠이거나, 문일 수 있다. 2. 열쇠의 정보를 가지고 있는 key 배열을 아스키 코드 값을 이용해서 만든다. a(97) ~ z(122) 이므..
순열? 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것 nPr = n*(n-1)*(n-2)* …*(n-r+1) ex) 1~10의 숫자 중에서 3개의 숫자를 중복없이 순서에 상관있게 선택하는 경우의수 10Ρ3 = 10 x 9 x 8 = > 720 가지 구현 방법 숫자를 담을 nums[] 배열과 방문처리를 해줄 visited[] 배열을 생성한다. perm(0) 함수를 타고 0 ~ N 까지 for문을 돌면서 방문한 적이 없다면 방문처리와 함께 nums[] 배열에 값을 넣어주고 perm(cnt+1) 재귀함수를 탄다. 계속 반복하다가 cnt 가 R(3)이 되었을 때, 배열을 출력하고 return 한다. p[] 배열 중 R(3)개 를 nums[] 배열에 순서에 상관 있게 뽑는 ..
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 최장 증가 부분 수열(LIS : Longest Increasing Subsequence) 과 같은 것이다. 풀이방법1 - dp dp[]배열을 생성한다.(i번째 원소를 마지막원소로 가지는 LIS 길이) 이전 nums[]값들을 순회하면서 지금 위치의 nums값이 더 크면 이전dp[]값+1 과 현재 dp[]값 중 큰 값을 넣..
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이방법 book[] 배열로만 사용했을 때, 시간초과가 나서 HashMap을 사용 했다. => 출력 할 때, 숫자가 주어지면 배열에서 바로 뺄 수 있는데, 문자열이 주어지면 앞부터 계속 비교하면서 탐색하기 때문 1. book배열에 주어진 포켓몬 이름을 넣는다. 2. 해시맵에 문자열을 키 값으로, 인덱스 변호를 value값으로 가질 수 있도록 넣는다. 3. 숫자가 주어지..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이방법 1. 이동하는 방향을 오,아래,왼,위 순으로 지정해두고 오른쪽회전이면 direction을 +1, 왼쪽회전이면 direction을 -1 로 변환 2. 이동하는 큐와 뱀큐를 만들어서 진행 3. 이동했을 때, board범위가 벗어나거나 뱀(2)이라면 while문을 빠져나옴 4. board가 사과(1)가 아니라면 뱀큐에 제일 처음들어온 요소를 꺼내서 board에 지움(0) 5. 방문한 board에 뱀이..
