jee's coding story

유클리드 호제법 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 호제법은 두 수가 서로의 수를 나누어 원하는 수를 얻는 알고리즘을 나타낸다고 하는데, 2개의 자연수 A, B(A > B)에 대해 A를 B로 나눈 나머지를 R이라고 하면 A, B의 최대공약수는 B, R의 최대공약수와 같다. 따라서 B를 R로 나눈 나머지 C를 구하고, 다시 R을 C로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 A, B의 최대공약수가 된다. 위키백과에서 위 설명을 읽었을 때 이해가 완벽하게 되지 않았고.. 어렵다는 생각이 들었는데 예시를 보니 생각보다 간단했다! 위키백과의 예시를 직접 한 단계씩 직접 작성하고 출력해 보면서 이해를 했다. 243, 135의 최대공약수를 찾는다고 할 때 구하는 순서..

DFS/BFS를 알아가기 전에.. 탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정이며 DFS/BFS가 이 알고리즘에 속한다. DFS/BFS를 풀기 위해서 알아야 할 몇 가지 자료구조를 먼저 알아보려고 한다. 여기서 자료구조란 데이터를 표현, 관리, 처리하기 위한 구조이다. 자료구조 중에서 스택과 큐가 가장 기초적인 개념으로 자리잡고 있다. 스택(Stack) 나중에 들어온 데이터가 먼저 삭제되는 후입선출 구조의 자료구조이다. 예전 블로그에서 실행 컨텍스트에 대해 개념을 정리하면서 스택/큐 개념도 함께 정리했는데, 당시 그렸던 그림을 첨부한다. 그림처럼 후입 선출임을 알 수 있다. 이를 코드로 구현하려면 입력은 리스트의 가장 뒤쪽에 데이터를 삽입하는 append(), 출력은 리스트의 가장 뒤쪽에 있는..

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘 즉, 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 "가장 큰 순서대로" 또는 "가장 작은 순서대로"와 같은 기준을 제시해준다. 아래는 책에 제공되어 있는 연습 문제인데, 문제는 검색하면 나와있으니 나는 내가 접근한 방식이나 풀이 위주로 글을 작성했다. [이코테] 실전문제 1: 큰 수의 법칙 처음엔 반복문으로 풀이하려고 접근했다가 문제를 계속 살펴보니 굳이 반복문을 사용하지 않고 풀 수 있을 것 같다는 생각이 들어 중간에 풀이를 한번 갈아엎었다. 가장 큰 수를 만들기 위해서는 숫자 배열 중 첫 번째로 큰 수, 두 번째로 큰 수만 필요하..

복잡도 시간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지 의미 공간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지 의미 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘 시간 복잡도 빅오(Big-O)표기법을 사용 a = 5 b = 7 print(a + b) 위 소스코드의 연산 횟수는 1이므로 시간 복잡도는 상수 시간인 O(1)이 된다. array = [3, 4, 5, 6] summary = 0 for x in array: summary += x print(summary) 위 소스코드는 4개의 데이터를 차례로 4번 더해준다. 즉, 연산 횟수는 N개의 데이터에 비례함으로 시간 복잡도는 선형 시간인 O(N)이 된다. ar..