codingTest (14) 썸네일형 리스트형 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 - (9) 삽입 정렬 삽입 정렬 - 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 - 시간 복잡도는 O(n^2)으로 느린 편이지만 구현하기 쉽다. 핵심 이론 - 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입한다. 삽입 정렬 과정 현재 index에 있는 데이터 값을 선택한다. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다. 문제 풀이 https://yurison.tistory.com/439 [백준/자바] 11399.. Do it! 알고리즘 코딩테스트 with JAVA - (8) 선택 정렬 선택 정렬 - 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 - 구현 방법이 복잡하고 시간 복잡도도 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않는다. 핵심 이론 - 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap한다. 선택 정렬 과정 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다. 문제 풀이 https://yurison.tistory.com/438 [백준/.. Do it! 알고리즘 코딩테스트 with JAVA - (7) 버블 정렬 버블 정렬 - 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 - 간단하게 구현할 수 있지만, 시간복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다. 버블 정렬 과정 비교 연산이 필요한 루프 범위를 설정한다. 인접한 데이터 값을 비교한다. swap 조건에 부합하면 swap 연산을 수행한다. 루프 범위가 끝날 때까지 2~3을 반복한다. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다. 비교 대상이 없을 때까지 1~5를 반복한다. - 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다. 문제 풀이 https://yurison.tistory.com/4.. Do it! 알고리즘 코딩테스트 with JAVA - (6) 스택과 큐 스택과 큐 - 배열에서 발전된 형태의 자료구조 - 구조는 비슷하지만 처리 방식은 다르다. 스택 - 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조 => 재귀 함수 알고리즘 원리와 일맥상통하다. - 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다. - 깊이 우선 탐색, 백트래킹 종류의 코딩 테스트에 효과적이다. - 용어 : top(삽입과 삭제가 일어나는 위치), push(삽입 연산), pop(삭제 연산), peek(조회 연산) 큐 - 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조 => 먼저 들어온 데이터가 먼저 나간다. - 삽입과 삭제가 양방향에서 이뤄진다. - 너비 우선 탐색에서 자주 사용된다. - 용어 : rear(가장 끝 데이터), front(가장 앞의 데이터), add(rea.. 이전 1 2 다음
