알고리즘 저장소 (일반방식과 나만의 풀이)

[백준] no11943: 파일 옮기기

문제 * 두 개의 바구니에 각각 사과와 오렌지가 다른 개수로 주어진다. * 한 바구니에 한 가지의 과일만 있도록 옮기는 최소값을 구해라 * 단, 한번에 한개의 과일만 옮길 수 있다. 문제 링크 : https://www.acmicpc.net/problem/11943 원리 * 결국 A바구니의 사과를 옮기면, B바구니의 오렌지를 옮길 수 밖에 없다. * 따라서, a1, o1, a2, o2가 있다고 할 때, * a1 + o2 혹은 a2 + o1 만큼 옮겨야 한다. * 즉, 둘 중 더 적은 합만큼이 정답 나의 코드 1. 조건문으로 Math 함수 없이 풀기 시도 [일부실패] 더보기 import java.io.*; import java.util.StringTokenizer; public class no11943 { ..

[백준] no11660: 구간 합 구하기5

문제 /** * 주어진 N * N 사이즈의 매트릭스에서 * x1, y1 ~ x2, y2에 해당하는 숫자의 합을 구하시오 */ 문제 링크 : https://www.acmicpc.net/problem/11660 원리 * 1. DP * 2. 누적 합 풀이방법 1. 누적 합 중, 2차원 배열을 이용한 이중반복을 피하기 위한 방법 (예시) : 매트릭스(이중배열)로 되어있는 수를 1차원 배열에 나열 한 뒤, 각 숫자는 N으로 나눈 나머지의 비교를 이용한 조건문으로 대체가 가능하다. 더보기 private static void calculate () { DP = new int[N*N+1]; int num = (N*(y1-1))+x1; int finish = (N*(y2-1))+x2; int last = 0; while..

[백준] no12865: 평범한 배낭 - DP

문제 /** * N가지의 물건이 주어진다. (1

[백준] no1504: 특정한 최단 경로 - 다익스트라

문제 /** * 문제 : 1번에서 N번으로 가능 경로 중 주어진 두 정점을 지나는 경로 중 최단거리를 구하기 * 조건1 : 한번 지났던 경로를 재방문 가능(중복 node, 중복 edge) * 조건2 : '출발지점, 도착지점, 사이의 거리'가 순차적으로 주어짐 */ * 1. 이 문제는 문제를 똑바로 안읽어서 헤멘 문제다. 고로 문제를 똑바로 읽자라는 경각심을 또다시 일으킨 문제. + 근무중 VS code로 문제풀이 진행 (듀얼 모니터와 intelliJ가 그립다.) * 2. 레퍼런스 코드를 통해, 다익스트라의 응용과 메모리 향상을 위한 Java 내 기능 활용을 되짚어 볼 수 있는 문제. 원리 다익스트라를 이용한 탐색문제이다. 풀이방법 나의 코드 1차 시도 : 임의의 정점에서 시작할 수 있고, A와 B만 지나..

[백준] no12851: 숨바꼭질 2 - BFS(중복 일부 허용)

문제 * X : 현재 숫자 * K : 목표 숫자 * 조건 : X-1 또는 X+1 또는 X*2 가능 * 출력 : 최소 도달 cnt와 최소 도달 방법 수 문제 링크 : https://www.acmicpc.net/problem/12851 원리 이 문제는 BFS의 중복을 일부 혀용해 주는 경우가 핵심 즉, 기본적으로 중복 방문은 허용하지 않되, 중간 루트에 같은 시간을 소요해서 같은 위치에 도착한 경우의 중복은 허용 풀이방법 * 1. BFS로 최소 도달 시간을 구함 * 2. 최소 도달 시간과 같은 시간에 도달하는 경우를 cnt 나의 코드 1. [실패] 첫 시도 : BFS로 최소시간 구하기는 성공. 최소 경로 개수 count 실패. : Recur부분에서 무한 루프에 빠짐 더보기 private static int ..