본문 바로가기

알고리즘, 문제해결/알고리즘, 자료구조21

다이나믹 프로그래밍 프로그래밍은 대개 현실 세계의 문제를 전산적으로 접근하여 풀기 위하여 사용됩니다. 그 중 어떤 문제들은, 컴퓨터를 사용해도 매우 오래 걸리거나 해결하기 어렵기도 합니다. 컴퓨터 역시 현실 세계의 물건인 만큼, 저장 공간이나 연산 속도에 한계가 존재하며, 이러한 한계가 걸림돌이 되는 경우가 분명히 존재합니다. 만약 어떤 알고리즘이 O(2^N)의 시간 복잡도를 가진다면, N의 크기가 커질수록 처리 속도가 비약적으로 증가할 것입니다. 하지만, 메모리를 조금 더 사용하여 같은 문제를 O(N)의 시간 복잡도로 해결할 수 있다면, 이는 매우 효율적인 방법이 될 수 있습니다. 다이나믹 프로그래밍 (dynamic programming) 은 이렇게 연산 속도를 대폭 줄일 수 있는 대표적인 방법입니다. 다이나믹 프로그래밍.. 2021. 2. 5.
이진 탐색 탐색이라 함은, 데이터의 집합 중에서 원하는 값을 찾는 것을 의미합니다. 오늘 다루어 볼 내용은 이진 탐색 (binary serach)인데, 이에 앞서 가장 기본적인 탐색 방법인 순차 탐색을 다루고자 합니다. 순차 탐색 순차 탐색 (sequential search)는 배열 내의 특정 데이터를 찾기 위해 앞에서부터 순차적으로 확인하는 방법입니다. 정렬되지 않은 배열에서 데이터를 찾을 때, 시간만 충분하다면 순차 탐색이 좋은 방법이 될 수 있습니다. 'Carrot' 이라는 문자열을 찾는 과정입니다. 파란색은 현재 'Carrot'와 비교하는 문자열, 빨간색은 이미 비교하였으며 일치하지 않은 문자열, 초록색은 목표로 하는 문자열입니다. 첫 번째 문자열 'Apple', 두 번째 문자열 'Banana'는 일치하지 .. 2021. 2. 4.
정렬 정렬은 컴퓨터과학 분야에서 광범위하게 사용되는 개념입니다. 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미하는데, 오름차순, 내림차순, 등등 상황에 따른 여러 특정한 기준이 존재합니다. 다양한 정렬 알고리즘이 존재하며, 각각 장점과 단점을 가지고 있습니다. 이 중 상황에 맞는 효율적인 알고리즘을 고르는 것이 중요합니다. 다음과 같은 숫자가 있다고 생각합시다: 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 우리는 위 숫자들을 오름차순으로 정렬하고 싶습니다. 어떻게 진행할까요? 전체 숫자를 슥 보고, 숫자들이 0~9 사이의 숫자들임을 파악한 후, 0부터 차례대로 나열할 것입니다. 하지만 컴퓨터가 정렬을 할 때도 이런 방법이 효율적일까요? 또, 데이터가 수백, 수천만 개가 있다면 이런 방법이 .. 2021. 2. 4.
DFS/BFS DFS/BFS를 이용하여 푸는 문제는 코딩 테스트에서 흔히 나오는 유형 중 하나입니다. 알고리즘 및 자료구조에서 탐색 (search) 란, 많은 양의 데이터 중에서 원하는 특정 데이터를 찾는 과정을 의미합니다. DFS는 depth-first search, 즉 깊이 우선 탐색이라고 불리며, BFS는 breadth-first search, 즉 너비 우선 탐색이라고 불립니다. 두 방법 모두 이름에서 알 수 있듯 탐색 (search)를 수행하는 알고리즘입니다. 이를 이해하기 위해서는 먼저 stack과 queue, 그리고 재귀 함수에 대한 이해가 선행되어야 합니다. 이 글에서는 해당 내용들을 전부 알고 있다고 전제하겠습니다. DFS와 BFS는 모두 그래프 자료구조를 탐색할 떄 사용하는 알고리즘입니다. 그래프에 대.. 2021. 2. 2.
구현 코딩 테스트 및 온라인 저지 사이트에서 자주 접하게 되는 문제 유형들 중 하나가 구현 문제입니다. 구현 문제란, 머릿속에 있는 알고리즘을 코드로 옮기는 과정을 의미합니다. 엄밀히 말하자면 모든 문제가 구현 문제인 셈입니다. 구체적으로, 구현 문제는 프로그래밍 언어의 기본 문법구조와 자료구조를 이용하여, 특정 문제를 해결하는 문제입니다. 몇 개의 예시를 들면 다음과 같습니다: 브론즈 5 - 별 찍기 - 1: www.acmicpc.net/problem/2438 골드 5 - 빗물: www.acmicpc.net/problem/14719 골드 4 - 아기 상어: www.acmicpc.net/problem/16236 (삼성전자 기출 문제) 골드 2 - 2048 (Easy): www.acmicpc.net/proble.. 2021. 2. 1.
그리디 그리디 (Greedy Method) 알고리즘에 대해 다루어보고자 합니다. Greedy는 한국어로 번역하여 탐욕법, 또는 욕심쟁이 알고리즘이라고도 합니다. 그리디 알고리즘이라고도 하는데, 개인적으로 알고리즘보다는 방법 (method)이 더 어울리는 표현이라고 생각합니다. 이하 '그리디 알고리즘' 이라고 표현을 통일하겠습니다. 그리디 알고리즘은 이름에서 알 수 있듯, 단순하게 탐욕적으로 문제를 해결하는 방법을 의미합니다. 즉, 지금 당장 현재 상황에 가장 좋은 선택지를 고르는 방법을 뜻합니다. 중요한 점은 이 선택이 추후에 미칠 영향에 대해서는 고려하지 않는다는 점입니다. 따라서 최적해를 보장하지는 않습니다. 그리디 알고리즘은 그 의미가 매우 넓습니다. 두루뭉실하게 '현재 가장 좋은 선택지를 고른다'고 뜻이.. 2021. 1. 30.

티스토리툴바