백준26 [Java]백준 16194번 :: 카드 구매하기 2 백준 온라인 저지 16194번 - 카드 구매하기2 Java 알고리즘 문제풀이 풀이 DP(다이나믹 프로그래밍) 문제입니다. 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테스트에 자주 출제되는 문항이다. 문제를 해석해보면 카드 N개를 구매해야한다. 카드팩에 들어있는 카드가 적은 것부터 산다. 카드 N개를 구매하는데 드는 비용의 최소를 구하는 문제이다. DP를 풀때 일반항 형태로 정의하는 것이 중요하다. 일단, 케이스 단위로 생각해보자. 카드 i개를 구매하는 방법은? 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다. 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다. 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다. ... 일반화 시키면 D.. 2019. 3. 13. [Java]백준 11052번 :: 카드 구매하기 백준 온라인 저지 11052번 - 카드 구매하기 Java 알고리즘 문제풀이 풀이 DP(다이나믹 프로그래밍) 문제입니다. 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테스트에 자주 출제되는 문항이다. 문제를 해석해보면 카드 N개를 구매해야한다. 카드팩에 들어있는 카드가 적은 것부터 산다. 카드 N개를 구매하는데 드는 비용의 최대를 구하는 문제이다. DP를 풀때 일반항 형태로 정의하는 것이 중요하다. 일단, 케이스 단위로 생각해보자. 카드 i개를 구매하는 방법은? 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다. 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다. 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다. ... 일반화 시키면 D[.. 2019. 3. 13. [Java]백준 7569번 :: 토마토 백준 온라인 저지 7569번 - 토마토 Java 알고리즘 문제풀이 풀이 BFS(너비 우선 탐색) 문제입니다. BFS를 이용해 해결하는 문제는 3가지 조건을 가지고 있다. 1. 최소 비용 문제 2. 간선의 가중치가 1이다. 3. 정점과 간선의 개수가 적다. (시간제한, 메모리 제한 내에 만족한다.) DFS, BFS 관련 자료 : https://developer-mac.tistory.com/64 토마토 문제에서는 BFS를 이용하면 된다. 익은 토마토를 큐에 담아 좌, 우, 위, 아래 총 4가지 경로를 탐색해주면된다. 이때 익은 토마토 기준으로 다른 칸으로 갈때 (안익은 토마토 0이 있을 때만, 비어 있는 공간 -1일 때는 제외한다.) 그리고 3차원 배열을 사용했기 때문에 이전 토마토 문제보다 신경써줘야 할 .. 2019. 3. 12. [Java]백준 7576번 :: 토마토 백준 온라인 저지 7576번 - 토마토 Java 알고리즘 문제풀이 풀이 BFS(너비 우선 탐색) 문제입니다. BFS를 이용해 해결하는 문제는 3가지 조건을 가지고 있다. 1. 최소 비용 문제 2. 간선의 가중치가 1이다. 3. 정점과 간선의 개수가 적다. (시간제한, 메모리 제한 내에 만족한다.) DFS, BFS 관련 자료 : https://developer-mac.tistory.com/64 토마토 문제에서는 BFS를 이용하면 된다. 익은 토마토를 큐에 담아 좌, 우, 위, 아래 총 4가지 경로를 탐색해주면된다. 이때 익은 토마토 기준으로 다른 칸으로 갈때 (안익은 토마토 0이 있을 때만, 비어 있는 공간 -1일 때는 제외한다.) 이전 값에서 +1을 해주면서 전체를 탐색하면 된다. import java... 2019. 3. 12. [Java]백준 4963번 :: 섬의 개수 백준 온라인 저지 4963번 - 섬의 개수 Java 알고리즘 문제풀이 코딩테스트 DFS, BFS : https://developer-mac.tistory.com/64 풀이 그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다. DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다. 실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다. DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 첫 번째로 스택을 이용하는 것 두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. BFS 알고리즘은 Queue를 .. 2019. 3. 11. [Java]백준 1463번 :: 1로 만들기 백준 온라인 저지 1463번 - 1로 만들기 Java 알고리즘 문제풀이 풀이 다이나믹 프로그래밍(DP) 문제이다. 간략하게 DP를 소개하자면 큰 문제를 작은 단위로 쪼갠 작은 문제로 큰 문제의 답을 구하는 것을 뜻한다. 푸는 방식에는 2가지가 존재한다. 이 문제도 2가지 방법으로 풀어볼 것이다. 1. Top-Down 2. Bottom-Up 먼저, Top-down은 용어 그대로 위에서부터 아래로 이어지는 것이다. 이 방법에 특징은 재귀함수를 사용하는 것이다. 작은 부분의 답을 저장해 이미 계산을 진행한 작은문제는 저장된 값을 이용하는 방법이다. /* Top down */ import java.util.Scanner; public class Beak1463 { static int[] d; public sta.. 2019. 3. 10. 이전 1 2 3 4 5 다음