전체 글

작년에 2022를 마무리하며..라는 글로 블로그를 본격적으로 시작했는데 어느새 2023을 마무리하며 라는 글을 쓰게 되었다. 작년과 마찬가지로 한해를 되돌아보고 앞으로의 목표와 다짐까지 적어보려한다. 2023년은 상반기는 사회생활을 했고 하반기에는 입대를 했기에 작년과 같이 나눠서 기록한다. 상반기의 목표는 부족한 학점을 채우자 였던거 같다. 컴퓨터공학부가 정확히 뭐하는 학과인지도 모르고 입학해서 1학년을 신나게 놀고, 코딩과목 학점도 신나게 말아먹었으니 복구해야한다는 생각이 들었다. 코딩에 대해 아무것도 몰랐던 1학년때와는 다르게 1일 1백준으로 나름 자신감을 갖고 2학년을 시작했다. 그리고 1일1백준의 효과를 바로 체감할 수 있었다. 1일1백준을 할 때의 목표는 코드로 아무것도 만들지 못했기에, 단순..

DP: 한 문제를 해결하기 위해 문제를 부분 문제로 분할하여 해결하고 부분문제들의 해를 바탕으로 큰 문제를 해결하는 문제해결기법. 정의를 딱 보자마자 생각나는 생각이 분할정복이랑 비슷하다라는 생각이 든다. 하지만 내용은 문제를 나눈다는 사실을 제외하고는 비슷한 문제해결방법이 아니다. 심지어 문제를 나누는 것도 분할정복은 큰 문제라는 덩어리를 여러부분으로 쪼개는 느낌이고, DP는 큰 문제의 이전 단계의 경우를 생각하는 걸 문제를 나눈다고 한다. 분할정복: 큰 덩어리 문제를 작은 덩어리로 쪼개서 해결한 뒤에 합치는 방식으로 문제를 해결 DP : 큰 문제를 작은 부분 문제로 나누고 작은 부분 문제의 해을 저장하여 중복 계산을 피하거나, 작은 부분문제의 최적해로 점화식을 세워 큰 문제를 해결 DP는 문제 유형을..

● 분할정복(Divide and Conquer) 한번에 해결하기에 불가능하거나 매우 오래걸리는 문제를 작은 문제로 나눠서(분할) 해결하고 다시 결합하여(정복) 문제를 해결하는 방식 **앞서 포스팅 했던 이분탐색 또한 분할정복을 사용한 알고리즘 Merge sort(병합정렬) 분할정복을 이용한 정렬방법으로 O(NlogN)의 시간복잡도를 가지며 버블정렬, 삽입정렬, 선택정렬 보다 실행시간이 빠르다. (파이썬에 내장되있는 sort함수도 병합정렬) 병합정렬을 통해서 분할정복이 어떤식으로 이루어지는지 알아보자. 정렬을 하기 위해 임의의 무작위 배열 arr = [3, 25, 1, 75, 42, 100, 63, 38] 이 있다고 하자. 이 배열의 Divide 과정은 아래그림과 같다. 배열의 중간을 기준으로 더 이상 나..

스택과 큐는 데이터를 제한적으로 접근할 수 있는 나열 구조로 가장 기본적인 자료구조 중 하나이다. 1. 스택(Stack) 데이터를 차곡차곡 쌓아올린 형태의 자료구조로 후입선출(Last in First Out) 개념이다. 스택에 나중에 들어간 놈이 먼저 나온다고 생각하면 된다. 그림과 같이 Stack에 데이터를 추가하는 작업을 push, 제거하는 작업을 pop 이라고 한다. StackOverflow(오버플로우): 스택이 가득차서 더 이상의 데이터를 추가할 수 없는 경우 ● stack.push(x) - 스택에 데이터를 추가 ● stack.pop() - 스택의 최상위 데이터를 삭제 ● stack.top() - 스택의 최상위 데이터를 반환 ● stack.empty() - 스택이 비었는지 확인 ● stack.si..

이분 탐색 또한 앞서 포스팅 했던 Brute force와 마찬가지로 solved.ac의 Class2에서 등장하는 알고리즘이다. 이분 탐색은 문제를 푸는 하나의 도구로 굉장히 중요하며 자유자재로 사용할 수 있어야 한다. 먼 미래지만 세그먼트 트리를 형성할 때 이분 탐색과 비슷한 형식으로 트리를 형성하고 그리디(Greedy) 등의 알고리즘과 함께 나와도 이상하지 않을 정도로 사용 빈도가 꽤 높다. 우리가 어떤 배열이나 벡터에서 숫자를 찾을 때 최악의 시간복잡도는 O(n)으로 선형 시간(Linear time)을 갖는다. (** 알고리즘의 실행 시간이 데이터가 증가함에 따라 선형적으로 증가할 때의 시간을 선형시간이라고 함.) 하지만 이분 탐색의 시간복잡도는 log2(n)으로 선형 탐색에 비해 빠른 시간 안에 원..

아마 solved.ac를 통해서 문제를 풀다보면 구현이나 수학 문제를 제외하고 가장 처음 접하는 알고리즘일 것이다. (주위에 물어보면 그래도 들어는 봤다라고 하는 사람이 많았다.) 이름은 거창하지만 이 기법은 모든 가능성을 빠짐없이 탐색하는 방법이다. 이 표현도 다시 표현하면 노가다 정도로 말할 수 있겠다. 사실 일반 구현문제하고 비슷하다. 브루트 포스라고 해서 특별한 방법이 있는 것이 아니라 가능한 모든 경우의 수를 전부 확인할 수 있도록 코드를 짜면 그게 Brute force 탐색이다. 그럼 속으로 그냥 다 해보면 되는거니까 완전 쉬운거 아닌가? 라고 생각할 수 있는데 다 탐색하도록 코드를 구상하는 것이 생각보다 쉽지 않다. 구현력을 상당히 많이 필요로 하는 알고리즘이다. 코딩테스트에서도 거의 빠짐없..