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

[백준] no1916: 최소비용 구하기 - 우선순위큐 다익스트라

문제 Input 첫 번째 줄 : 도시(노드)의 수 N 두 번째 줄 : 버스(간선)의 수 M 세 번째 ~ M+2번째 줄 : 출발지점 도착지점 비용 마지막 줄 : 출발지점A 도착지점B Output A에서 B로가는 최소비용 문제 링크 : https://www.acmicpc.net/problem/1916 원리 1. 노선이 없는 경우(null)를 확인하기위해 Integer[][]사용 private static Integer[][] map; 2. 버스 노선별 비용 입력시, 비용 최소화 if(map[start][end] != null) map[start][end] = Math.min(map[start][end], cost); else map[start][end] = cost; 3. BFS 탐색시, 비용 합산이 적은 ..

[백준] no1918: 후위 표기식

문제 중위 표기식으로 된 연산식을 후위 표기식으로 표현하기 문제 링크 : https://www.acmicpc.net/problem/1918 원리 Stack을 사용 (필자는 메모리 효율을 위해 Deque를 사용하여 작성했습니다.) 1. 연산을 나타내는 수식은 아래와 같이 세 가지로 표현할 수 있다. 1. 전위 표기법(prefix notation) : +ab 2. 중위 표기법 : a+b 3. 후위 표기법(postfix notation) : ab+ 2. 중위 표기식 -> 후위 표기식 변환 방법 1. 피연산자는 바로 출력한다. 2. 연산자는 우선순위를 지정해서 stack에 넣는다. 3. 만약 현재 연산자의 우선순위보다 큰 연산자가 stack의 맨 위에 있다면, 없을때까지 pop한다. 4. )일 경우, (가 나올..

[백준] no26575: Pups - 소수점 변환/0처리

문제 Input 첫 번째 줄 : 테스트 케이스 수 두 번째 줄부터 : 강아지 수, 강아지당 먹이 용량, 먹이용량당 가격 Output 각 테스트 케이스별 $ + (강아지수*용량*비용)의 소수점 둘째자리까지 출력 주의할 점 1. 출력시 맨 앞에 단위인 $ 입력 : 출력시 맨 앞에 $ 붙여서 출력 2. 소수점 둘째자리까지 출력 String.format("%.2f", 곱셈결과값); 3. 입력 중 맨 앞자리가 0인경우는 0이 없이 입력이 들어옴 : 입력시, String의 맨 앞자리가 "."인 경우를 판별하여 붙여줌 private static double checkZero(String input) { if(input.charAt(0)=='.') doubleValue = Double.parseDouble("0" + ..

[백준] no1865:웜홀 - 벨만포드 알고리즘

문제 Input 1번째 줄 : 테스트 케이스의 수 2번째 줄 : 지점(Node)수 도로(Edge)수 웜홀(wormhole)수 3번째 줄 ~ 도로수+웜홀수 : 시작지점 도착지점 비용 1번째 줄을 제외하고 테스트케이스만큼 2~3번 반복 * 단, 도로는 무방향, 웜홀은 단방향 Output YES : 테스트 케이스 내에서, 출발지점에서 다시 출발지점으로 도착했을 때 시간 역행이 가능한 케이스가 있는 경우 NO : 불가능한 경우 문제 링크 : https://www.acmicpc.net/problem/1865 원리 벨만포드 알고리즘 : 음수를 포함한 최단거리 구하는 알고리즘 * 처음 나의 시도 : 비슷한 논리이지만, 이중배열을 이용한 BFS 탐색의 경우 소모되는 메모리가 너무 심하다. 더보기 1. 이중배열을 이용해..

[백준] no1991: 트리 순회 - 전위/중위/후위 순회

문제 I : 트리가 주어진다. O : 트리에 대한 전위/중위/후위 순회를 통해 지나온 노드의 순서를 출력하라. 원리 주어진 트리의 노드는 ABCDEFG이고, 트리의 형태가 다음과 같을 때, 입력 내용을 바탕으로 Node 객체로 되어있는 트리를 만든다. 이후, 전위, 중위, 후위의 순서에 맞게 재귀호출하며 기록하고 출력한다. 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 나의 코드 더보기 import java.io.*; import java.math.BigInteger; import java.util.ArrayLi..