MJmemento

깊이 우선 탐색(DFS)란? 19세기에 프랑스 수학자 샤를 피에르 트레모가 미로를 풀기 위한 전략으로 연구하여, 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기 위한 알고리즘이다. 알고리즘은 (시작)루트 노드(만약 그래프의 경우 임의 노드)에서 시작하여 역추적하기 전에 각 분기를 따라 가능한 멀리 탐색한다. 아래 그림을 통해 어떻게 DFS가 노드에 순차적으로 접근하는지 알 수있다. 처음 시작 노드에서 인접 노드로 움직이는데 한번 팠다면 끝까지 파는 깊이있는 알고리즘이다.(그래서 깊이 우선 탐색) 그렇다고 불도저 마냥 불가능해도 계속 한 우물만을 파는 녀석은 아니다. 만약 가다가 더 이상 불가능한 노드(4)를 만났을 때는 그제서야 돌아가 다른 최근 노드(5)로 우물을 판다. 해당 각 노드는 인접리스트와..

이분 탐색이란? 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제며, 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 더 자세히 말하자면 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다 아직 말로는 잘 모를 수 있다. 그림으로 이해해보자. 위에는 우리가 할 이분 탐색, 아래는 순차적으로 탐색이다. (이진 탐색의 시간 복잡도는 O(logN) 전수 조사하는 O(N)) 정렬된 리스트에서 중앙값이 찾고자하는 값보다 작거나 큰지에 대하여 범위가 수정되어 다시금 찾는 방식이다..

동적 계획법이란? "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘이다. 다시 말하면 어떠한 문제를 풀 때, 이전의 문제를 기반으로 현재 문제를 해결해야하는 상황이 온다면 똑같은 과거의 문제를 풀어야하는 상황에 노일 수도 있다. 예시로) A라는 문제를 풀기위해 B라는 녀석을 풀었다. 근데 C라는 문제를 풀기위해 B라는 녀석을 풀어야한다네? B를 굳이 다시 풀어야할까? 이미 A를 풀때 B를 풀었다면 B의 값을 기억하고 C를 풀면된다. 다음 예시와 같이 문제를 해결하는 것이 동적 계획법 DP다. 그렇다면 DP 를 구현하기 위해 어떻게 문제에 접근해야할까? 1. 상향식 접근방식 하위 문제에 대한 결과 계산을 시작한다 . 하위 문제 결과를 사용..

분할 정복이란? 주어진 문제에서 길이를 반으로 계속해서 잘라 최소 단위로 만든 뒤 , 최소단위를 해결함으로써 상위 문제를 계속해서 해결해 결과적으로 정답을 도출해내는 알고리즘이다. 아래 사진을 보면 해당 문제를 아래로 갈 수록 반으로 분할(빨간색) 위로 갈 수록 하나로 병합(파란색) split과 merge를 통해 problem을 해결한다. 분할 정복을 통한 대표적인 알고리즘으로는 병합 정렬(merge sort), 이분 탐색(binary search)이 있다. 그중에 우리는 병합 정렬을 통해 분할 정복을 다시 보고자한다. 병합 정렬을 그림으로 보자면 아래와 같다. 일단 숫자열을 계속해서 반으로 나누어 하나의 가장 작은 단위로 만든다. 그 뒤에 서로 다른 두 배열의 앞 인덱스 값을 비교하여 작은 요소를 왼쪽..

탐욕 알고리즘은 현재 사용할 수 있는 최선의 옵션을 선택하여 문제를 해결하기 위한 접근 방식이다. 현재의 최상의 결과가 전반적인 최적의 결과를 가져올지는 걱정하지 않으며 현재 진행 중인 선택이 잘못되더라도 이전의 결정을 뒤집지 않고 계속 진행한다. 다시금 얘기하면 현재 보기에 가장 최적으로 보이는 경우를 조건으로 두고 계속해서 답을 좆는 방식이란 것이다. 최적의 해를 구하기 위해 설계적으로 딱! 하고 가는 것이 아니라 일차적 최적, 이차적 최적해서 가장 가까운 최적을 찾아가는 기법이기에 항상 최적의 해를 구할 수 있는 문제는 아니다. 그러나 왜 이 알고리즘을 많이 사용할까? 코딩테스트에서 구현문제의 경우 그리디 알고리즘을 사용하는 경우가 많다. 전체적인 맥락에서 처음부터 끝까지 최적의 길을 찾기보단 순차..

이번에 소개하고자 하는 알고리즘은 완전탐색이다. 단어에서 보이는대로 모든 경우의 수를 탐색하는 알고리즘이다. 완전 탐색 말고도 브루트포스라고도 하며 웬만큼 코딩테스트에서 사용하지 않는다. (시간초과가 뜰테니까 ㅠ) 모든 경우를 탐색하기에 꼼꼼하지만 모든 것을 돌아 확인하는 이 방식은 쓸모없는 행동이 많다. 예를 들어보자 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제에서 9난쟁이중 7난쟁이의 키 합이 100이란 사실을 확인하고 찾아주면 된다. 이중..

구현한 알고리즘의 성능을 보기로만으로 비교하기는 쉽지 않다. 그렇기에 어느정도의 척도를 갖고 비교해야만하는데 우리는 이러한 문제를 해결하기위해 빅오 표기법을 사용할 수 있다. 빅오 표기법 이란 알고리즘의 성능을 수학적으로 표현해주는 표기법으로 O 라는 함수 안에 숫자 혹은 n 을 넣음으로써 알고리즘의 성능을 표기할 수 있다. 여기 성능은 시간과 공간복잡도를 표현한다. ++ 알고리즘의 실제 러닝타임을 표기하는 것이 아닌, 데이터나 사용자의 증가량에 따른 알고리즘의 성능을 예측하는 것이 목표이기 때문에 상수가 100인든 11000 이든 O(1)로 표기한다. 또한 O(2n) -> O(n) 으로 볼 수도 있다. 그러나 O(n^2+m) 같이 각 항의 변수가 다를 경우는 함부로 없앨 수 없다. O(1) 알고리즘은 ..

내가 지나온 어느 결정들이 막다른 길이 보이면 내가 가장 최근에 내린 경로를 따라 가는 것이 back- tracking이다. 오늘 풀어볼 문제는 N-Queen이라고 해서 이 백트레킹알고리즘을 사용하여 해결할 것이다. 문제는 이렇다. n*n 체스판에 n개의 말을 놓는데 그 어떤 두 말도 동일한 행이나 열 대각선에 위치하지 않게 하는 문제다. 일단 하나씩 해결해보자 첫번째 말을 첫번째 행 중 하나 놓는다면 그 행과 열 대각선은 앉지 못한다. 계속해서 두번째 말을 실패하지 않는 경우에 계속해서 놨지만 결과적으로 더 이상 퀸을 체스판에 놓지못할 때 가장 최근의 경우의 수로 번복하여 새로 경우의 수를 둘 것이다. 그렇게 계속 두다가 첫번째 말이 첫 번째 행 모두를 뒀지만 만약 모든 경우가 막혔다면. 첫번째 행에 ..