[백준,BOJ 11004] k번째 수( JAVA 구현)

-내 생각 우선 이 문제를 보면, 단순하게 자바에서 제공하는 Arrays.sort()를 이용하여 정렬 후 k번 째 수를 출력하면 되는 간단한 문제라고 생각했다. 그러나 결과는 시간 초과가 발생하였고, 입력 값의 수가 많기 때문에 BuffredReader 클래스를 사용하여서 StringTokenizer을 통해 공백을 구분하여 입력받아 제출해보았지만, 역시 시간 초과가 발생하였다. 그래서 검색을 통해 찾아보았더니 이러한 N개의 수에서 K번 째 수를 반환하는 경우에 사용되는 특정한 알고리즘인 Quick Selection이라는 알고리즘이 존재한다는 사실을 알 수 있었고, 해당 알고리즘은 Quick sort방식을 응용한 방식이라는 점을 알게 되어서, 우선 Quick sort문제를 풀면서 공부하기로 한 이후 미루어..

→2019.12.06

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2751] 수 정렬하기 2( JAVA 구현)

-내 생각 우선 이 문제를 풀게 된 계기는 11004번 문제인 k번째 수 문제를 풀려고 했는데, 이러한 방식은 Quick Selection이라는 별도의 알고리즘을 사용한다고 해서 찾아보니, 해당 알고리즘은 기존의 퀵 정렬 알고리즘을 활용한 방식이라고 하여서 퀵 정렬 알고리즘을 우선적으로 공부해보고자 해서 풀게 되었다. 이전에 동영상 강의를 보면서 병합 정렬을 사용해서 풀었던 문제였는데, 한 달이라는 시간이 지나서 기억이 나지 않아서 우선 퀵 정렬을 이용해 풀어보기로 했다. 그러나 혼자 힘으로 구현해보려 했지만 잘 되지 않아서 마이구미님의 블로그를 참고하게 되었다. 아래에 설명이 자세히 나와있다. https://mygumi.tistory.com/308 퀵소트 알고리즘 :: 마이구미 이 글은 정렬 중 퀵소트..

→2019.12.06

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11652] 카드( JAVA 구현)

-내 생각 이 문제의 경우 처음 봤을 때, 주어질 수 있는 정수의 범위만큼 별도의 배열을 생성하여서 해당 정수 값을 인덱스로 하여서 해당 정수를 만날 때마다 해당 인덱스 값을 증가시키는 방법을 생각했었는데, 문제를 보면 데이터의 범위가 +-2^62로 굉장히 크기 때문에 이러한 방식을 사용하면 메모리 낭비가 심하고 데이터의 탐색 역시 오래 걸릴 것 같아 사용하지 않았다. -해법 위에서 언급한 문제점을 해결하기 위해서 우선 값을 입력받는 배열을 생성해 값을 입력받은 후 오름차순 또는 내림차순 정렬을 통해 같은 숫자를 연속하게 놓이게 만들었다. 이후 n-2까지 탐색을 통해 다음 원소와 비교하여 값이 달라질 경우 카운트 변수를 초기화하여 최대 카운트 수를 가지는 정수를 찾은 후 출력하려고 했다. 그러나 문제 제..

→2019.12.05

코테/백준 온라인 저지(BOJ)

[백준,BOJ 10825] 국영수( JAVA 구현)

-내 생각 일단 문제 자체의 이해는 쉽고, 무엇을 사용해야 할지 알 수 있었다. 일반적으로 정렬 문제의 경우 특별한 경우가 아니면 Comparator클래스에서 compare 메서드를 오버 라이딩해서 풀거나 클래스로 만들어 Comparable클래스로 compareTo메서드를 오버 라이딩해서 풀어야 하는데, 한 동안 DFS, BFS, DP 문제만 풀다 보니까 리턴 값이 헷갈려서 약간 막힌 부분이 있었다. -해법 String의 compareTo와 Integer.compare은 왼쪽에 오는 것이 더 작으면 -1(0)을 반환한다. 같으면 0을 반환한다. Comparator의 compare메소드의 경우 두 인자 중, 첫 번째 인자가 다음에 오는 요소(a), 두 번째 인자가 기준이 되는 요소(b)라 할 때, a와 b..

→2019.12.04

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11052] 카드 구매하기( JAVA 구현)

-내 생각 이 문제의 경우 문제 지문이 상당히 길기 때문에 자칫 어렵게 보일 수 있는데, 그렇게 어려운 문제는 아니라고 생각한다. 문제의 요점을 잘 읽어보면 카드의 개수와 1 ~ n개의 카드팩으로 이루어진 가격 p1 ~ pn이 주어질 때 카드 개수를 살 수 있는 최댓값을 구하는 것이 문제의 요지이다. 즉, 예제 입력 1의 경우 4개의 카드를 사고자 할 때, 카드 1개로 이루어진 p1의 가격, 카드 2개로 이루어진 p2의 가격, 3개로 이루어진 p3의 가격 4개로 이루어진 p4의 가격이 주어지고, 어떤 카드팩을 골라야 최대 비용으로 구매할 수 있는지 묻는 것이다. 처음 접근은 역시 dp테이블을 만든 후 각 경우의 수를 따져보는 것이었다. 즉 카드를 4장 구매하고 싶다고 할 때, 각 가격별로 카드를 1장 살..

→2019.12.04

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2011] 암호코드( JAVA 구현)

