알고리즘

# 그리디(Greedy) 알고리즘 정의 그리디 기법(Greedy method)은 탐욕적 기법이라고도 한다. 모든 경우를 고려해 보고 가장 좋은 답을 찾는 것이 아니라 '그 순간에 최적'이라고 생각되는 답을 선택한다. 미래를 고려하지 않고, 현재 가장 저렴한 선택 or 현재 가장 가치있는 선택 or 가장 빠른 선택을 하는 것이다. 예를 들어, 아래 그림에서 시작 지점에서 가장 큰 수를 구하는 문제일 경우 가장 좋은 path는 6-128이지만, 그리디 알고리즘을 사용하면 17-23을 서택하게 된다. 이런 결과가 나오는 이유는 그리디 알고리즘은 현재 상황에서 가장 좋은 것을 선택하기에 이런 path가 나온다 # 그리디(Greedy) 조건 그리디 알고리즘은 항상 최적의 해를 찾는 것은 아니다. 현재의 최적 해 ..

그래프 순회는 하나의 정점에서 시작해 그래프의 모든 정점을 한 번씩 방문하는 작업을 말한다. 그래프의 정점들을 순회하는 체계적인 방법에는 깊이 우선 탐색과 너비 우선 탐색이 있다. # 깊이 우선 탐색(DFS: Depth First Search) 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향을 다시 탐색한다. 이것은 이진 트리의 전위순회와 비슷한데, 위 그림처럼 A-B-D-E-C-F의 순서대로 탐색이 진행된다. # 깊이 우선 탐색 진행 방법 시작 정점에서 한 방향으로 갈 수 있는 곳까지 깊이 탐색을 진행하다가, 더 이상 갈 곳이 없으면 가장 최근에 만났던 갈림길 정점으로 되돌아온다. 갈림길로 돌아와서는 가 보지 않은 다른 방향의 간선으로 탐색을 ..

# 함수 실행 시간(running time) 계산하는 방법 우선 실행 시간 계산을 위해 단순화해야하는 것이 있다. 실행 시간의 개념을 흔히 우리가 라는 시간적인 개념이 아닌, 함수나 알고리즘 수행에 필요한 스텝(step) 수라고 정의해야 한다. 이때 스텝 수는 각 코드 라인마다 고정적으로 정해져 있다(constant)고 해야한다. # 시간 복잡도란? 시간 복잡도는 n개의 입력 데이터에 대해 알고리즘이 문제를 해결하는데에 얼만큼의 시간이 걸리는지 나타내는 것. 일반적으로 시간 복잡도를 나타내기 위해 점근적 표기법(asymptotic notation)을 사용한다. 점근적 표기법이란, 중요하지 않은 상수와 계수들을 제거해 알고리즘의 실행 시간에서 중요한 성장률에 집중하는 방법을 의미함 점근적이라는 의미는 가장..

테이블이 킷값을 기준으로 정렬되어 있다면 이진 탐색(binary search)이라는 보다 효율적인 알고리즘을 사용할 수 있다. 이것은 한 번 비교할 때마다 탐색 범위가 절반으로 줄어들기 때문에 '이진'이란 이름이 붙었다. 테이블의 모든 레코드가 킷값의 오름차순으로 정렬되어 있다고 가정해보자. 이진 탐색은 먼저 테이블의 중앙에 있는 레코드를 탐색 키와 비교한다. 1. 만약 중앙 레코드의 킷값이 탐색 키와 같으면 탐색은 성공한 것이고, 중앙 레코드의 위치(인덱스)를 반환하면 된다. 2. 중앙 레코드가 탐색 키보다 크면 그보다 오른쪽에 있는 모든 레코드는 탐색 키보다 크므로 더는 탐색할 필요가 없다. 3. 중앙 레코드가 탐색 키보다 작으면 오른쪽만 탐색하면 된다. 이렇게 이진 탐색에서는 단계마다 검색해야 할 ..

자료들이 뒤섞이고 잘 정리되어 있지 않다면 원하는 자료를 빨리 찾기 쉽지 않을 것이다. 만약 자료들이 일정한 규칙에 따라 잘 정리되어 있으면 훨씬 효율적인 탐색이 가능할 것이다. 결국 탐색 알고리즘은 자료들이 어떻게 정리되어 있는가에 많은 영향을 받는다. 이진 탐색 방법에 대해 알아보자! # 탐색이란? 사람들은 항상 무언가를 찾아 헤맨다. 입고 나갈 옷을 찾거나 점심 식사를 위해 맛집을 찾고, 여행에서 찍은 사진을 검색한다. 이것은 컴퓨터에서도 마찬가지이다. 탐색은 컴퓨터에서 가장 흔한 작업의 하나이고. 많은 시간이 요구되기 때문에 효율적인 탐색은 매우 중요하다. 탐색은 데이터의 집합에서 원하는 조건을 만족하는 데이터를 찾는 작업이다. 탐색을 위한 대상을 보통 레코드(record)라 하고, 이러한 레코드..

📍1. 스택(Stack) 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 따라서 가장 마지막에 들어온 자료가 가장 먼저 삭제되는 구조이다. 스택은 정해진 방향으로만 쌓을 수 있어, top으로 정한 곳을 통해서만 접근할 수 있다. - First In, Last Out 구조(후입선출) 👉 스택(Stack)이 사용되는 예시 - 웹 브라우저 방문기록(뒤로가기) - 실행취소(cmd + z) 💻 스택을 활용한 문제풀이 (Javascript) https://www.acmicpc.net/problem/10828 이 문제는 시간초과 때문에 애를 먹었다.. [내 답안] 을 보면 console.log가 주석처리 되어 있는걸 볼 수 있는데, 이게 초기 코드였고 계속 시간초과가 발생했다. 그래서 출력할 답을 담을 배열인 re..