Leo.K | To become a cooler Developer

※ 소개 오늘은 오랜만에 코딩테스트 문제풀이를 위한 알고리즘을 정리해보고자 한다. 평소에도 문제풀이를 할때 논리가 부족해서 그런지 정렬이나 탐색 알고리즘보다 그리디나 동적 계획법쪽이 많이 어려웠는데 이번기회에 마리오 형의 강의를 참고해서 확실히 개념정리를 하고 문제를 풀어보면서 연습해보고자 한다. 알고리즘 기법의 명명 과정을 웃고 넘어갈 겸 살펴보니 다이나믹은 멋있어 보여서 붙였다고 한다... (괜히 있어보이긴 함) 프로그래밍이라는 단어는 컴퓨터 언어로 코딩을하는 것이 아니라 어떤 것을 계획하는 것을 의미하는 바가 크다. 즉, 문제가 있으면 특수한 형태로 변형시켜 쉽게 풀어내기 위한 일련의 과정이다. 입문하기는 쉽지만 마스터하기는 아주 어려운,,, 하지만 대회에서도 자주 출제되어 거의 뭐 알고리즘 학문에..

자료구조란? 자료구조는 데이터를 효율적으로 저ㅗ장, 접근, 수정하기 위한 그릇입니다. 코딩 테스트에서는 각 문제에 주어진 입력 데이터의 형태와 사용해야 하는 알고리즘에 따라 적절한 자료구조를 선정해 사용하는 것이 매우 중요하다. 3-1 배열과 리스트 기본 자료구조인 배열과 리스트는 비슷한 점도 많지만 다른 점도 많다. 두 자료구조의 특징을 정확하게 이해하고 문제가 요구하는 조건에 따라 적절하게 선택해 사용하는 것이 중요하다. 배열 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다. 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다. 다음 그림은 배열을 나타낸 것이다. 그림을 보면 배열에 값1, 값2, ... 값6이 채워져 있고, 각 값은 0부터 5까지 인..

취업 준비기간에 알고리즘 학습용 책을 구매했었는데, 문제풀이 참고용으로만 사용하여 "진짜" 학습을 하지는 못한 것 같아서 다시 천천히 공부해보려 한다. 목표는 매일 한 챕터씩 학습하고 정리하는 것이다. 취업 이후 실무에서 작업을 하는 도중 마주치는 문제는 항상 단연코 '좀 더 빠르게', '메모리를 좀 더 효율적으로'일 것 같다. 나름 알고리즘을 열심히 풀어서 좀 한다고 생각했지만,,, 원리를 모르고 문제를 풀이하는 방법만 공부해왔던 것 같아서 다시 제대로 정리해보려 한다. 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.모든 개발자들이 바라는 효율적인 알고리즘이란 쉽게 말하면 입력값이 커짐에 따라 증가하는 연산 시간의 비율을 최소화하는 것이다. 일반적으로 수행시간은 1억 번의 ..

오늘은 코딩테스트에 자주 등장하는 기본 개념으로 조합을 알아보자. 사실 조합으로만 푸는 문제가 나오진 않지만, 가장 빈출되는 동적 계획법을 풀이하기 위해선 조합에 대한 이해를 기반으로 점화식을 도출하는 연습은 필수라고 할 수 있다. 조합과 대비되는 개념으로는 순열이 있는데 이는 가볍게 개념만 인지하고 넘어가자 - 조합 : nCr = n!/(n-r)! -> n개의 수 중에서 r개의 수를 순서를 고려하여 나열할 경우의 수 - 순열 : nPr - n!/(n-r)!r! -> n개의 수 중에서 r개의 수를 순서를 고려하지 않고 뽑는 경우의 수 알고리즘에서는 위의 수학적 점화식을 코드ㄹ화하지 않고 점화식을 사용해 표현한다. 1. 특정 문제를 가정하기 먼저 가벼운 조합 문제를 가정해보자. 5개의 데이터에서 3개를 선..

트리 그래프에서 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상(LCA : Lowest Common Ancestor)이라고 한다. 핵심 이론 - 배열 형성 > 높이 맞추기 > 찾기 1. 일반적인 최소 공통 조상 구하기 먼저 트리의 높이가 크지 않을 때 LCA를 구하는 방법을 예시와 함께 알아보자. 특정 트리에서 두 개의 노드를 임의로 정한 다음 각 노드의 깊이와 부모 노드를 찾아보자. 이때는 DFS or BFS를 이용해 탐색을 수행한다. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 깊이의 노드를 해당 노드의 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춰준다. 이때 만일 두 노드가 같아지면 ..

취업을 하고 자사의 솔루션을 학습한다는 핑계로 미뤄두었던 알고리즘 학습을 다시금 천천히 시작해보려 한다. 오늘은 트리부터 시작해서 간단한 개념 정리와 문제풀이를 하려고 한다. 트리는 노드와 에지로 연결된 그래프의 특수한 형태로, 주요 특징은 아래와 같다. 순환 구조를 가지고 있지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 나머지 노드는 반드시 단 하나의 부모노드를 가진다. 2개 이상의 부모 노드가 있다면 순환구조가 생길 수 밖에 없음 트리의 부분 트리 역시 트리의 모든 특징을 따른다. 트리의 구성요소 구성 요소 설명 노드 데이터의 index와 value를 표현하는 요소 에지 노드와 노드의 연결관계를 나타내는 선 루트 노드 트리에서 가장 상위에 존재하는 노드 부모 노드 두 노드 사이의 관계에..

