본문 바로가기

알고리즘

 (100)
백준 1670 정상회담 2 https://www.acmicpc.net/problem/1670 1670번: 정상 회담 2 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. www.acmicpc.net 다이나믹 프로그래밍 문제 점화식은 f(n) = { f(n-2) * f(0) } + { f(n-4) * f(2) } + ... + { f(k - m) * f(m-2) } + ... + { f(0) * f(n-2) }다. 예를 들어서 f(4) = f(2) * f(0) + f(0) * f(2) f(6) = f(4) * f(0) + f(2) * f(2) + f(0) * f(4) 이다. 그림을 보며 이해해보자 . 여섯명짜리 악수를 대표로 살펴보자 이렇게 세 가지 경우가 나올 수 있다. 8개..
백준 1219 오민식의 고민(Java) https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착�� www.acmicpc.net 벨만 포드 알고리즘을 활용한다. 코드를 보면 이해할 수 있을 것 같다. import java.io.*; import java.util.*; public class Main { private static int N; private static int startCity; private static int arriveCity; private static int nTransport; private ..
백준 9661 : 돌 게임 7 https://www.acmicpc.net/problem/9661 9661번: 돌 게임 7 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 시뮬레이션을 해보면 승패승승패가 반복되는 걸 확인할 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader br = new BufferedReader(new InputStreamReade..
백준 1111 IQ Test(Java) https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 내 아이큐를 테스트하는 것 같은 문제.. arr[i+1] - arr[i]를 arr[i] - arr[i-1] 로 나누면 a를 구할 수 있다. 점화식을 세워보면 금방 알 수 있당 a를 구하면 b를 구하는 건 껌이다. A를 출력해야하는 상황과 B를 출력해야하는 상황을 잘 구별하는 게 이 문제의 핵심이다. 둘 모두 "주어진 배열의 다음 숫자"에 대한 것임을 명심하자! 만약 배열의 크기가 1이라면 그 다음에 어떤 숫자든 올 수 있다. --> A 예를 들어서 [3] 그 숫자..
백준 16946 벽 부수고 이동하기4(JAVA) https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 간만에 알고리즘을 푸려니까 잘 안된다 이 문제는 벽이 없는 구간들을 그룹화 하는게 중요하다. 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 위와 같은 인풋이 들어오면 다음과 같이 그룹화해준다. 1 10 10 1 11 1 1 12 11 11 1 12 11 11 1 12 각각을 그룹화 한 다음 Map에 그 그룹이 몇개인지 저장한다. 그룹 10 : 2 그룹 11 : ..
백준 14867 물통(JAVA) https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최� www.acmicpc.net 모든 경우의 수를 탐색하는 BFS... DFS로 하면 시간초과 뜬다. import java.io.*; import java.util.*; import java.util.concurrent.LinkedBlockingDeque; public class boj14867 { static class Pair { int n ,m; Pair(int a, int ..
백준 1377 버블 소트 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 버블 소트를 몇 번이나 해야하는지 출력하는 문제다. 각 원소가 정렬되기 위해 움직여야하는 최대 횟수 + 1을 출력하면 된다. 왜 + 1을 하냐면, 정렬이 끝난 후에도 한번 훑어야 하기 때문이다. import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.StringTo..
백준 11779 최소 거리 구하기2(Java) https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스� www.acmicpc.net 다익스트라 알고리즘을 활용한 문제. 최소 거리를 구하면서 각 노드의 바로 직전 노드를 저장한다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Pair im..
백준 2613 숫자구슬(자바) https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 �� www.acmicpc.net 이분탐색을 활용한 문제다. 뭔가 모든 걸 선택해야 하는 문제같은데, 백트랙킹을 쓰기에는 시간복잡도가 부담스럽다면 이분탐색이 답인 것 같다. import java.io.*; import java.util.StringTokenizer; public class boj2613 { static int N, M, upperBound, lowerBound; static int[] nArr; sta..
백준 2143 두 배열의 합(JAVA) https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 자바는 코드가 너무 길다... 이 코드 길이 볼 때마다 파이썬으로 갈아타고 싶어진다 ㅠㅠ 투 포인터를 활용한 문제 import java.io.*; import java.nio.Buffer; import java.util.ArrayList; import java.util.Collections; import java.util..

티스토리툴바