kwang2134 님의 블로그

[백준] 마인크래프트접근브루트 포스 (Brute Force)풀이땅을 가장 높게 평탄화시키는 데 걸리는 시간과 땅의 높이를 구하는 문제이다. 블록을 쌓고 제거하여 모든 블록을 같은 높이로 만드는 데 걸리는 시간을 구해야 하는데 문제의 조건중 답이 여러 개 라면 가장 높은 높이를 출력하라는 부분이 있다.그 말은 블록의 높이가 다양하게 있을 때 땅을 모두 8의 높이로 평탄화할 때와 10의 높이로 평탄화할 때 걸리는 시간이 같을 수 있다는 소리다. 그렇다면 완전 탐색을 통해 모든 경우의 수를 구한 뒤 작업 시간이 최소이고 땅의 높이가 최대인 경우를 찾아야 한다. 일단 기본적으로 입력 값들을 받아 현재 땅의 최소 높이와 최대 높이를 구해줘야 한다. 그리고 최소 높이 부터 최대 높이까지 높이마다 반복을 진행하며 평..

[백준] 최소 힙접근PriorityQueue (우선순위큐)풀이이번 문제는 힙을 다루는 문제로 최소 힙의 연산을 출력하는 문제이다. 실버 상위 단계부터는 알고리즘을 사용한 구현 문제들이 나오기 시작하는 거 같다. 이 문제도 구현 자체의 난이도는 매우 쉬운 편이나 힙이라는 자료구조를 구현해 봐라 하는 의미에서 실버에 있는 것 같다. 힙 (Heap)에 대한 내용부터 알고 들어가야 할 것 같다. 힙 (Heap)이란 특정한 구조적 속성을 가진 완전 이진트리(Complete Binary Tree)이다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 2개의 자식 노드로 채워져 있고 마지막 레벨은 가능한 왼쪽부터 채워지는 특징을 가지고 있다. 루트 노드를 기준으로 루트 노드가 가장 큰 값을 가지는 최대 힙 속성과..

[백준] 잃어버린 괄호 접근dfs그리디풀이수식을 입력받아 괄호를 적절히 추가해 최솟값을 만드는 문제이다. 처음에 문제를 읽고 접근을 잘못된 방향으로 해버려 통째로 갈아엎고 다시 풀었던 문제이다. 이전에 dfs와 bfs문제를 풀며 남은 코드를 활용하고자 모든 경우의 수 중 최솟값을 구하는 방식으로 진행했다. 우선 잘못 풀었던 방법은 일단 수식을 +와 -, 연산자가 나올 때 마다 문자열을 잘라주었다. 그리고 만들어진 문자열을 가지고 정수로 변환하는데 숫자 앞에 나온 연산자가 +라면 양수로 -라면 음수로 만들어 버렸다. 즉 55-50+40이라는 수식이 있을 경우 {"55", "-", "50", "+", "40"}으로 잘라준 뒤 {55, -50, 40}이라는 배열로 만들었다. 이 배열을 가지고 인덱스가 2이상 ..

DFS와 BFS접근dfsbfs풀이이름에 나와 있는 것처럼 DFS와 BFS를 구현해 보는 문제이다. 정점과 간선의 정보가 주어지고 DFS와 BFS로 탐색되는 순서를 출력하는 문제이다. 우선 정점의 정보를 담을 클래스를 선언한다.private static class Vertex{ private final int index; private final List connectedVertexes; public Vertex(int index) { this.index = index; connectedVertexes = new ArrayList(); } }정점은 자신의 번호와 연결된 정점들의 정보를 가진다.List vertex..

