코딩 테스트/백준

[백준][Gold2]10473 - 인간 대포 - JAVA

[문제] https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net [풀이] * 알고리즘 : 다익스트라 알고리즘(https://programmer-chocho.tistory.com/63) 1. 출발지와 도착지가 존재하기 때문에(a -> b) 최단 경로 알고리즘을 응용하는 문제다. 최초에 그래프를 어떻게 만들것이냐가 관건이다. 만들어진 그래프가 있어야 최단 경로를 구한든 말든 할 것이기 때문에;; 2. 최단 경로를 구하는 그래프를 만들려면 가중치가 ..

[백준][Sliver1]1932 - 정수 삼각형 - JAVA

[문제] https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net [풀이] * 알고리즘: 다이나믹 프로그래밍 다이나믹 프로그래밍을 이용하여 푸는 문제이다. 점화식은 쉽게 세울수 있다. 그런데 인덱스를 이용한 삼각형 배열을 만드는 것이 어려웠다. 어려웠던 이유는 1차원 배열로 삼각형을 만드려했기 때문이었다. 2차원 배열로 삼각형을 만드니 쉽게 다이나믹프로그래밍을 이용하여 문제를 풀 수 있었다. 바텀업 방식으로 풀면되는데 현재 위치에서 위로 왼쪽 대각선, 오른쪽 대각선에 있는 수 중 큰 수를 현재값과 더해주면 된다. 그런데 삼각..

[백준][Gold5]1107 - 리모컨 -JAVA

[문제] https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net [풀이] - 알고리즘 분류 부르트포스 알고리즘 정리를 하면 원하는 채널로 이동하는 방법은 2가지가 있다. 1. +,- 로만 이동하는 방법 2. 가장 근접한 채널까지 이동후, 나머지는 +,-로 이동하는 방법 처음에 1번 방법은 생각을 못했다. 그런데 만약 이동하려는 채널이 102번일 때 고장난 버튼 없다고 해서 102 세자리 수를 누르는 것보다 +를 2번 누르는 것이 더 클..

[백준][Gold5] 12865 - 평범한 배낭 - JAVA

[문제] https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 처음에 완전탐색으로 풀었는데 시간초과가 떴다. 찾아보니 배낭문제(knapsack problem)는 dp를 응용하는 아주 유명한 문제라고 한다. dp, 즉 메모이제이션을 이용하기 위해서는 값을 저장할 테이블을 정의해야 한다. 다음과 같은 이차원 배열을 정의하겠다. dp[i][j] = value - i : 1 ~ i 까지의 아..

[백준][gold5] 9251번: LCS - JAVA

[문제] www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 대학교 알고리즘 수업때 들었지만 기억이 가물가물했다. 아래 유튜브를 보면서 다시 공부했다. www.youtube.com/watch?v=EAXDUxVYquY [코드] package com.algorithm.baekjoon.gold5; import java.io.*; /** * 9251 - LCS */ public class Test04 { public stat..

[백준][gold5] 14502번: 연구소 - JAVA

[문제] www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [풀이 내용] * 알고리즘 분류 - 부르트포스 알고리즘 - 너비 우선 탐색 0으로 표시된 빈칸들 중에 3곳을 골라 벽을 세워야 한다. 어떻게 3곳을 골라야 가장 안전 영역을 많이 확보할 수 있는지 모르므로 경우의 수를 모두 해봐야 한다. 그 다음 각 경우마다 바이러스가 퍼질 수 없는 안전 영역의 크기를 구하고 그 중 최댓값을 출력한다. 1. 연구소 2차원 배열에서 0으로 표시된 칸들 중에 3가지를 선택하는 경우의 ..