봄봄.devlog

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net ✍ 문제 풀이 - 문제에서 정점은 물론 간선도 여러 번 이동할 수 있다고 하였다. - 단, 특정 정점 2개를 반드시 거쳐야 한다고 명시하였다. - 어떻게 생각하면 될까? - 원래 거쳐야 하는 정점이 없다면, 1부터 N까지 다익스트라 1번만 실행하면 된다. - But, 거쳐야 하는 정점이 있다면 쪼개서 다익스트라를 하면 된다. 1 -> v1 -> v2 -> N 1 ->..

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net ✍ 문제 풀이 minHeap과 maxHeap 우선순위큐를 만들고 값을 추가로 입력받을 때마다 조건에 맞게 큐에 담아서 가운데 값을 찾는다. ✍ 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; // List에 담는..

www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 📌동적 프로그래밍(Dynamic Programming) - dp 문제는 이전의 구한 값을 통해 현재 원하는 값을 도출하는 방식 - 중복하는 값이 있다면 제외하고 풀면 된다. - 만들고 싶은 value(=여기선 금액)을 기준으로 한다. 📌문제 풀이 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. dp[] 배열을 선언한다. dp[i] = j 라고 하면, i = 금액 j = i원을 만드는데 가능한 경우..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net 🎈 기억 할 것 (주소값 비교(==)와 값비교(equals)) == 연산자는 비교하고자 하는 두개의 대상의 주소값을 비교 equals 메소드는 비교하고자 하는 두개의 대상의 값 자체를 비교 int, char형은 Call by Value의 형태로 기본적으로 대상에 주소값을 가지지 않는 형태로 사용. But String은 클래스이기에 기본적으로 Call by Reference 형태로 생성 시 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 🎈 문제 풀이 - 모든 정점을 돌 수 있는 반복문을 우선적으로 만들고, - '1'을 만날 때 dfs함수를 호출하고, 각 단지내 집의 수를 count할 수 있도록 한다. - dfs 함수에서 돌아왔을 때 총 단지 수는 +1이 된다. 각 단지내 집의 수를 count할 수 있는 방법을 2가지로 생각해봤다. 1) return 값이 있는 DFS static int dfs(int r, int c) { // 종..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 🎈 문제 풀이 - 박스를 순회하면서 익은 토마토(= 1)을 Queue(큐)에 담는다. - 익은 토마토(= 1)가 동시다발적으로 주위 안익은 토마토(= 0)에 영향을 줘야하기 때문에 일반 BFS방법처럼 일정한 시작점에서 시작할 수 없다. Queue(큐)에 익은 토마토들을 먼저 넣고 하나씩 차례대로 빼서 익은 토마토로 바꾸고 최소 날짜를 더해준다. 예를 들어, 익은 토마토가 박스에 ..

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 🎈 문제 풀이 현실 세계의 동전과 지폐의 가치는 작은 금액의 지폐의 몇 배수이다. 이 조건이 주어진 경우에, K 금액을 만족하는 동전의 최소수를 계산할 때 큰 동전부터 사용해야 한다. 예) 5만원, 1만원, 5천원, 1천원, 500원, 100원 165200원 = 5만원 + 5만원 + 1만원 + 5천원 + 100원 + 100원 모든 경..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료�� www.acmicpc.net 🎈 My 문제 풀이 문서도의 '중요도'를 확인. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있으면 뒤로 보낸다. 그렇지 않으면 바로 인쇄. 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것. - 각 문서의 인덱스와 중요도 값을 저장할 수 있는 Document 클래스를 만들고, 중요도를 저장할 수 있는 ArrayList 배열을 따로 만들어서 관리했다. - 그리고 나서 중요도 Ar..