알고리즘 온라인 저지 (48) 썸네일형 리스트형 알고리즘 : 이진 탐색 (=이분 탐색, binary search) 이진 탐색은 정렬이 되어있는 N개의 데이터를 대상으로 log(N) 시간 탐색을 할 수 있는 알고리즘이다. 이진 탐색의 대상은 트리(특별히 이진 탐색을 위한 트리를 이진 탐색 트리, binary search tree라고 부른다.)가 될 수도 있고. 배열이 될 수 도 있다. (이경우 배열은 비교하기 위한 기준에 의해 정렬되어있어야 한다.) 심지어는 임의의 정수 영역에 대한 이진 탐색을 수행할 수도 있다. 만약 정렬이 되어있지 않으면 이진 탐색이 불가능하기 때문에, 이진 탐색 트리, 수 영역에 대한 이진 탐색이 아니라면 탐색의 대상을 정렬하는 행위가 선행되어야 한다. (이진 탐색 트리는 삽입 시점에서 정렬을 하면서 삽입을 한다, 수 영역은 개념적으로 정렬이 되어있다.) 포스팅의 예시는 배열을 대상으로 진행하며.. 알고리즘 : 깊이 우선 탐색(DFS) 우선 그래프, 트리, 스택 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는 것이 좋다. 더보기 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 그래프 (graph) 자료구조 그래프 (graph) 그래프는 입력된 자료들을 특정한 규칙을 이용해 관계를 맺어 줄 수 있는 형태의 자료구조이다. 예를 들면 사람들의 지인 관계는 그래프로 나타내기 좋은 형태이다. 그래프는 다양한 방법으로 dev-game-standalone.tistory.com 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 트리 (tree) 자료구조 트리 (tree) 트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가.. 알고리즘 : 너비 우선 탐색(BFS) 우선 그래프, 트리, 큐 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는 것이 좋다. 더보기 자료구조 그래프 (graph) 그래프는 입력된 자료들을 특정한 규칙을 이용해 관계를 맺어 줄 수 있는 형태의 자료구조이다. 예를 들면 사람들의 지인 관계는 그래프로 나타내기 좋은 형태이다. 그래프는 다양한 방법으로 dev-game-standalone.tistory.com 자료구조 트리 (tree) 트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가 추가된 자료구조이다. 나무를 뒤집어 놓은 것과 비슷하게 생겼다 하여 이름 붙여진 트리는, 알고 dev-game-standalone.tistory.com 자료구조 큐 (queue) 큐는 선입 선출(First.. 자료구조 트리 (tree) 트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가 추가된 자료구조이다. 나무를 뒤집어 놓은 것과 비슷하게 생겼다 하여 이름 붙여진 트리는, 알고리즘 문제를 풀 때 단골로 등장하는 자료구조이다. 다음은 이진트리를 이용해 정렬된 숫자들을 탐색하는 이진 탐색 트리의 예시이다. 위에서 언급했듯 트리는 그래프의 일종이므로 그래프의 특성을 공유한다. 거기에 추가되는 노드 간 부모 - 자식 관계가 더해지는 것이 트리의 특징이다. 트리는 그래프 이상의 다양한 종류로 분류된다. 종류를 분류할 기준을 크게 3가지로 나누어 적어보았다. 자식의 개수별 분류 트리 : 자식의 개수에 대한 제한이 없는 트리 이진트리 : 모든 노드에 대하여 자식의 개수가 2개 이하인 트리 N진 .. 자료구조 그래프 (graph) 그래프는 입력된 자료들을 특정한 규칙을 이용해 관계를 맺어 줄 수 있는 형태의 자료구조이다. 예를 들면 사람들의 지인 관계는 그래프로 나타내기 좋은 형태이다. 그래프는 다양한 방법으로 구현할 수 있기 때문에, 어느 한 가지 구현 방식만이 그래프라고 생각하지 않는 것이 좋다. 대표적으로 사용되는 그래프 구현 방식은 class, struct 등을 이용하여 정의한 노드와 포인터를 이용한 방식 (주로 c++) 배열을 이용한 방식 (인접 행렬, 세그먼트 트리 등등) 연결 리스트를 이용한 방식 (인접 리스트, map 자료구조를 이용한 방식 등등) 등이 있다. 그래프를 사용하는 방법 또한 다양한 방법이 있기 때문에, 어느 한 가지 사용법만이 그래프 자료구조를 이용했다고 생각하지 않는 것이 좋다. 대표적으로 그래프 구.. 자료구조 큐 (queue) 큐는 선입 선출(First In First Out : FIFO) 형태의 자료구조이다. 큐는 들어온 순서를 이용하는 기능에서 적절하게 사용할 수 있다. 더보기 들어온 순서를 이용하기 위해 큐를 이용한 예시 : 2022.07.15 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 알고리즘 : 너비 우선 탐색(BFS) 알고리즘 : 너비 우선 탐색(BFS) 우선 그래프, 트리, 큐 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는것이 좋다. 더보기 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 그래프 (graph) 자료구 dev-game-standalone.tistory.com 선착순 대기열 기능이 좋은 예시이다. 어떠한 서비스를 이용하고자 하는 사용자 4명이 .. 자료구조 스택 (stack) 스택은 선입 후출(First In Last Out : FILO) 형태의 자료구조이다. 스택은 직전 단계로 돌아가는 기능이 필요한 경우 적절하게 사용할 수 있다. 인터넷 브라우저의 뒤로 가기 기능이 좋은 예시이다. 인터넷을 이용하는 과정에서 1번 페이지에서 2번 페이지로, 2번에서 3번, 3번에서 4번 페이지 순으로 이동했다고 가정해보자. 4번 페이지에서 뒤로 가기 버튼을 누르면 3번 페이지로 이동해야 한다. 마찬가지로 3번 페이지에서 한번 더 뒤로 가기 버튼을 누르면 2번 페이지로 이동해야 한다. 위의 예시처럼 이전 상황을 복원해야 하는 상황에서 스택은 좋은 선택이 될 수 있다. 스택은 대부분의 프로그래밍 언어에서 라이브러리로 지원되고 있다. C++ / Java의 경우 push(삽입), pop(삭제), .. BOJ 7579번 앱 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net DP를 이용한 문제이다. 일반적으로 이러한 문제를 만나면, 확보되는 메모리를 인덱스로한다. 그렇게 해야 DP 테이블을 구한 뒤 문제에서 요구하는 인덱스의 값을 바로 출력 해 줄 수 있기 때문이다. 그런데 이 문제의 경우에는 확보할 메모리의 범위가 너무 넓다 (1 ~ 10,000,000) 비용의 범위가 (0 ~ 10,000) 인 것을 감안하면 결국 2byte 이상의 변수를 이용해야 하는데 그렇게되면 DP 테이블의 크기만 거의 20MB 가 되기 때문에 꺼려진다. (msvc.. 이전 1 2 3 4 5 6 다음
