본문 바로가기

Preparing Coding Test114

[Java/백준/DP] 1003번: 피보나치 함수 문제 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 실패 코드(시간초과) 초과 뜰 것 같긴 했다 ㅎ... import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class Main{ static long[] zerone = new long[2]; public static long fib(int n) { if(n==0) { zer.. 2020. 9. 30.
[Java/백준/DP] 2748번: 피보나치 수 2 문제 www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된�� www.acmicpc.net 코드 틀렸습니다가 자꾸 떠서 속상했는데 알고보니 결과값이 int형의 범위를 넘어가기 때문이었다. 안심^^ import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputS.. 2020. 9. 25.
다이나믹 프로그래밍 (Dynamic Programming) 동빈나 유튜브 참고 www.youtube.com/watch?v=FmXZG7D8nS4 다이나믹 프로그래밍 = 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 다이나믹 프로그래밍을 사용할 수 있는 조건! 큰 문제를 작은 문제로 나눌 수 있다. (분할-정복의 개념) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (핵심!!) 예시 : 피보나치 수열 f(n) = f(n-1) + f(n+1) 이미 계산한 결과를 배열에 저장하는 메모이제이션(Memoization)이 분할-정복 기법과 다른 점이다. 어떤 조건일 때 종료되는지도 알아둬야 함! #include int dp(int x){ //언제 끝나는지 명시해주는 역할 if(x==1) return 1; if(x==2) return 1; return .. 2020. 9. 25.
[Java/백준/BFS] 1697번: 숨바꼭질 문제 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 코드 visited[start]를 처음에 1로 준 이유는, start의 위치도 아래의 if문에서 visited[~]==0의 조건에 걸릴 수 있기 때문이다. 계속 저 f-1 >=0 을 >라고 해서 틀렸다고 떴었다..... import java.util.*; import java.io.*; public class Main { static int[] visited = new in.. 2020. 9. 24.
[Java/백준/BFS, DFS] 2644번: 촌수계산 문제 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net BFS 코드 adjacent라는 ArrayList[] 배열을 만들어서 각 사람들의 부모-자식 관계 사람들을 추가해준다. BFS queue 안에 알아야 할 사람 중 한명(start)를 넣고 거기서부터 BFS로 검사해 나간다. visited[사람]에는 start로부터 몇칸씩 떨어져 있는지가 입력된다. queue에서 제일 처음 것을 빼냈을 때 이것이 start와 관계를 묻는 사람(end)이면 r.. 2020. 9. 21.
[Java/백준/BFS] 7576번, 7569번: 토마토 문제 (2차원 배열) www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 코드 백준 미로 탐색 문제와 비슷한듯 다르다. 토마토 문제는 익은 토마토로부터 검사를 시작하는데, 그 갯수를 알 수 없기 때문이다. 다행히 입력할 때부터 선언한 queue 안에 익은 토마토의 좌표를 넣어주면 된다는 것을 알게 되었다.^__^ bfs 함수 queue 안에는 익은 토마토의 좌표가 들어있다. 검사할 토마토의 사방을 보았을 때, >> 안익은 토마토일 것 && 지나.. 2020. 9. 21.
[Java/백준/BFS] 2178번: 미로 탐색 문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 코드 최단거리는 BFS로 푸는 것이 좋다. 한 노드에서 연결된 각 노드들을 동시에 검사하기 때문이다. 이 문제에서의 visited는 boolean[][]이 아닌 int[][]이다. (지나갔는지 체크하는 용도가 아니라 몇칸 옮겼는지 기록하는 역할) (0,0)에서 시작해 (n-1,m-1)까지 BFS로 검사하다 제일 먼저 (n-1,m-1)에 도착하는 경로가 있으면 visited[n-1][m-1]에 입력된다. 다른 경로로 visited[n-1].. 2020. 9. 21.
[Java/백준/DFS] 1012번: 유기농 배추 문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 코드 단지번호 붙이기와 비슷하게 풀었다 아이고 속시원해 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class Main{ static int[] dx = {0,0,-1,1}; s.. 2020. 9. 19.
[Java/백준/DFS와 BFS] 2667 - 단지번호붙이기 문제 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 코드 DFS가 재귀를 써도 되기 때문에 자주 사용하게 된다. 입력받은 2차원 배열은 village에 저장한다. dx, dy를 사용해서 상하좌우 좌표를 정해준다. 이중 for문을 돌면서 1인 좌표를 발견하면 dfs함수를 호출한다. 굳이 visited를 사용하지 않아도 dfs가 시작되면 village의 해당 좌표 값을 0으로 바꾸어 준다. (그럼 다음에 쓰루함) 해당 좌표에서 dx, dy로 상하좌우를 탐색하면.. 2020. 9. 17.

티스토리툴바