탐색 알고리즘 중 하나, 정렬된 리스트에서 logN의 성능을 보인다.
그래프의 완전탐색 기법중 하나, 2차원 평면 좌표를 탐색할 때 사용하기도 한다.
그리디 알고리즘, 다이나믹 프로그래밍 둘 중 하나의 방식으로 해결 할 수 있는 문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지
BFS + 구현능력이 필요한 알고리즘 문제
한국어로 해석하면 최장 증가 부분 수열,부분 수열이 주어진 수열에서 일부 항들을 원래 순서대로 나열하여 얻는 수열을 부분 수열 이라고 한다.그렇다면, 최장 증가 부분 수열은 부분 수열 중에서도 가장 길이가 긴 부분 수열을 말한다. 그렇다면, LIS를 어떻게 구현할 것
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 6, 10, 2라면 6102, 6210, 1062, 1026, 2610, 2106를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이
📖 BOJ - 10799 쇠막대기 문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는
선택 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제.간단한 해결 방법최소 숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 그 숫자를 제거한다. ⇒$O(kn)$최소 숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는다 ⇒ $O(nlogn)$⇒
최근접 점의 쌍을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제.모던 점에 대하여 각각의 두 점 사이를 계산하여 가장 가까운 점을 찾는 방법$\_nC_2$가 소요 => 모든 순서를 조합해야하므로 $O(n^2)
최소 신장 트리 주어진 가중치 그래프에서 사이클 없이 모든 점을 연결 시킨 트리 중 간선들의 가중치 합이 최소인 트리 크루스칼 알고리즘 가중치가 가장 작은 간선이 사이클을 만들지 않을 때만 'Greedy' 하게 그 간선을 추가시키는 방법 Pseudo Code Kru
Prim MST Algorithm 주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, (n-1)개의 간선을 하나씩 추가시켜 트리를 생성 Kruskal의 경우 간선의 비용을 항상 최소로 정했다면 Prim 알고리즘의 경우 정점을 기준으로 항상 최소의 가중치를 추가하여
주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제다익스트라 최단 경로 알고리즘이 가장 대표적인 최단 경로 탐색 알고리즘 중 하나임출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가그 점의 최
n개의 원소를 가진 집합인 U가 있고, U의 부분 집합들을 원소로 하는 집합 F가 주어질 때, 어떤 집합들을 선택하여 합집합이면 U와 같게되는 최소의 집합 수로 결정하는 문제만약 신도시를 계획하는데 각 도시를 커버할 수 있는 최소한의 학교를 건설하는 문제를 가질 때 해
작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 저근 수의 기계에 배정하는 문제학술대회에서 발표자들을 강의실에 배정하는 문제와 같음작업의 수 \- 입력의 크기이므로 알고리즘을 고안하기 위해 고려되어야 하는 직접적인 요소는 아님각 작업의 시작시간과 종료시간작업의
배낭(Knapsack) 문제는 n개의 물건이 있고, 각 물건이 무게와 가치를 가지고 있을 때, 최대의 가치를 갖도록 한정된 용량의 배낭에 넣을 물건들을 정하는 문제원래 배낭 문제는 물건을 통째로 배낭에 넣어야 되지만, 부분 배낭(Fractional Knapsack) 문
최단 경로를 찾는 방법은 다익스트라 알고리즘을 수행하면 된다 이때 $O(n^3)$이 소요된다. n은 점의 개수이다.모든 쌍 최단 경로를 찾는 방법으로, 시간 복잡도는 다익스트라 알고리즘을 $n-1$회 사용할 때와 동일하나, 매우 간단한 방법으로 효율적이다.다이나믹 프로
기존의 파일의 문자를 고정 변환 방식을 이용 하는 대신 빈도 순으로 문자가 가진 비트를 줄여 효율적인 메모리 사용하는 방법변환시킨 문자 코드 사이에는 접두부 특성이 존재하는데, 문자에 할당된 이진코드는 어떤 다른 문자에 할당된 이진 코드의 접두부가 되지 않는다는 것을
BOJ Silver - 5 / Greedy
BOJ 1715 - 카드 정렬하기 / Gold4 / Greedy
BOJ 17413 - 단어 뒤집기 / Silver 3 / Implementation
BOJ - 1990 / Gold 5
BOJ - 1918 / Stack / Gold-2
Programmers - 더 맵게 / Lv.2 / Heap
BOJ - 9205 / BFS / Gold - 5
BOJ - 1107 / BruteForce / Gold 5
BOJ - 5052 / Gold4 / String
BOJ - 9935 / Stack, String / Gold - 4
Programmers / Kakao Internship / Lv3 / Implementation