모든 문제를 푸는 데에 있어서 가장 쉽고 간단한 방법을 짚고 넘어가겠다. 원래는 다른 탐색 알고리즘을 정리하기 전에 먼저 한 번 짚고 넘어가야 했지만,,, 은연중에 쉽다는 생각에 미뤄두었었다. 하지만 최근에 완전탐색 문제를 풀다가 제대로 깨진적이 있어서 정리하고 넘어가려고 한다. 단순하게 생각하면, 가능한 경우의 수를 일일이 모두 다 탐색해보는 것이다. 정확도는 100%에 달하는 유용한 방법이지만 세상에 좋은 기능만 있는것이 어디 있겠는가... 정확도가 증가하는 것에 비례하게 시간이 증가한다. 그렇기 때문에 정확도를 높게 유지한 상태로 코드를 문제에 맞게 조건을 걸어서 최적화를 해주어야 한다. 한 가지 간단한 예시를 들어보겠다. 사실 브루트 포스가 어려운 이유는 바로 후자, 조건에 맞게 코드를 최적화하면..

지난 번에 그래프의 종류에 대해서 정리를 했다. 오늘은 그래프를 순회하는 방법중의 하나인 DFS탐색법을 정리하겠다. BFS는 다음시간에 이어서 정리하도록 하겠다. 코테에 가장 많이 나오는 탐색유형으로 한 번쯤은 정리할 필요성이 있다고 생각했다. 아직 그래프에 대해 잘 모른다면, 여기로 가서 간단하게 개념을 익히고 오는 것이 좋을 것 같다. 보통 BFS는 큐를, DFS는 스택을 사용하여 구현하는데, 재귀함수 또한 스택 메모리 공간에 쌓아 올려지는 구조를 띄기 때문에 재귀함수를 사용하여 구현 및 정리하도록 하겠다. 그래프의 모든 정점을 한 번씩만 방문하기 위해 DFS(depth-first-search)를 구현하기 전에 간단하게 DFS의 탐색 과정과 순서를 살펴보고 넘어가자. 이름 그대로 한 우물만 깊게 파다..

수학에서 정수론은 수의 성질을 탐구하고 공부하는 분야를 뜻합니다. 모든 정수론을 공부하는 것은 비효율적이니 코딩테스트에 자주 등장하는 소수와 호제법 부분을 다루겠습니다. [소수 구하기] - 자기 자신보다 작은 두 수의 곱으로 표현할 수 없는 1보다 작은 자연수 - 1과 자기 자신 이외의 약수가 존재하지 않는 수 [에라토스테네스의 체] 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다. 2부터 시작하고 현재 숫자가 지워지지 않을때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다. 범위의 끝값의 제곱근까지 과정을 반복하고 2번 과정을 반복하고 남아 있는 모든 수를 출력합니다. ex) 1부터 30까지의 수 중 소수를 구하기 1은..

구간합은 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 코딩테스트에 출제되는 빈도가 높다고 하여 한 번 정리하고 가겠습니다. 구간 알고리즘의 핵심은 배열을 초기화하면서 합 배열을 구하는 것입니다. 이렇게 실제로 합을 구하기 전에 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 대폭 감소합니다. 예를들어, 위와 같이 배열A에서 구간의 합을 구해야 할 때, 합 배열을 구해놓으면, 실질적으로 합 계산을 수행할 때, 시간을 단축시킬 수 있습니다. [합 배열 안 구한 경우] (최악) O(N) -> idx 0 ~ 5까지의 합을 구하시오 for(int i=0; i idx 0 ~ 5까지의 합을 구하시오 S[5] - S[0] 단..

BFS(Breadth First Search) BFS는 그래프를 완전탐색하는 방법 중 하나로 너비를 우선하여 탐색하는 방법입니다. 즉, 출발하는 지점(시작노드)에서 인접 노드(가장 가까이 있는 노드를 우선적으로)를 모두 방문하고, 방문한 노드에서 다시 인접노드를 모두 방문하는 것을 반복하면서 탐색하는 방법입니다. 위의 그래프에서 탐색을 하는 과정을 순서대로 보면 다음과 같습니다 [1 -> 2 -> 3 -> 4 -> 5] 1번노드를 시작 노드라고 한다면 1번과 인접한 노드인 2, 3번 노드를 방문하게 됩니다. 2번 노드와 인접한 4, 5번 노드를 방문합니다. (모든 노드 탐색 끝) 3번 노드와 인접한 1, 5번 노드, 4번 노드와 인접한 2, 5번 노드, 5번 노드와 인접한 2, 3, 4번 노드는 앞에서 ..

알고리즘 문제를 해결할 때, 가장 좋은 방식은 문제를 이해하고 어떤 자료구조를 사용하여 해결할 것인가에 대한 사고과정이 중요합니다. 알고리즘을 선택하는 기준으로 시간복잡도를 고려해야 하기 때문에 오늘은 이에 대해서 공부해보겠습니다. 자료구조를 알고 사용하는 것이 중요하지만, 각 자료구조마다 사용되는 시간 복잡도가 어느정도인지를 알면 선택에 있어 더 효율적인 방향을 잡을 수 있습니다. 하루 만에 모든 시간복잡도에 대한 공부와 예시를 들기는 어렵기 때문에,,, 기본 개념만 잡아두고, 앞으로 공부를 하면서 해당 복잡도에 관한 알고리즘을 풀게 되면 예시로 들면서 내용을 추가하겠습니다. 1. 시간복잡도 표기법 알아보기 먼저 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 ..