곽로그

문제 www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 코드로 설명이 되어서 풀이는 패스. 주의해야 할 점은 출력하는 피보나치 수의 자료형은 long 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main ..

문제 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 map을 순회하면서 칸이 비어있으면 넘어가고, 집인 경우 탐색을 한다. 한번 탐색을 할 때 방문처리를 한 것이 다음 탐색에도 쓰이기 때문에 그 칸을 다시 탐색하는 경우는 없다. 따라서 bfs로도 풀 수 있고, dfs로도 풀 수 있다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamRead..

문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근 (0,0)에서 (N-1,M-1)까지 이동할 때 최단거리를 구하는 문제이다. 탐색이므로 dfs로도 풀 수 있지만, dfs로 풀경우 모든 경우를 탐색하게 되므로 시간복잡도는 O(4^MN)가 된다. 이 경우 시간초과가 나므로 dfs로 풀면 안된다. 최단거리라고 했으므로 bfs로 풀어야한다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.Inp..

문제 programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이 DFS로 풀 수 있다. 우선 (x,y)와 같은 색인 영역의 수를 구하는 함수를 생각해보자. 아래와 같이 색칠판이 있을 때 (3,0)을 기준으로 (3,0)과 같은 색인 영역의 크기를 구해보자. (3,0)에서 북, 동, 남, 서 를 차례로 탐색한다. (3,0)과 이웃한 셀을 (x,y)라고 하자. (x,y)이 (3,0)과 같은 영역으로 분류되려면, 영역내의 셀이어야 한다. ..

문제 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 ↑ → ↓ ← 순서로 이동한다고 하자. (N-1, M-1)에 도착하게되면 파란색부분은 더이상 이동할 수 있는 방향이 없으므로 (0,3)까지 return이 된다. 그러면 다시 (0, 3)에서 ↓으로 호출을 한다. 그런데 여기서 (0, 0) ~ (N-1, M-1)로 가는 첫번째, 두번째 경로에서 중복이 발생하게 된다. 초록색으로 표시한 길은 이미 첫번째 경로에서 구했던 경로다. 다시말해 (1, 3)에 도착하면..

문제 www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 N과 M (9)를 확실히 이해했다면 (10), (11) (12)도 비슷한 방향으로 풀 수 있다. N과 M (9)에 대한 풀이는 여기 를 클릭 문제의 핵심은, 0~ N-1까지의 숫자 중에서 index에 대한 조건, 값에 대한 조건 체크를 하는 것이다. index에 대한 조건 체크만 있다면 이 문제는 N과 M(4) 와 같은 문제다. 2 3 7 7 9 에서 비내림차순으로 숫자를 뽑을 때 인덱스를 기준으..

문제 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이1- 브루트 포스 모든 경우의 수를 다 확인해보는 방법이다. 절차는 아래와 같다 현재위치에서 다음위치로 이동한다 이때 다음 위치가 유효한지 확인한다 다음 위치가 boundary안에 있다 현재위치보다 다음위치의 높이가 낮다 다음위치로 이동한다 이동한 위치가 도착점(N-1, M-1)이면 count를 1 증가시킨다 하지만 모든 경우의 수를 다 체크하면, 시간 초과가 난다. 가로 N, 세로 M인경우 (0,0)에서 ..

문제 www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 이 문제는 중복을 어떻게 처리할지가 관건이다. 뽑을 수 있는 숫자가 담긴, 크기가 N인 배열을 candidates라고 하자. 그리고 candidates에서 뽑은 숫자를 넣는, 크기가 M인 배열을 numArray라고 하자. 그러면 numArray에 들어갈 수 있는 숫자는 candidate의 0번째 인덱스부터 N-1인덱스 중에서 이전에 선택하지 않은 인덱스이다. 그런다음 중복된 값에 대한 처리를 해줘야..