공부 기록/알고리즘 (19) 썸네일형 리스트형 Do it! 알고리즘 코딩테스트 with JAVA - (16) 그리디 알고리즘 그리디 - 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 핵심 이론 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다. 문제 풀이 https://yurison.tistory.com/572 [백준/자바] 11047 - 동전 0 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.. Do it! 알고리즘 코딩테스트 with JAVA - (15) 이진 탐색 이진 탐색 - 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘 - 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. - 시간 복잡도는 O(logN)이다. - 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다. 핵심 이론 - 오름차순으로 정렬된 데이터에서 아래의 4가지 과정을 반복하며, 내림차순이라면 조건을 반대로 하여 과정을 반복한다. 현재 데이터셋의 중앙값을 선택한다. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. 문제 풀이 https://yuri.. Do it! 알고리즘 코딩테스트 with JAVA - (14) BFS(너비 우선 탐색) BFS(너비 우선 탐색) - 그래프를 완전 탐색하는 방법 중 하나 - 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 - 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다. - 특징 : FIFO 탐색, 큐 자료구조를 이용한다. - 시간 복잡도는 O(V + E)이며, 여기서 V는 노드 수, E는 엣지 수를 말한다. BFS 과정 BFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화한다. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입한다. 큐 자료구조에 값이 없을 때까지 반복한다. 문제 풀이 https://yurison.tistory.com/555 [백준/자바] 1260 - DFS.. Do it! 알고리즘 코딩테스트 with JAVA - (13) DFS(깊이 우선 탐색) DFS(깊이 우선 탐색) - 그래프 완전 탐색 기법 중 하나 - 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 - 특징 : 재귀 함수로 구현되며,(스택 오버플로에 유의) 스택 자료구조를 이용하기도 한다. - 시간 복잡도는 O(V + E)이며, 여기서 V는 노드 수, E는 엣지 수를 말한다. 핵심 이론 - 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다. - 탐색 방식은 후입선출 특성을 가진다. DFS 과정 DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화한다. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입한다.(방문 배열 체크) 스택 자료.. Do it! 알고리즘 코딩테스트 with JAVA - (12) 기수 정렬 기수 정렬 - 값을 비교하지 않는 특이한 정렬 - 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. - 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다. 핵심 이론 - 10개의 큐를 이용하며, 각 큐는 값의 자릿수를 대표한다.(0~9) 문제 풀이 https://yurison.tistory.com/362 [백준/자바] 10989 - 수 정렬하기 3 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws I.. Do it! 알고리즘 코딩테스트 with JAVA - (11) 병합 정렬 병합 정렬 - 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 - 시간 복잡도는 O(nlogn)이다. 병합 정렬 과정 최초에 가장 작은 그룹으로 나눈다. 2개씩 그룹을 합치며 오름차순 정렬한다. 다시 2개씩 그룹을 합치며 정렬한다. 위의 과정을 거치면 그룹 전체의 오름차순 정렬이 완료된다. 2개의 그룹을 병합하는 과정 - 투 포인터 개념을 사용하여 왼족, 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다. 문제 풀이 https://yurison.tistory.com/344 [백준/자바] 2751 - 수 정렬하기 2 import java.io.*; import java.util.Arra.. Do it! 알고리즘 코딩테스트 with JAVA - (10) 퀵 정렬 퀵 정렬 - 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬한다. - 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2)이 된다. 핵심 이론 - pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬한다. 퀵 정렬 과정 데이터를 분할하는 pivot을 설정한다. pivot을 기준으로 아래의 과정을 거쳐 데이터를 2개의 집합으로 분리한다. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다. end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다. start가 가리키는 데이터가 p.. Do it! 알고리즘 코딩테스트 with JAVA - (9) 삽입 정렬 삽입 정렬 - 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 - 시간 복잡도는 O(n^2)으로 느린 편이지만 구현하기 쉽다. 핵심 이론 - 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입한다. 삽입 정렬 과정 현재 index에 있는 데이터 값을 선택한다. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다. 문제 풀이 https://yurison.tistory.com/439 [백준/자바] 11399.. 이전 1 2 3 다음
