본문 바로가기

분류 전체보기

 (12)
[알고리즘] 이진 탐색(Binary Search) 탐색(Search) 탐색이란 리스트 내에서 원하는 데이터를 탐색하는 방법을 말한다.데이터를 정렬하는 것 말고도 원하는 데이터를 탐색할 때에도 여러가지 알고리즘을 적용할 수 있다.  탐색법 중에 잘 알려진 것으로는 가장 기본적인 탐색법인 순차 탐색(또는 선형 탐색으로도 알려져 있다), 이번에 알아볼 이진 탐색, 그리고 해시 탐색 등등이 있다. 순차 탐색(Sequential Search) 이진 탐색에 대해 알아보기 전에, 가장 기본이 되는 탐색법인 순차 탐색(Sequential Search), 또는 선형 탐색(Linear Search)에 대해서 알아보자. 쉽게 말해서 순차 탐색법은 리스트의 처음부터 시작해 찾는 데이터가 나올 때까지 다음 데이터로 넘어가며 무식하게 전부 탐색하는 방법이다. 위 그림은 순차 탐..
[알고리즘] 정렬(Sorting) 정렬이란? 정렬은 다량의 데이터를 특정한 기준에 다라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 특정한 기준(주로 오름차순, 내림차순)에 따라 정렬한 후 가공하는 경우가 많기에 다량의 데이터를 다루기 위해서는 필수적으로 다룰 줄 알아야 하는 알고리즘이다. 또한 데이터를 정렬하게 되면  '이진 탐색'(Binary Search)이 가능해진다는 이점이 있다. 정렬 알고리즘의 종류는 셀 수 없이 많다. 데이터를 원하는 순서대로 정렬한다는 목적은 같지만, 그 방식이 완전히 다르기에 각각의 장단점을 가진다. 예를 들면, 버블 정렬(Bubble Sort)은 구현이 매우 간단하지만 비효율적이며, 계수 정렬(Count Sort)은 정렬하고자 하는 데이터가 특정 조건에 부합할 때만 사용할 수 있지만..
[알고리즘] DFS/BFS(Depth/Breadth-First Search) DFS(Depth-First Search)란? DFS는 깊이 우선 탐색이라고도 불리는, 그래프의 가장 깊은 곳까지 우선적으로 파고들어 탐색을 하게 되는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. 그래프는 노드(Node)와 간선(Edge, 종종 정점(Vertex)라고도 불린다)으로 표현되는 일종의 마인드 맵과 같다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하는데, 이는 길 찾기 및 최단경로 알고리즘 등을 구현하기 위한 기본 원리이다.   두 노드가 간선으로 연결되어 있다면 두 노드가 '인접한다'(Adjacent)라고 표현한다. DFS는 스택 자료구조를 사용하는데, 따라서 재귀함수를 통해 간단하게 구현할 수 있다. 구현함에 있어 별도의 모듈이..
[자료구조] 스택(Stack)과 큐(Queue) 스택(Stack)이란? 스택은 데이터 저장 방식의 하나이며, 데이터의 삽입과 삭제 시에 순서의 제약을 받는데, 이는 큐와 마찬가지이다. 스택은 영단어 Stack에 맞게 박스 쌓기에 비유할 수 있다. 박스는 아래에서부터 위로 차곡차곡 쌓고, 치울 때는 위에서부터 아래로 치우게 된다. 스택 또한 마찬가지로, 스택에 데이터를 삽입할 때는 아래에서 위로 삽입하게 되고, 스택에서 데이터를 제거할 때는 위에서 아래로 데이터를 제거하게 된다. 이러한 구조를 선입후출(First In Last Out) 또는 후입선출(Last In First Out)구조라고 한다. 다행히도, Python에서 스택을 구현하기 위해서는 별도의 모듈이 필요 없다.list 자료형의 append() 메소드와 pop() 메소드를 활용하면 자동으로 ..
[알고리즘] 구현(Implementation) 구현이란?구현이란 머릿속에 있는 알고리즘을 실제 소스 코드로 바꾸는 과정이다. 어떤 문제를 풀더라도 소스 코드를 작성하는 과정은 필수이므로 '구현 문제' 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 알고리즘 공부를 통해 문제에 대한 해법을 머릿속으로 떠올릴 수 있었다면, 이제 프로그래밍 언어의 기능들을 십분 활용하여 소스 코드를 작성해야만 한다. 코딩 테스트에서, 알고리즘은 대체로 간단하지만 막상 소스 코드로 쓰려면 어려운 문제들을 구현 유형의 문제라고 부른다. 구현 시 고려해야 할 제약 사항들구현 시 고려해야 할 첫 번째 제약 사항은 바로 메모리이다. C/C++ 등에서는 변수를 선언할 때 자료형을 지정해야 하는데, 지정된 자료형에 따라서 저장할 수 있는 값의 크기가 달라진다. 이 점..
[알고리즘] 시간 복잡도(Time Complexity)와 빅오 표기법(Big-O Notation) 시간 복잡도란? 시간 복잡도는 알고리즘이 실행될 때 입력값의 크기에 따른 연산 횟수를 일종의 함수로 표현한 것이다. 이 때, 실행 시간은 프로세서의 성능과 언어에 따라 천차만별이 되기 때문에 보다 정량적인 비교를 위하여 연산 횟수를 척도로 삼은 것이다. Big-O Notation이란?알고리즘은 그 입력값의 크기에 따른 연산 횟수의 고유의 성장률을 가진다. 알고리즘 실행 결과의 최악의 경우(탐색 알고리즘의 경우, 탐색 대상이 탐색 순서 상 가장 마지막에 위치한 경우)그 성장률에서 가장 큰 영향을 주는 항만 분리해 내어 일종의 함수로 표기한 것이 Big-O Notation이다. 이 때, 가장 큰 영향을 주는 항 앞의 계수는 무시한다. Big-O Notation은 O(n에 대한 시간복잡도)의 꼴으로 표기하며,..
[알고리즘] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘이란? 그리디 알고리즘은 여러 문제 해결 방법 중의 하나이며 그 이름에서 알 수 있듯이, '탐욕적'으로, 지금 당장 좋은 것만을 고르는 방법이다. 그리디 알고리즘은 문제 해결 과정에 포함되는 여러 작업 중, 가장 선호하는 작업부터 가장 덜 선호하는 작업까지 명확한 행동의 우선순위를 세우고, 선호도가 높은 작업을 할 수 있을 경우 "무조건" 선호도가 높은 작업을 수행하며, 선호도가 낮은 작업은 선호도가 높은 작업을 진행할 수 없을때에만 "어쩔 수 없이" 진행하게 된다. 그리디 알고리즘의 장점 문제 해결에 있어 "작업의 우선순위"를 배정하고, 그에 따라 문제를 해결하기 쉬운 경우에 막강한 힘을 발휘한다. 알고리즘을 세우고 문제를 해결할 때, 해결 과정에서 선택이 미치는 영향에 대해서 고민할 필..
[Python] 클래스 클래스에 대해서 세계에서 가장 자주 쓰이는 언어 중 하나인 C언어에는 클래스라는 개념이 존재하지 않는다. 그말인즉슨, 클래스를 사용하지 않고도 원하는 기능을 구현하는데에는 지장이 없다는 것이다. 그럼에도 우리가 클래스를 배우고 사용하는 것은 클래스를 알고, 사용함으로써 얻을 수 있는 이점이 많기 때문이다. 우리는 여지껏 파이선을 공부하면서 int, float 등의 많은 데이터 타입을 배워 왔다. 우리가 다루게 될 클래스는 쉽게 말해서, "사용자 지정 데이터 타입" 이다. 클래스를 만드는 법 클래스는 class name: 으로 만들 수 있다. class는 클래스를 생성하기 위한 예약어이며, name에는 개발자가 원하는 어떤 이름이라도 넣을 수 있다. 하지만 코드를 읽는 사람으로 하여금 이해를 쉽게 하기 위..

티스토리툴바