본문 바로가기

알고리즘/백준

 (34)
[JAVA]백준_1003_피보나치함수 문제 : www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 유형 : dp 풀이방식 : 재귀로 풀때 시간초과 -> dp 메모이제이션 통과 피보나치 0 일땐 1 0 출력 (0 한개 1 X) 피보나치 1 일땐 0 1 출력 (0 X 1 한개) arr[x][0] = 숫자x일때 0의 개수 arr[x][1] = 숫자x일때 1의 개수 bottom-up 방식 : arr[i][0] = arr[i-1][0]+arr[i-2][0]; arr[i][1] = arr[i-1][1]+arr[i-2][1]; 소스코드 package BOJ; import java.util.Scanner..
[JAVA]백준_17478_재귀함수가뭔가요 문제 : www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제 유형 : dfs, 재귀 풀이 방식 : 간단한 재귀구현 문제이다. ----와 ____를 구분을 잘하면 틀리지 않았ㅣㅏㄴ모ㅓ앰노ㅕㅜㅊ파ㅐㅣㅁ니ㅏㅌㅇㄷㅁ 소스코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ_17478_재귀함수가..
[JAVA]백준_16922_로마숫자만들기 문제 : www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 문제 유형 : 브루트포스 풀이방식 : check[50*20+1] => 제일 큰 값(50) * 사용할 수 있는 문자의 개수(N 최대값 20) i = 1 개수, j = 5 개수, k = 10 개수, l = 50 개수 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class ..
[JAVA]백준_1743_음식물피하기 문제 : www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net 문제유형 : BFS 풀이방식 : BFS 기본문제 소스코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import jav..
[JAVA]백준_5014_스타트링크 문제 : www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제유형 : BFS 풀이방식 : 최단경로를 구할때는 DFS보다 BFS가 효율이 좋다 주의사항은 조건에서의 처음 부분과 제일 끝부분을 고려 소스코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util..
[JAVA]백준_2589_보물섬 문제 : www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제 유형 : BFS 풀이방식 : 육지인 지점 마다 BFS 탐색하여 최대 LEVEL 측정 소스코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.ut..
[JAVA]백준_5427_불 문제 : www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 문제 유형 : BFS 풀이 방식 : BFS형식으로 Queue 사이즈 만큼(한 턴)만 퍼지는 방식으로 1. 불퍼지고 2. 상근이 이동 상근이가 이동하지 못하는 턴일때 -> IMPOSSIBLE 상근이가 빠져나왔을때 -> time 출력 소스코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..
[JAVA]백준_1260_DFS와BFS 문제 : www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제유형 : 그래프 탐색, DFS, BFS 풀이방식 : 그래프 탐색(인접행렬을 이용한 DFS와 BFS) 소스코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import ..

티스토리툴바