티스토리

popo story

검색하기

블로그 홈

popo story

12yeonii.tistory.com/m

마이구미포포 님의 블로그입니다.

구독자: 9

방명록 방문하기

주요 글 목록

[알고리즘] 힙 정렬 (Heap Sort) 이진 힙 (Binary Heap) : 힙 조건을 만족하는 완전 이진 트리 : 힙 조건 : 각 노드의 우선순위(priority)가 자식 노드의 우선 순위보다 높다 – 최대 힙(Maximum Heap): 가장 큰 값이 루트에 저장 – 최소 힙(minimum Heap): 가장 작은 값이 루트에 저장 ex) n개의 노드를 가진 힙 – 완전 이진 트리이므로, 힙의 높이가 log2n이며, 노드들을 빈 공간 없이 배열에 저장 힙의 노드 관계  힙에서 부모와 자식의 관계 – A[i]의 부모 = A[i/2] (단, i가 홀수이면 i/2에서 정수 부분만) – A[i]의 왼쪽 자식 = A[2i] – A[i]의 오른쪽 자식= A[2i+1] 힙 정렬 (Heap Sort) 루트에 가장 큰 수가 있는 최대 힙을 정렬한다고 하자 .. 공감수 0 댓글수 0 2022. 6. 4.
[알고리즘] 쉘 정렬(Shell Sort) 알고리즘 버블정렬이나 삽입정렬은 이웃하는 원소의 자리바꿈이다 하지만 쉘 정렬은 그룹화를 시켜 정렬하는 방식으로, 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 이동시키고 앞부분의 큰 숫자는 뒷부분으로 이동시킨다 예를 들어 숫자가 이렇게 있다고 하자 이 배열을 간격 5로 그룹화를 하면 이렇게 그룹이 지어진다, 그럼 여기서 이제 그룹1 안에서 삽입정렬, 그룹2 안에서 삽입정렬을 해주면된다 그룹별 정렬을 하고 나면 이렇게 정렬이 되고, 5의 갭차이로 그룹을 나누었으니 다음에는 3의 갭차이로 그룹을 나누어 정렬한다 그리고 마지막에는 1의 갭차이로 그룹을 나누어 정렬한다 (그냥 삽입정렬과 동일) 알고리즘 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A 1. for each gap h = [ h0>h1>.... 공감수 0 댓글수 0 2022. 6. 4.
[이취코] Ch09-3. 최단경로 / 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) - 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우에 사용할 수 있는 알고리즘 - 2차원 리스트에 '최단 거리' 정보를 이용한다 - 다이나믹 프로그래밍 플로이드 워셜 알고리즘은 단계마다 해당 노드를 거쳐가는 경우를 고려해 최단경로를 비교한다 예시를 들어 말하자면 A, 1, B 노드가 있고 A에서 B까지 가는 최단 경로를 구한다고 할 때 노드 1을 거쳐가는 경우(A-1-B)와 A에서 B로 가는(A-B) 경로를 비교해 더 작은 것을 최단 경로로 선택하는 것이다 점화식으로 표현하자면, a에서 b까지 가는 경우의 최단 거리는 'a에서 바로 b로 가는 경우' 와 '노드 k를 거쳐 가는 경우' 중 작은 값이다 예시를 통해 구체적.. 공감수 0 댓글수 0 2022. 5. 25.
[이취코] ch06-4. 계수 정렬 (Count Sort) 계수 정렬 (Count Sort) : 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 계수 정렬은 다른 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 알고리즘)이 아니다 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다 예시를 통해서 알아보도록 하자 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 초기 데이터가 이렇게 있다고 해보자 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 담길 수 있는 리스트를 선언한다 여기서 가장 큰 데이터가 9 이고 가장 작은 데이터가 0 이므로 모두 담을 수 있는 크기가 10 인 리스트를 선언하면 된다 계수정렬에서 데이터의 값은 새로 선언한 리스트의 인.. 공감수 0 댓글수 0 2022. 5. 3.
[알고리즘] 배낭 문제 (Knapsack Problem) - 0-1 배낭문제 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 4. 20.
[알고리즘] 최소신장트리, 프림(Prim) 알고리즘 신장 트리 신장트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다 이 때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다 따라서 이러한 그래프를 신장 트리라고 부르는 것이다 신장트리 예시는 다음과 같다 최소 신장 트리 우리는 다양한 문제 상황에서 가능한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 설치한다고 생각해보자 2개의 도시 A,B를 선택했을 때, 도시 A에서 B로 이동하는 경로가 반드시 존재해야한다 모든 도시를 연결할 때 최소한의 비용을 들이려면 어떻게 알고리즘을 이용해야할까? 예를 들어 왼쪽 그래프가 있다고 생각해보자 3.. 공감수 0 댓글수 0 2022. 4. 19.
[알고리즘] 최소신장트리, 크루스칼(Kruskal) 알고리즘 신장 트리 신장트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다 이 때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다 따라서 이러한 그래프를 신장 트리라고 부르는 것이다 신장트리 예시는 다음과 같다 최소 신장 트리 우리는 다양한 문제 상황에서 가능한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 설치한다고 생각해보자 2개의 도시 A,B를 선택했을 때, 도시 A에서 B로 이동하는 경로가 반드시 존재해야한다 모든 도시를 연결할 때 최소한의 비용을 들이려면 어떻게 알고리즘을 이용해야할까? 예를 들어 왼쪽 그래프가 있다고 생각해보자 3.. 공감수 0 댓글수 0 2022. 4. 19.
[알고리즘] 작업 스케줄링 (Job Scheduling) 문제 작업 스케줄링 (Job Scheduling) 문제 • 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 • 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다. ex) 발표= ‘작업’, 강의실= ‘기계’ 작업 스케줄링 문제에 주어진 문제 요소 • 작업의 수 > 입력의 크기이므로 알고리즘을 고안하기 위해 고려되어야 하는 직접적인 요소는 아니다. • 각 작업의 시작시간과 종료시간 • 작업의 길이 > 작업의 시작시간과 종료시간은 정해져 있으므로 작업의 길이도 주어진 것 시작시간, 종료시간, 작업 길이에 대한 그리디 알고리즘 • 빠른 시작시간 작업 우선 (Earliest start time first) 배정 • 빠른 종료시간 작업 우선 (Earliest finish time.. 공감수 0 댓글수 0 2022. 4. 18.
[알고리즘] 집합 커버 문제 (Set Cover) 그리디 알고리즘을 이용해 푸는 문제 중 하나인 집합 커버 문제를 보자 - n개의 원소를 가진 전체 집합 U - U의 부분집합 Si 를 원소로 갖는 집합 F - F의 원소들인 Si 를 합집합하여 U가 되는 Si 의 최소 개수를 찾아야함 예를 들어 생각해보자 [신도시 학교 배치] - 10개의 마을이 신도시에 만들어질 계획 - 다음 조건을 만족하는 학교의 위치 선정을 해야함 º 학교는 마을에 위치해야함 º 등교 거리는 걸어서 15분 이내 - 어느 마을에 학교를 신설해야할까? - 2번 마을에 만들면 마을 1, 3, 4, 8 커버 - 6번 마을에 만들면 마을 5, 7, 9, 10 커버 > 전체 마을이 커버됨 > 최소 마을 개수 : 2개 이걸 어떻게 집합 커버 문제로 풀 수 있을까? U = {1, 2, 3, 4, .. 공감수 0 댓글수 0 2022. 4. 18.
[알고리즘] 배낭 문제 (Knapsack Problem) - 부분 배낭 문제 (Fractional Knapsack) 배낭 문제는 한정된 배낭에 무게와 가치가 정해져있는 물건을 담을 때 담은 물건이 최대의 가치를 갖도록 물건을 정하는 문제이다 - n개의 물건 집합 S={1, 2, 3, 4,..., n} (물건번호) - 배낭의 최대 무게 M - 물건 i의 무게 w={w1, w2, w3,..., wi} - 물건 i의 이윤 Pi 이렇게 있을 때 - ∑ wi*xi ≤ M (물건의 무게 총합 ≤ 배낭의 최대 무게) - ∑ Pi*xi => 최대 (물건 총합 가치 최대) 여야한다 여기서 xi의 범위에 따라 구현 방법이 달라지는데 두 가지 방법이 있다 1) xi 의 값이 0 ≤ xi ≤ 1 : 부분 배낭 문제 xi 가 1/3이라면 물건을 1/3 만큼 담는다는 얘기이다 - 그리디 알고리즘을 이용한다 (0-1 배낭문제보다 비교적 수월하다.. 공감수 0 댓글수 0 2022. 4. 18.
[이취코] ch09-2. 최단 경로 / 다익스트라 알고리즘 (힙 이용) 앞에서 리스트로 순차 탐색해 다익스트림을 구현하는 방법을 알아보았다 하지만 그렇게 구현하는 것보다 더 효율적으로 다익스트림 알고리즘을 구현할 수 있는 방법이있다 바로 힙 자료구조를 이용하는 것이다 힙(heap) 자료구조 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나다 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다 스택, 큐, 우선순위 큐를 비교하면 자료구조 추출되는 데이터 스택 (Stack) 가장 나중에 삽입된 데이터 큐 (Queue) 가장 먼저 삽입된 데이터 우선순위 큐 (Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐는 c++에서 라이브러리를 제공하므로, 라이브러리를 그대로 사용하면 된다 단, c++에서는 최대.. 공감수 0 댓글수 0 2022. 4. 18.
[이취코] Ch09-1. 최단경로 / 다익스트라 알고리즘 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다 '길 찾기' 문제라고도 불리고, 최단 경로 알고리즘 유형에는 다양한 종류가 있는데 상황에 맞는 효율적인 알고리즘이 이미 정립되어있다 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등 다양한 사례가 존재한다 최단 경로 문제는 보통 그래프를 이용해서 푸는데, 그래프에서 '노드' 는 각 지점을 의미하고 '간선' 은 지점 사이 연결 도로를 의미한다 최단 거리 알고리즘 중 많이 사용되는 알고리즘은 다익스트라 알고리즘이다 다익스트라 알고리즘에 대해 공부해보자 다익스트라 알고리즘은 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로.. 공감수 0 댓글수 0 2022. 4. 18.
[알고리즘] 합병(병합)정렬, Merge Sort 개념 및 구현 합병 정렬은 분할 정복 알고리즘에 속한다 * 분할 정복 알고리즘 : 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 합병 정렬은 n개의 숫자를 n/2개씩 2개의 부분 문제로 분할하여 1개가 남을때까지 분할하고 분할한 숫자들을 다시 합병하며 정렬한다 즉, 작은 문제로 쪼개고 다시 조합한다는 것이다 - n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할 - 각각의 부분 문제를 순환으로 합병 정렬 - 2개의 정렬된 부분을 합병하여 정렬(정복) 예를 들어 이런 배열이 있다고 하자 그 후 이 배열을 계속 2로 나누어 하나가 남을때까지 쪼갠다 이렇게 하나 남을 때까지 배열을 모두 쪼개고 다시 합칠 때 정렬을 해준다 그림으로 보면 합병 정렬의 원리가 더 이해가 잘 될것이다 합병 정렬의 시간 복잡.. 공감수 0 댓글수 0 2022. 4. 13.
[이취코] ch06-3. 퀵 정렬 퀵 정렬은 매우 많이 사용되는 알고리즘으로 속도가 매우 빠르다 퀵 정렬과 합병(병합) 정렬은 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도하다 퀵정렬? 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식이다 퀵정렬은 분할정복 알고리즘으로 분류되고, 합병정렬과 다른점은 각 부분 문제의 크기가 일정하지 않다는 것이다 (합병정렬은 일정 분할이다) 퀵 정렬에서는 피벗(pivot)이 사용된다 피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'이다 퀵 정렬을 수행하기전에는 피벗을 어떻게 설정할것인지 반드시 명시해야한다 피벗을 설정하는 방식에는 여러가지가 있지만 우선 대표적인 호어 분할(Hoare Partition)방식을 기준으로 이해해보자 호어분할방식 - .. 공감수 0 댓글수 0 2022. 3. 30.
[이취코] ch06-2. 삽입 정렬 (Insertion Sort) 삽입정렬? 특정한 데이터를 적절한 위치에 '삽입'한다 선택정렬보다 실행 시간 측면에서 더 효율적이고 선택정렬에 비해 구현 난이도가 높은편이다 특히 삽입정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다 삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다 그림으로 보면 이해가 더 쉬울것이니 그림으로 살펴보도록 하자 초기 데이터가 다음과 같이 있다 삽입정렬은 두번째 데이터부터 시작한다 첫번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다 (1) 첫번째 데이터 7은 이미 그 자체로 정렬되어 있다고 생각하고, 두번째 .. 공감수 0 댓글수 0 2022. 3. 30.
[이취코] ch06-1. 선택정렬 (Selection Sort) 선택정렬? 데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는과정을 반복하는 것이다 이 방법은 가장 원시적으로, '매번 가장 작은 것을 선택한다'는 의미에서 선택정렬이다 정렬되어있지 않은 초기 데이터를 선택정렬로 정렬해보자 7 5 9 0 3 1 6 2 4 8 * 주황: 정렬되지 않은 데이터 중 가장 작은 데이터 * 초록: 가장 작은 데이터와 자리가 교체되는 맨 앞에 있던 데이터 (1) 가장 작은 데이터 0을 선택하고 맨 앞에 있는 데이터 7과 바꿔준다 → 0 5 9 7 3 1 6 2 4 8 (2) 정렬되지 않은 남은 데이터 중 가장 작은 데이터 1을 선택하고 맨 앞 데이터 5와 자리를 바꿔준다 → 0.. 공감수 0 댓글수 0 2022. 3. 30.
[이취코] ch05. 탐색 알고리즘 DFS/BFS 탐색 알고리즘을 알기 전에 먼저 그래프의 기본 구조를 알아야한다 그래프는 노드(Node)와 간선(edge)로 표현되며, 이 때 노드를 정점(Vertex)라고도 말한다. 간선으로 연결되어 있는 노드들은 "인접한 노드" 라고 표현한다 프로그래밍에서 그래프를 표현하는 방식은 2가지이다. 모두 알고있도록 하자 (1) 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 이렇게 연결된 노드들을 행렬로 표현하고, 연결되어 있지 않은 노드들은 무한의 비용이라고 작성한다 코드로 인접행렬을 작성하면 #include #define INF 999999999 // 무한의 비용 선언 using namespace std; // 2차원 리스트를 이용해 인접 행렬 표현 int graph[.. 공감수 0 댓글수 0 2022. 3. 28.
[이취코] ch05. 자료구조 기초 (스택/큐/재귀함수) 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 탐색 알고리즘을 이해하기 위해선 기본 자료구조인 스택, 큐에 대한 이해가 있어야한다. 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 - 삽입(Push) : 데이터를 삽입한다 - 삭제(Pop) : 데이터를 삭제한다. - 오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 (저장공간을 벗어나 데이터가 넘쳐흐를 때) - 언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 발생 [스택] 스택은 박스 쌓기로 생각하면 된다. 아래부터 위로 쌓는 방식 / 위에서부터 아래로 내리는 방식.. 공감수 0 댓글수 0 2022. 3. 22.
[이취코] ch04. 구현 유형 문제 풀이 #1 시각 [문제] - 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제 - 완전 탐색 (Brute Forcing) 문제 유형 -> 가능한 경우의 수를 모두 검사해보는 탐색 방법 [코드] cpp #include using namespace std; int h, cnt; // 특정한 시각 안에 '3'이 포함되어 있는지의 여부 bool check(int h, int m, int s) { if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3) return true; return false; } int main(void) { // H를 입력받기 cin >> h; for (int i = 0; i = 1 && nextRo.. 공감수 0 댓글수 0 2022. 3. 15.
[이취코] 04. 구현 유형 개요 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 * 알고리즘 대회에서 구현 유형의 문제란? - 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 - 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제 - 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제 - 적절한 라이브러리를 찾아서 사용해야 하는 문제 [예시] 1. 행렬 - 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용 2. 방향벡터 - 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용 [대표문제 - 상하좌우] - 요구사항대로 충실히 구현하면 되는 문제 - 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에.. 공감수 0 댓글수 0 2022. 3. 15.
[이취코] 그리디 알고리즘 그리디(Greedy) 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 ex) 거스름돈 Q. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하여라 A. 가장 큰 화폐 단위부터 돈을 거슬러 주기 - 그리디 알고리즘의 정당성 대부분의 그리디 알고리즘 문제는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 공감수 0 댓글수 0 2022. 3. 8.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.