알고리즘 & 자료구조/알고리즘 개념

미로찾기 현재 위치에서 출구까지 가는 경로가 있으려면 현재 위치가 출구이거나 혹은 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 boolean findPath(x,y) if(x,y) is the exit return true; else for each neighbouring cell (x', y') of (x,y) do if(x',y') is on the pathway if(findPath(x',y') return true; return false 미로찾기는 답이 Yes or No인 문제이다. boolean findPath(x,y) if(x,y) is either on the wall or a visited cell return false; else if (x,y) as ..

순환 알고리즘 설계 적어도 하나의 basecase, 즉 순환되지 않고 종료되는 case가 있어야 한다. 모든 case는 결국 base case로 수렴해야 한다. 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라. 순차탐색 int search(int[] data, int n, int target){ for(int i=0; i end) return -1; else if (target == data[begin]) return begin; else return search(data, begin+1, end, target); } 이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색 구간의 시작점을 명시적(explicit)으로 지정한..

자기 자신을 호출하는 함수 void func(...){ ... func(...); ... } recursion이 항상 무한루프에 빠지는 것은 아니고 종료 조건을 알맞게 설정해주면 원하는 만큼 함수 호출이 가능하다. 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. → 종료 조건 recursion을 반복하다면 결국 종료조건으로 수렴해야 한다. 1~N까지의 합 public static int func(int n){ if(n == 0) return 0; else return n + func(n-1); } 팩토리얼 0! = 1 n! = n x (n-1) ! (n>0) public static int factorial(int n){ if(n == 0) return 1; else n * fact..

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DBS와 BFS를 꼽을 수 있는데, 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다. 그런데 DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 자료구조는 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그 중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 물론 실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 ..

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다. 우리가 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있나? 그렇지 않다. 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다. 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지..

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 이 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법으로 소개된다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 것은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 코딩테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은 이미 그 알고..