Algorithm & PS/Problem Solving
백준 - 4097. 수익
알고리즘과 자바에 대해 다시 상기시키고 싶어서 다시 PS를 시작하고자 한다. 4097. 수익https://www.acmicpc.net/problem/4097 문제 설명첫째 줄에 N, 둘째 줄부터 N개의 줄엔 수익 P가 주어진다. 범위는 N은 250,000까지, P는 -10,000 ~ 10,000까지이다.다만 테스트 케이스 개수는 정해지지 않아서 O(N)에 구현하는 것을 목표로 고민했다. 접근 1구간에 대해 가장 큰 값을 구하는 것은 어렵지 않았다. 합이 음수가 되는 순간 가장 큰 값이 아니게 되기 때문이다.고민했던 부분은 구간이 비어있으면 안 된다는 조건이다. 반목문을 통해 값을 더해갔는데, 최초 값을 반복문 밖으로 빼서 받을지, 첫 입력인지에 대한 Flag를 둘지 고민했고, 후자로 결정했다. 풀이 코..
백준 - 12100. 2048 (Easy)
구현한 코드가 성능은 좋지 않지만 개인적으로 마음에 들어서 정리하고자 한다. 12100. 2048 (Easy)https://www.acmicpc.net/problem/12100 접근 문제의 형태와 조건(시간제한이 1초, N의 최댓값이 20, 최대 이동 횟수가 5회)을 보고 구현&시뮬레이션이라고 생각하며 풀이를 시작했다. 이런 문제를 풀 때마다 성능이 우선이라고 생각해 코드가 마음에 들지 않아도 적당히만 손보고 넘어갔었다.하지만 이 문제는 성능을 위해 상하좌우 이동 로직을 각각 구현하면 코드가 매우 유사하기에 매우 별로일 것이라고 생각했다. 따라서 이를 해결할 방법을 고민했고 그렇게 떠올린 해결책은 보드를 돌리는 것이다.보드를 회전시키는 동작이 추가로 필요하지만 블록을 한 방향으로만 이동시켜도 문제를 풀..
백준 - 11003. 최솟값 찾기
이런저런 방법으로 접근한 문제라서 정리하고자 한다. 11003. 최솟값 찾기https://www.acmicpc.net/problem/11003 문제 입출력 설명구간을 이동하면서 구간 내의 최솟값을 출력하면 되는 문제이다.문제 자체는 매우 짧고 간단하다. 접근우선 시간제한이 매우 짧고 N의 값이 최대 500만이므로 시간복잡도 O(N)을 떠올렸다. 즉, 값을 입력받을 때 바로 출력해야 한다고 생각했다. 알고리즘은 전체 N개의 값이 주어지고 구간을 이동하며 L개의 값 중 최솟값을 출력하는 문제이므로 슬라이딩 윈도우가 떠올랐다. 하지만 이 알고리즘을 활용하기엔 큰 문제가 있다.바로 최솟값을 다시 찾을 때 L만큼 반복문을 돌아야 한다는 것이다. 이 문제점을 해결하는 것이 이 문제의 목적이라는 것을 질문 게시판..
백준 - 14938. 서강그라운드
반례를 생각하지 못해서 해결하는데 한 시간이 넘는 시간이 걸려 내용을 정리하고자 한다. 14938. 서강그라운드https://www.acmicpc.net/problem/14938 문제 입출력 설명item의 개수와 가중치가 있는 그래프가 주어진다.한 node에서부터 가중치의 합이 r 이내인 node들의 item의 합을 구하는 문제이다. 접근아래 방법으로 풀었다.각 node마다 거리가 r 이하인 node를 visited true로 변경visited가 true인 node의 item 값을 더함자꾸 9%에서 틀려서 오래 고민했다가 해결했다. 우선순위 큐를 활용해 거리가 짧은 node부터 방문하도록 구현했는데 visited를 활용해 한 번 접근한 node는 다시 접근하지 않도록 구현한 것이 문제였다. 그래프의 ..
백준 - 9663. N-Queen
백트래킹 문제 중 완전 기출이기에 적어보고자 한다.9663. N-Queenhttps://www.acmicpc.net/problem/9663 문제 입출력 설명N에 맞게 board를 생성하고 N개의 Queen을 서로 공격하지 않도록 배치하는 경우의 수를 구하면 된다.예를 들어 아래와 같이 배치하면 성공이다. 접근아래와 같이 윗 행부터 조건을 만족하는 곳들을 찾아 배치했다.사실 if문만 잘 구현하면 된다. 나는 이 부분에서 막혀서 구현에 생각보다 오랜 시간이 걸렸다. 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main..
백준 - 18405. 경쟁적 전염
Java언어 중 2등을 달성해 좋아서 작성하는 글이다. 18405. 경쟁적 전염https://www.acmicpc.net/problem/18405 문제 입출력 설명N*N 시험관에 1번부터 바이러스가 놓여있고 숫자가 작은 것부터 상하좌우로 증식한다.S초 후에 (X, Y)에 바이러스가 존재하는지, 그렇다면 어떤 숫자의 바이러스인지를 출력해야 한다. 접근N(시험관 크기), K(바이러스 개수), S(흐른 시간) 값의 범위는 아래와 같다.N의 범위: 1 ~ 200K의 범위: 1 ~ 1,000S의 범위: 0 ~ 10,000모두 범위가 작기에 문제가 원하는 방법은 BFS를 활용하는 것이라고 생각했다.다만, 입력에서 S, X, Y의 값이 모두 주어지므로 BFS를 활용하지 않는 방법으로 접근했다. 과정은 아래와 ..
백준 - 2096. 내려가기
가장 일반적인 DP 문제라고 생각해서 정리해보고자 한다. 2096. 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 입출력 설명 첫째 줄에 N의 크기가 주어지고 이후 N개의 줄에 0 ~ 9까지의 숫자가 3개씩 주어진다. 예제 입력의 경우 배열의 모습은 아래와 같다. 우리는 규칙에 맞게 첫째 줄부터 아래로 내려가면서 얻을 수 있는 최소 점수와 최대 점수를 구해야 한다. (규칙: 다음 줄로 내려갈 때에는 바로 아래 수 or 아래 수와 붙어 있는 수로만 ..
백준 - 12865. 평범한 배낭
사람들이 흔히 말하는 Knapsack 문제이다. 이 문제를 오랜 기간 풀지 못했는데 해결하기까지의 시행착오를 정리하고자 한다. 12865. 평범한 배낭 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 입출력 설명 첫 줄에 물품의 수(N)와 배낭 무게(K)가 주어진다. 이후 각 물건의 무게(W)와 가치(V)가 주어진다. 배낭이 버틸 수 있는 무게(K) 내에서 가장 가치(V)가 높게..