공부공간

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전이 무수히 많고, A(i) 번째는 A(i-1) 번째의 배수이므로 그리디가 성립한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public clas..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 해쉬맵에 다 떄려넣고 GET으로 M개만큼 불러오자 출력에 시간이 걸리므로, 모아서 출력하자. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWri..

https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 6,9는 번갈아 사용할 수있으므로, 9의 개수를 6에 더해준다. 그리고 만약 6이 최대개수를 가진다면, 세트의 수는 홀수인경우 나누기 2 + 1이고 짝수인경우 나누기 2이다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 큐브의 시뮬레이션을 위해서 모든 경우의수에 대해서 색과 방향을 고려해 코딩해준다. 맨 윗면이 시계방향으로 돌았을 경우, 옆면의 제일 윗면도 같이 돌아감에 유의하여 구현한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public s..

https://www.acmicpc.net/problem/12846 12846번: 무서운 아르바이트 성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다. 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다. 돈은 당일에 주지 않고 퇴직을 할 때 한 www.acmicpc.net 연속한 수열에서 가장 최솟값을 기준으로 얻을 수 있는 총합의 가장 큰 값을 고르는 문제이다. 문제상황을 잘 읽어보면, https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,00..

https://www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 길이가 N인 수열에서, 내가 현재있는 index 에서 [index-(M-1) , index+(M-1)] 에서 가장 큰 값을 찾으면 된다. N = 100만 이므로, N^2의 풀이보다는 NlogN의 풀이인 세그먼트 트리를 이용하여, N개의 쿼리를 처리해주자, 위문제는 O(NlogN+N) 에 처리가 가능하다. 즉, 구간의 최댓값을 저장하는 배열을 세그먼트 트리로 만들면 된다. i..

https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위� www.acmicpc.net 주말동안의 PS주제는 포드-풀커슨알고리즘과 이분 매칭이였다. https://coderkoo.tistory.com/4 네트워크플로우(Network flow) - 포드 풀커슨(Ford-Fulkerson) 알고리즘 네트워크 플로우란(Network flow)? 그래프의 경로의 길이가 아닌, ‘용량’의 관점에서 바라보는 시점. Ex) 인터넷으로 영화를 다운받고 있는데 파일 원격지에서 얼마나..