봄봄.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://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 📖 문제 풀이 - DFS에서는 점화식과 종료조건을 찾는 것이 가장 중요하다. 📖 소스 코드 public class 타겟넘버 { public static void main(String[] args) { int[] numbers = {1,1,1,1}; int target = 3; System.out.println..

https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 🎈 문제 풀이 - DFS를 활용하면 되는 문제였다. - 다른 문제와 다르게 했던 점은 다음 인접 정점을 탐색하기 위해서는 계속 "같은 색상의 값"이어야 했기 때문에 dfs 파라미터로 처음 dfs 탐색을 시작할 때 가지고 있던 색상 값을 받아서 현재 탐색 중인 정점과 비교했다. - 한 번 dfs를 돌 때 마다 numberOfArea를 1씩 추가하고 - dfs 호출을 ..

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(큐)에 익은 토마토들을 먼저 넣고 하나씩 차례대로 빼서 익은 토마토로 바꾸고 최소 날짜를 더해준다. 예를 들어, 익은 토마토가 박스에 ..