kwang2134 님의 블로그

[백준] 최소 힙접근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..

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

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

[백준] 프린터 큐접근우선순위 큐정렬큐풀이강의를 안들을 때 틈틈이 백준에서 문제를 풀고 있다. 이제 class 2의 문제를 거의 다 풀었는데 실버 3 티어가 되었다. 실버 내의 저 티어 문제들은 그래도 아직 깊은 생각 없이 바로바로 풀리는 거 같다. 오늘의 문제의 제목은 프린터 큐이다. 제목부터 큐를 사용하라고 나와있다. 중요도가 있고 중요도순으로 출력을 할 경우 원하는 문서가 몇 번째에 나오냐 라는 문제인데 우선순위 큐 한 번 써봐라 하는 문제 같았다. 그렇게 우선순위큐로 제출하자마자 실패가 떴다. 문제를 자세히 보니 주어지는 값은 중요도이고 중요도는 같지만 문서 자체는 다른 것을 고려하지 않았다. 중요도가 낮은 출력물은 맨 뒤에 넣어지게 되고 우선순위 큐만 사용해서는 원하는 출력을 얻을 수가 없었다...

[백준] 수 정렬하기 3접근정렬풀이이 문제는 N개의 입력받는 수를 오름차순으로 정렬하여 출력하는 문제이다. 너무 간단하고 기본적인게 아닌가 했지만 시간 초과가 나는 것을 보고 그렇게 간단한 문제는 아니었구나 해서 문제를 가져왔다. 문제를 보자마자 드는 생각은 그냥 배열이나 리스트에 쭉 받고 정렬하고 그대로 다시 쭉 출력하면 끝 아닌가? 그렇게 간단하게 코드를 작성한 후 바로 시간 초과가 났고 N의 범위는 10,000,000으로 기본 내장된 Arrays.sort나 Collections.sort로는 감당할 수 없는 시간이 요구되었나 보다. 그렇게 찾아 보던 중 입력받는 값의 범위가 정해져 있는 이런 상황에서 사용할 수 있는 카운팅 정렬이라는 것을 발견했다. 카운팅 정렬이란 숫자의 개수를 세어 배열에 저장해 ..

[백준] 부녀회장이 될테야접근DP풀이문제의 설명을 보니 DP입니다라고 말을 하는 거 같았다. 아직 백준에서 어려운 문제를 손댈려면 한참 남은 거 같아서 중간중간 쉬운 문제들도 가져왔다. 문제는 아파트에 거주할려면 밑에 층의 1호부터  자기 호수까지 거주하는 사람 인원 총합계만큼 입주하여야 한다. 그 말은 밑에 층 부터 차근차근 인원수를 더하여 bottom-up 방식으로 채워나가면 될 것이다. 아파트 크기의 배열을 선언해 아파트를 인원수대로 다 채우고 나서 입력받는 호수의 값을 출력하기로 했다.int[][] apart = new int[15][15];for(int i = 1; i 0층부터 14층까지로 크기가 15인 2차원 배열을 선언해 주고 0층의 인원을 초기화해줬다. 문제에서 0호는 존재하지 않음으로 1..