[백준] Four Squares접근DP풀이다시 돌아온 백준 문제다. 이번 문제는 입력받은 숫자를 제곱수의 합으로 표현하되 가장 짧은 표현식에 사용되는 숫자가 몇 개인지 물어보는 문제다. 입력받은 수를 N이라고 할 때 계속 N의 제곱근을 구하여 제곱만큼 N에서 빼주는 방법을 0까지 반복하여도 수식은 얻어지지만 1자리 수에서 1의 제곱이 여러 번 나오는 등 최솟값이 아닌 경우들이 있다.  예를 들어 N=11339인 경우 문제의 만족하는 정답은 1052 x 172 x 52 지만 위의 방식으로 구현할 경우 1062 x 102 x 12 x 12 x 12 으로 더 많은 연산을 소요하게 된다. 그렇기 때문에 또 DP를 사용해 구현해 주어야 한다.int[] dp = new int[n + 1];Arrays.fill(dp..

[백준] 구간 합 구하기 411659번: 구간 합 구하기 4 (acmicpc.net)접근누적합풀이문제만 봐선 브론즈 정도의 문제가 왜 실버에 있는가 했다.Scanner 말고 BufferedReader를 사용하라고 해둔 문제인가 싶어 BufferedReader와 BufferedWriter로 풀어봤다. 입력받은 값들을 배열에 넣고 반복문을 돌려 합을 구했더니 시간초과가 났다.그래서 수가 많아지면 배열 접근에 시간이 많이 드는가 싶어 map에 넣어 돌려봤지만 또 시간 초과가 났다.직접 합을 계산하라는 문제가 아닌 거 같았다. 그렇다 이 문제는 누적합을 이용하라는 문제였던 것이다.누적합은 주로 구간합이나 부분합을 계산하는 데 사용된다. 누적합을 사용하지 않을 경우 시간 복잡도는 테스트 케이스의 수인 M번의 반복..

[백준] 파도반 수열접근수학적 귀납법풀이삼각형이 시계 방향으로 나선형을 그리며 변의 길이들이 합쳐져 큰 삼각형이 되는 문제이다. 대체적으로 이런 도형 문제들은 거의 코딩 문제를 푼다기보다 수학 문제를 푸는 느낌이다. 이번 문제도 수학적 귀납법을 사용해 사실상 수학 문제를 풀고 수식을 출력할 코드만 작성해 주면 된다. 문제를 해결하기 위해서는 수열을 보고 규칙을 찾아야 한다. 우선 어느정도 일정하게 늘어가는 구간을 찾아야 한다. 그림을 봤을 땐 한 변의 길이가 3인 삼각형부터 다른 두 삼각형의 변 길이를 더하며 진행되는 걸 볼 수 있다. 그렇다면 변 길이가 3인 삼각형보다 앞에 있는 삼각형들의 기본 값들을 구해보자 i가 1,2,3일 경우 모두 한 변의 길이가 1이다. i가 4,5일 경우 한 변의 길이가 2..

[백준] 1로 만들기1463번: 1로 만들기 (acmicpc.net)접근dp풀이주어진 수를 1로 만드는데 필요한 최소 연산수를 구하는 문제다.적용 가능한 연산은 3가지이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.위의 3가지 연산을 잘 조합해서 최소한의 횟수로 주어진 숫자를 1로 만들어야 한다. 단순하게 생각한다면 3으로 나누는 게 2로 나누는 거보다 숫자를 더 크게 줄일 수 있으니 순서대로 조건문을 설정하고 주어진 수가 1이 될 때까지 반복문을 돌리면 될 거 같아 보인다.//1차원적인 방식 -> 잘못된 접근while(n != 1){ if(n % 3 == 0){ n /= 3; } else if(n % 2 == 0){ n..

[백준] 피보나치 함수접근dp(메모이제이션)풀이피보나치 함수의 0과 1이 반환되는 횟수를 구하는 문제이다. 문제에 나와있는 코드를 그대로 들고 가 count 변수를 할당해 직접 세어준다면 바로 시간초과가 나게 된다. 시간초과가 나지 않을려면 재귀나 탐색에서 사용되는 메모이제이션을 사용하여야 한다. 메모이제이션은 DP(Dynamic Programming) 동적 프로그래밍의 한 기법으로 이미 계산한 결과를 저장해 두고 다시 필요할 때 값을 꺼내어 재사용하는 기법이다.private static final int MAX = 40;private static final int[] countZero = new int[MAX + 1];private static final int[] countOne = new int[M..

[백준] 스택 수열1874번: 스택 수열 (acmicpc.net)접근스택풀이문제의 제목에부터 스택이 들어가는 스택 문제이다. 도대체 백준에 문제 설명들은 왜 다 이런 모양인지 이해가 가질 않는다. 저 설명을 보고 이해해서 문제를 풀려면 출제자쯤 돼야 하지 않나 싶다. 문제를 읽어봐도 이해는 가지 않고 내가 아는 수열이 아닌 건가 싶고 예시 케이스를 봐도 뭔 짓을 한 건지 도저히 이해가 가질 않아서 질문 게시판을 찾아봤다. 질문 게시판에서 누군가 유튜브에 해당 문제 해설을 올려둔 걸 보고 나서야 문제를 이해했다. 해설을 보고 나니 그걸 이해한 사람도 신기하고 문제가 저건데 설명을 이렇게 올린 사람도 참 신기했다. 문제는 주어지는 입력을 스택을 가지고 처리할 수 있는지 없는지를 구하는 문제이다. 예제 입력인..