-내 생각 처음 문제를 풀 때, dp테이블을 그려보려 했는데 감이 잡히질 않았고, 어떻게 풀어야 할지 감이 잡히지 않아 여러 방법으로 시도해보았는데 풀리지 않았다. 특정 예시를 들어서 테이블을 그려야 했었는데, 처음에 그릴 때, 입력값인 암호가 1일 경우 A, 2일 경우 B,... 11일 경우 AA, K.. 같은 방식으로 생각해서 접근이 불가능했었다. -해법 이 문제의 경우 푸는 방식이 다른 DP들과 별로 다르지 않았다. 우선 입력 예제 25114로 예시를 들면, DP에서 많이 썼던, 각 글자를 마지막 숫자로 보는 방식이다. 즉 2부터 2가 마지막으로 오는 경우의 수를 구하고, 다음 5가 마지막으로 오는 경우의 수를 구하고 와 같은 방식이다. 그러나 이 문제에서는 주의해야 할 점이, 1부터 26까지의 숫..

→2019.12.04

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2225] 합분해( JAVA 구현)

-내 생각 처음 문제를 접했을 때는 어떻게 접근해야 할지 감이 잡히지 않았다. 그러나 조금 생각해 봤더니 어느 정도 길이 보였다. 처음 접근한 방법은 각 경우의 수를 따져보는 것이었는데, 이 문제의 경우는 자리 수가 고정되어 있는 것이 아닌, 입력값에 따라 자릿수가 달라지기 때문에 각 자릿수에 따라 경우의 수를 따져야 될 것 같았다. 예를들어 예제 입력의 경우 자리 수가 2자리 이기 때문에, 자리 수가 1인 경우를 따진 후 자리 수가 한 자리 늘어났을 때 이전 자리 수의 경우의 수를 활용하는 방식으로 표를 완성할 수 있었다. -해법 위의 방식으로 접근해보아야겠다는 생각을 한 후 경우를 따져 보았다. 우선 n이 4이고 k가 3일 때를 아래의 표를 보면서 따져보자. 첫 번째로 자리 수가 한 개일 경우는 n보..

→2019.12.02

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2133] 타일 채우기( JAVA 구현)

-내 생각 및 해법 이 문제 역시 타일 채우기 문제로, 예전에 유튜브 강의를 통해 접해 봤던 문제였다. 각 n의 경우에 따라서 타일의 모양을 그려보면 2x1, 1x2크기의 타일밖에 존재하지 않기 때문에 3xN크기의 타일을 채울 때, n이 1, 3, 5... 등 홀수의 경우에는 채울 수 없다는 것을 알 수 있다. 또한 n이 2일 때는 3개, 4일 때는 2의 경우의 수에서 새로운 모양 2가지가 등장해 총 11가지의 수가 등장한다. 이러한 새로운 모양은 n이 짝수로 증가할 때마다 2가지씩 새로운 모양이 등장하기 때문에 점화식을 세워보면, dp [n] = dp [n-2] * 3 + dp [n-4] *2 + dp [n-6] * 2.... 식으로 증가하게 된다. 이 때 주의하지 못했던 점이 있는데 바로 n이 0일 ..

→2019.12.02

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1699] 제곱수의 합( JAVA 구현)

-내 생각 이 문제의 경우 처음에 접근을 1, 2, 3 더하기 문제처럼 접근을 해버려서 오답 처리를 받은 문제였다. 즉, n이 1일 때, 1의 제곱으로 1개, 2일 때 1의 제곱으로 2개, 3일 때 1의 제곱으로 3개... 식으로 증가한다는 규칙을 찾아서 이전 dp배열에서 1개씩 증가하는 식으로 풀었다. 그러나 문제에서도 언급되어 있듯이, 최소항의 개수를 구하기 위해서는 n보다 작은 제곱수부터 구해나가야 최소항을 구할 수 있는 것이다. 해당 규칙을 알고도 다시 시도해서 풀었는데 정답을 받긴 했지만. 아슬아슬하게 통과한 수준이라 다른 분들의 블로그를 참고해야 했다. -해법 내가 푼 방식은 제곱수와 n이 일치하면 1을 저장하는 방식으로 진행했는데, 그렇게 할 필요가 없이, n값에서 특정 수의 제곱을 빼주면 ..

→2019.12.02

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11055] 가장 큰 증가 부분 수열( JAVA 구현)

-내 생각 이 문제는 이전에 풀었던 가장 긴 증가 부분 수열인 LIS 문제와 동일한 문제였다. 차이점이라 한다면, DP 배열에 저장되는 값이 부분 수열의 길이가 아닌, 부분 수열의 합이 된다는 점이다. 그렇기 때문에 기본이 되는 알고리즘은 LIS를 구하는 문제와 동일하다. -해법 이런 식의 부분 증가수열은 기준점을 잡은 후 기준점 이전까지의 수들과 비교하여 자신이 큰 경우만 DP 배열을 갱신해주면 된다. 예를들어 2를 기준으로 잡았을 때, 2의 이전 숫자들인 과 100을 2와 비교해서 2가 큰 경우, 비교했던 숫자가 가지고 있는 dp값 + 기준이 되는 자신의 값으로 갱신해주면 되는데, 이때 주의해야 할 점은 100은 2보다 크기 때문에 자신의 dp배열을 갱신해주어야 한다. 이 경우에는 이전에 선택한 값이..

→2019.12.01

티스토리툴바