이분 탐색이란? 이분 탐색아란 오름차순으로 정렬된 수열에서 원하는 값을 찾는 탐색 알고리즘입니다. 여기서 포인트는 정렬된 수열에서 가능하다는 것입니다! 이분 탐색 방법 정렬된 배열에서 값을 찾는다는 가정 하에 아래의 과정을 반복하면 됩니다! 배열의 가운데 요소의 인덱스를 pivot으로 정합니다. arr[pivot]의...

문제 풀이 백준의 18111번 문제입니다. 문제 출처 (1) 문제 파악 (2) 문제 풀이 방법 생각하기 땅의 높이를 모두 같게 만드려면 어느 높이로 같게 만들 것인지를 결정해야 합니다. 기준이 될 땅의 높이는 min, max 사이에 존재할 것이므로 min부터 max까지 순회하며 시간이 최소로 걸리는 땅의 최대 높이를 찾아내면 됩니다. (주의할...

문제 풀이 백준의 1181번 문제입니다. 문제 출처 (1) 문제 파악 알파벳 소문자로 이루어진 단어를 정렬하는 문제입니다. (2) 문제 풀이 방법 생각하기 중복된 단어는 하나만 남기고 제거해야 한다고 하니, Set을 사용하면 좋을 것 같네요! Set에 단어들을 담아 중복을 제거한 뒤, 단어들을 문제의 정렬 방식대로 정렬하면 됩니다. (3)...

문제 풀이 백준의 1018번 문제입니다. 문제 출처 (1) 문제 파악 가지고 있는 보드를 잘라 체스판을 만드는 문제입니다. (2) 문제 풀이 방법 생각하기 체스판의 크기는 8 * 8로 고정되어 있으니 보드가 주어지면 만들 수 있는 체스판의 개수가 나옵니다. 색칠할 칸의 최소 개수를 구하는 문제이므로, 가능한 보드를 모두 잘라 확인해보고 최소...

문제 풀이 백준의 11650번 문제입니다. 문제 출처 (1) 문제 파악 x,y 좌표를 가진 점이 있을 때, 점을 정렬시키는 문제입니다. (2) 문제 풀이 방법 생각하기 x좌표를 정렬하고, 같은 x좌표일 경우 y좌표를 정렬하면 되므로 x좌표를 key로 가지는 Map을 사용해 문제를 풀 수 있습니다. Map<x좌표, y좌표 리스트> ...

문제 풀이 백준의 10844번 문제입니다. 문제 출처 (1) 문제 파악 계단 수란 인접한 자리끼리의 차이가 모두 1인 수를 의미하며, 길이가 N인 계단 수의 개수를 찾는 문제입니다. (2) 문제 풀이 방법 생각하기 0~9까지의 정수 중 0과 9를 주의해야 합니다. 0 다음에는 반드시 1이 옵니다 -> \(arr[N][0] = ...

문제 풀이 백준의 9461번 문제입니다. 문제 출처 (1) 문제 파악 보자마자 DP가 떠오르는 문제입니다. 이어지는 수열을 계산하면 되는 문제이지요! (2) 문제 풀이 방법 생각하기 변이 더해져서 다음 것이 생기는거니까 앞 부분을 더해서 식을 만들어볼까? 하는 생각으로 규칙을 찾아보았습니다. 문제에 나온 예시를 통해 다음과 같은 규칙을 쉽게...

문제 풀이 백준의 1904번 문제입니다. 문제 출처 (1) 문제 파악 (2) 문제 풀이 방법 생각하기 \(P[a] = P[a-1] + P[a-2]\) 여기서 주의해야 할 점은 N이 1,000,000까지 가게 되면 int나 long의 범위를 넘어설 수 있습니다. 그러므로 값 자체를 저장하는 것이 아닌 15746으로 나눈 값의 나머지를 저장하여...

카운팅 정렬이란? 카운팅 정렬이란 단어 그대로 정렬 알고리즘 중 하나입니다. 그렇다면 앞에 붙은 카운팅은 무엇일까요? 무엇을 카운팅한다는 것일까요? 정답은 데이터의 값이 몇 번 등장했는지를 카운팅하는 것입니다. 대부분의 정렬은 데이터의 값을 직접 비교하여 정렬하는 경우가 많지만 데이터 값의 직접 비교는 시간 복잡도가 O(NlogN)보다 작아질 수 ...

문제 풀이 백준의 2108번 문제입니다. 문제 출처 (1) 문제 파악 문제에서 알려준 그대로 연산 결과를 출력하면 되는 문제입니다. (2) 문제 풀이 방법 생각하기 이 문제에서의 포인트는 최빈값 입니다! 숫자 값의 범위는 -4000에서 4000까지로 범위가 작으므로 각각을 인덱스로 사용하는 배열을 만들어 값의 숫자를 카운팅하였습니다. (3...