코테 연습 - 이분탐색

오늘은 이분탐색에 대해 정리해볼것이다.우선 이분탐색이 뭔지 알아보자이분탐색 : 정렬된 데이터에서 탐색 범위를 절반씩 줄여가며 목표 값을 찾는 탐색 알고리즘일단 이분탐색을 하기 위해선 반드시 배열을 정렬시켜둬야 한다.그리고 보통 low를 첫번째 인덱스, high를 마지막 인덱스로 지정한다. 그 후 (low + high) / 2로 mid(중앙값) 값을 정한다.그리고 찾기위한 수 (이 그림에선 31) target을 정한다. 위의 글대로 진행하면 low = 0, high = 9, mid = 4, target = 31이 된다.이제 중앙값과 target을 비교해줄것이다. arr[mid] = 13, target = 31 arr[mid] 다시 위 과정을 반복하면 low = 8, high = 9, mid = 8, tar..

이번주는 코딩테스트 정렬 알고리즘에 대해 정리해볼것이다.우선 정렬의 종류에는 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬 ,퀵 정렬, 힙 정렬, 계수 정렬 등 여러가지 종류가 존재한다.모든 정렬을 설명하는게 좋을 수 있지만 코딩테스트에서 사용되는건 퀵, 삽입, 병합 정렬 3종류가 주로 사용되기 때문에 3가지 정렬만 간단하게 정리하고 갈것이다. - 퀵 정렬 (Quick Sort)우선 퀵 정렬이다. 보통 퀵정렬은 기본타입들을 정렬할때 사용된다. ex) int[], double[], char[] 등등이제 퀵정렬의 메커니즘을 알아보자 step1 : 우선 pivot 선정한다. step2 : low 포인터를 pivot 이상의수가 나올때까지 이동시킨다(왼 -> 오). high 포인터는 pivot 이하의수가 나..

오늘은 코딩테스트 백트래킹에 대해 정리해 볼 것이다. 백트래킹은 가능한 모든 경우의 수를 탐색하면서 조건에 맞지 않는 경우에는 탐색을 중단하고 이전으로 돌아가는 방식의 알고리즘이다.이러한 방식을 가지치기라고 한다. (이러한 가지치기가 모든 경우를 탐색하는 dfs 와의 차이점이라고도 볼 수 있다)  백트래킹도 일종의 재귀함수이기 때문에 지난번의 재귀함수와 마찬가지로 기저 조건이 중요하다.일단은 코드로 간단한 백트래킹의 기본 구조를 알아보자void backtrack(int depth) { if (depth == 목표깊이) { // 정답처리 return; } for (int i = 시작값; i  백트래킹의 기저 조건은 가지치기를 하는 거라 볼 수 있을 것이다. 그런데 ..

오늘은 코딩테스트 재귀 알고리즘에 대해 알아볼것이다. 우선 재귀가 무엇인가 부터 알아야한다.재귀란 함수가 자기 자신을 호출하는 것이다. 말그대로의 뜻이기 때문에 크게 더 설명할 부분이 없다.쉬운 예시로 팩토리얼, 피보나치 수열등의 문제를 재귀로 풀 수 있다. 아래의 코드는 간단한 재귀 함수의 예시다.void recur(int n) { if (n == 0) return; // 기저 조건 (종료 조건) recur(n - 1); // 자기 자신 호출}재귀에는 반드시 기저조건(탈출, 종료 조건)이 필요한데 기저조건이 존재하지 않는다면 재귀함수를 무한히 호출하기 때문에 스택 오버플로우가 발생한다. 또한 재귀는 스택과 유사한 구조를 가지고 있는데 n = 3인 경우 위의 함수를 실행한다면recu..

이번에는 코테 알고리즘인 bfs/dfs 에 대해 알아볼것이다. bfs와 dfs 는 그래프탐색 방법 중 하나로, 어떤 노드를 방문할 때 그 방법이 다르다는 것이다.bfs 와 dfs 의 노드 방문 방법은 다음 그림과 같다. 자 그러면 bfs/dfs 문제에서 어떤 문제에서 어떤 알고리즘을 적용해야할까 고민일것이다. 일단 두 방법으로 모두 풀 수는 있지만시간제한 때문에 한가지 알고리즘으로 풀어야하는 경우도 존재할 것이다. 그러한 경우를 생각하며 bfs/dfs 를 설명해볼것이다. - BFS (너비 우선 탐색, Breadth-First Search)우선 탐색 순서는 가까운 노드부터 탐색한다. 자료구조는 Queue를 이용한다 큐는 알다시피 FIFO(First In First Out) 선입선출의 자료구조이다.왜 큐 자..

오늘은 Stack 알고리즘에 대해 알아보자우선 Stack 자료구조를 먼저 알아보자 스택은 LIFO(후입선출) 형식의 자료구조이다말 그대로 나중에 들어온 자료가 먼저 나간다는 의미이다. 간단하게 설명 할 수 있지만 더 자세히 이해하기위해 스택을 구현하는 코딩테스트 문제로 알아보자https://www.acmicpc.net/problem/10828 백준 10828 스택 문제이다. 두가지 풀이 방식이 존재하는데 하나는 Stack 자료구조를 이용하지 않고 배열을 이용해 구현하는 방법두번째는 Stack 자료구조를 이용하는 방법이다. 스택에 대해 무지하거나 스택을 구현해본적이 없다면 첫번째 방법을 먼저 시도해보는게 좋을것이라 생각된다. 우선 첫번째 풀이다.public class S_4_10828 { public..