본문 바로가기

알고리즘

 (63)
[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] Union-Find 유니온 파인드(Union-Find) ① 유니온 파인드란? ▷ 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다. ▷ 상호 배타적 집합(Disjoint-set)이라고도 합니다. ▷ 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. ▷ 2가지 연산으로 이루어져 있습니다. ▶ Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 ▶ Union : x와 y가 포함되어 있는 집합을 합치는 연산 ② 그림으로 보는 Union-Find 위와 같이, 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만듭니다. i : 노드번호, P[i] : 부모 노드 번호 를 의미하며, 즉 ..
[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..

티스토리툴바