[BOJ 1300] k번째 수
문제 BOJ 1300 문제의 저작권은 Baekjoon Online Judge에 있습니다. 접근방식 행렬의 원소는 항상 i의 배수가 된다. 이 문제에서 구하고자 하는 것은 K번째에 해당하는 수이므로 K번째 앞에 어떤 숫자가 오든 상관 없이 앞에 몇개가 있는지 생각해주면...
최근 포스트
[BOJ 12015] 가장 긴 증가하는 부분수열2(LIS)
문제 BOJ 12015 문제의 저작권은 Baekjoon Online Judge에 있습니다. 접근방식 이 문제는 이분탐색으로 풀 수 있고 접근한 순서는 다음과 같다. 넣어줘야 하는 값num이 현재 리스트의 마지막값보다 크면 그 뒤에 바로 넣어준다. if (...
[BOJ 2110] 공유기 설치
문제 BOJ 2110 문제의 저작권은 Baekjoon Online Judge에 있습니다. 접근방식 인접한 두 공유기 사이의 최대 거리를 mid로 두고 이분탐색을 한다. 집 거리가 저장된 배열에서 mid로 몇개의 공유기를 설치할 수 있는지 구한다. 만약 설...
[알고리즘] 이분탐색(Binary Search)
개념 데이터가 정렬된 배열에서 가운데값을 기준으로 특정한 값을 찾아내는 탐색 알고리즘 이분 탐색을 하기 위해서는 반드시 데이터가 정렬된 상태여야 한다. 시간복잡도 O(logN) 순서 배열을 오름차순으로 정렬한다. {17, 28, 43,...
[자료구조] 분할정복(Division and conquest)
개념 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법 하향식(Top-down) 접근방법 👍장점 문제를 나눔으로써 어려운 문제 해결 가능 병렬적으로 문제를 해결하는데 큰 강점 👎단점 함수 재귀 호...