티스토리

BSH 코딩 블로그

검색하기

블로그 홈

BSH 코딩 블로그

daily-life-of-bsh.tistory.com/m

BSHwan 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

서로소 집합(Disjoint-set) 서로소 집합 : 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 집합에 속한 하나의 특정 멤버(representative) 를 통해 각 집합들을 구분한다. 상호배타 집합을 표현하는 방법 : 연결리스트, 트리 상호배타 집합 연산 : Make-Set(x), Find-Set(x), Union(x, y) CODE 1. Make-Set(x) void makeSet(int x) { parents[x] = x; } 2. Find-Set(x) int findSet(int x) { if(x == parents[x]) return x; else { parents[x] = findSet(parents[x]); return findSet(parents[x]); } } 3. Union(x, y) vo.. 공감수 0 댓글수 0 2020. 4. 19.
프림 알고리즘 (Prim Algorithm) 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 정점을 하나씩 선택할 때마다 간선을 추가하면서 트리 확장 두 종류의 상호배타집합 정보를 유지 - 트리 정점들(tree-vertices) : MST를 만들기 위해 선택된 정점들 - 비트리 정점들(non-tree vertices) : 선택 되지 않은 정점들 동작과정 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 1, 2 과정을 반복 import java.util.Arrays; import java.util.Scanner; /* 7 11 0 1 2 0 2 2 0 5 8 1 2 1 1 3 19 2 5 5 3 4 7 3 5 11 3 6 15 4 .. 공감수 0 댓글수 0 2020. 4. 19.
크루스칼 알고리즘 (Kruskal Algorithm) 1. 신장트리 : 그래프의 모든 정점과 간선의 부분집합으로 구성되는 트리 2. 최소신장트리(MST) : 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 - 무방향 가중치 그래프 - 그래프의 가중치의 합이 최소여야 한다. - N개의 정점을 가지는 그래프에 대해 반드시 (N-1) 개의 간선을 사용해야 한다. - 사이클을 포함해서는 안된다. 3. Kruskal Algorithm - 탐욕적인 방법을 이용하여 가중그래프(가중치를 간선에 할당한 그래프)의 모든 정점을 최소비용으로 연결하는 최적해를 구하는 것 - 간선을 하나씩 선택해서 MST를 찾는 알고리즘 - 동작과정 ① 그래프의 간선들을 가중치의 오름차순으로 정렬한다. ② 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. a. 가.. 공감수 0 댓글수 0 2020. 4. 12.
순열 (Permutation) SW 역량테스트문제를 풀면서, 완전 탐색 (브루트포스) 문제를 해결할 때 필수적인 개념인 순열에 대해서 정리하려고 합니다. 브루트포스 문제를 만나면 단순 반복문을 통해 탐색하는 문제가 아닌, 재귀와 백트래킹을 통한 순열 또는 조합이 엮인 문제가 많은 것 같습니다. 그래서 순열과 조합에 대한 부분은 반드시 완벽하게 이해하고 문제를 풀어야 합니다. 그림만 통해서 저는 이해하기 어려웠기 때문에 문제와 그림을 통해서 정리해보겠습니다. 순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말합니다. 즉, 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시하기도 합니다. [네이버 지식백과] 순열 [Permutat.. 공감수 0 댓글수 0 2019. 4. 11.
크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘을 공부하기 전에, 스패닝 트리에 대해서 먼저 알아야 한다.span 은 '완전히 덮다' 라는 느낌의 뜻을 가지고 있는 단어이고, 트리는 사이클이 없는 그래프이다.그래서 스패닝 트리는 그래프의 모든 노드를 포함하는 트리이다. 위의 경우에도 스패닝 트리이고, 밑의 경우에도 스패닝 트리이다.하나의 그래프에서 스패닝트리는 여러개 존재할 수 있다.스패닝 트리의 가중치를 합하면 weight를 알 수 있는데, 그래프에서 weight의 값이 최소인 스패닝 트리를최소 스패닝 트리 (Minimum Spanning Tree) 이라고 한다. 위의 그래프에서 표시된 트리가 최소 스패닝 트리이다.크루스칼 알고리즘을 알기 위해서 또 알아야할 개념중에 하나가 Cut Property 라는 것이다.T1과 T2는 서로 다.. 공감수 1 댓글수 0 2019. 3. 9.
다익스트라 알고리즘 (Dijkstra's Algorithm) 최단경로를 구하는 알고리즘인 다익스트라 알고리즘을 공부하고자 한다.다익스트라 알고리즘은 한 점에서 모든 점까지 최단거리를 구하는 알고리즘인데, 가중치가 양수일 때만 사용하는 알고리즘이다.예시에서는 1에서 7까지 도달하는 최단경로를 구한다고 해보자. 먼저 시작정점 1까지는 최단경로 0으로 왔기 때문에 최단경로 0으로 도착했다고 표시한다.그리고 다음 경로로 2와 6으로 갈 수 있는데, 1에서 6으로 가는 방법은1 --> 6 과 1 --> 2 --> 6 두가지가 있다. 1에서 2로 가는 방법은 1 --> 6 --> 2 와 1 --> 2 가 있다. 1 --> 2 --> 6 과 1 --> 6 --> 2 를 구하려면2 --> 6 과 6 --> 2 를 알아야 하는데, 아직 1 --> 6 로 갈지 1 --> 2 로 갈.. 공감수 0 댓글수 0 2019. 3. 9.
최단경로 알고리즘 노드와 노드를 이어주는 간선의 어떤 값을 부여한 것을 간선의 가중치(weight)라고 한다.최단경로 문제는 어떤 노드부터 노드까지 가는 경로의 가중치의 최솟값을 구하는 문제이다. 위의 경로대로 A부터 B까지 가면 1+1+1+2+9 = 14 가 경로의 가중치를 모두 합한 값이다.하지만 이것은 최단경로가 아니므로 그래프에서 최단경로를 구해보면 12로 다음와 같다. 기초 최단경로 알고리즘은 세가지가 있는데, 특징은 위와 같다.플로이드 알고리즘은 모든 정점에서 모든 정점까지 최단거리를 구하지만, 그만큼 시간이 많이걸린다.다익스트라와 벨만포드 알고리즘의 차이점은 가중치의 음수값이 있느냐 없느냐에 따라 나뉜다. 최단경로 문제를 풀 때 중요한 특징은 2가지가 있는데첫번 째는 X까지 최단거리로 가기 위해서는 그 직전의.. 공감수 0 댓글수 0 2019. 3. 9.
넓이우선탐색 (Breadth First Search) BFS는 DFS와 다르게 Queue를 이용하여 그래프를 순회하는 방법이다. 제일 먼저시작하는 노드를 큐에 push하고 색칠한 후에 시작한다. 그 다음에① pop 하는 노드에서 인접한 노드들을 큐에 넣고 색칠한다.② 더이상 넣을 노드들이 없다면 큐에서 pop을 한다.이런식으로 동작한다. 예를 들어 설명해보자. 위에 그림에서 1에서부터 시작하므로1을 큐에 넣고 방문했다고 색칠한다. 1을 pop하고 나면, 이제 1에 인접한 노드들을 확인 한다. 즉 2와 4를 push 하고 방문했다고 색칠한다.현재 큐 상태는 1이 pop되어 있는 상태이고, 큐에 2와 4가 들어가있다.이제 1에 인접한 모든 노드 2와 4를 큐에 넣었으므로 더이상 넣을 노드가 없다.그러므로 현재 큐에서 pop을 해보면 front에 있는 2가 po.. 공감수 0 댓글수 0 2019. 3. 8.
깊이우선탐색 (Depth First Search) DFS는 자기가 방문했던 자취를 기억하는 스택의 특징을 이용하여 인적한 노드부터 차례대로 그래프를 순회하는 방법이다. 주어진 그래프에서 1부터 DFS를 한다고 예시를 들어보자. 여기에서는 더 작은 숫자가 먼저 탐색한다고 가정하면,2와 6중에서 2를 먼저 방문하게 된다. 2에서 다시 DFS를 시행하는데, 방문할 노드가 3과 6이 있으므로더작은 3을 방문하게 되고, 3에서 DFS를 다시 시행하여 4를 방문하고, 4에서 다시 DFS를 해서 5를 방문한다.이제 5에서 더 방문할 곳이 없기 때문에 그 동안 왔던 순서 대로5 --> 4 --> 3--> 2 로 돌아간다. 2로 다시 돌아와서 DFS를 하면 3과 6을 탐색하려고 하는데,3은 이미 방문한 노드이기 때문에 6을 방문한다. 6까지 방문하고 6에서 DFS를 해.. 공감수 4 댓글수 0 2019. 3. 8.
[DP-예제 2] 숫자 만들기 입력 N 과 M 이 주어지면, 1~M 까지 숫자를 더하여 N을 만드는 경우의 수를 구해보자.5와 3 같은 경우는 1~3의 숫자를 임의로 골라 더해서 5를 만드는 경우의 수를 구하는 것이다. 숫자 1~3을 가지고 더해서 5를 만드는 경우의 수를 따지면 위와 같이 13가지가 나온다.이제 문제를 해결하기 위해서 부분 문제를 정의해야 한다.동적 계획법으로 기준을 세우기 위에서 마지막 숫자를 기준으로 3가지로 나눌 수 있다.① 마지막에 숫자 1을 더하는 경우② 마지막에 숫자 2를 더하는 경우③ 마지막에 숫자 3을 더하는 경우 세분류로 나눈 것들이 뜻하는 것은 이렇게 해석 할 수 있다.① 마지막에 숫자 1을 더하는 경우 -> 5에서 1을 뺀 나머지 부분에서 4를 만들어야 한다.② 마지막에 숫자 2를 더하는 경우 -.. 공감수 2 댓글수 0 2019. 3. 4.
[DP-예제 1] 블럭채우기 동적 계획법의 예제인 블록채우기에 대해서 공부하면서 DP를 공부해 보자.세로 길이가 2 이고, 가로 길이가 N 인 블럭에 세로 2, 가로 1의 블럭을 채우는 경우의 수를 구하는 예제이다.쉬운 이해를 위해서 입력 N 이 4일 때(가로 길이가 4) 블럭을 채우는 경우의 수는 5이다. 블럭을 채우는 방법을 보면 이러한 식으로 채울 수 있는 방법이 생각해 보면 5가지가 있다.그런데 이 문제를 코딩으로 어떻게 해결 할 수 있을까? 블럭 채우기 알고리즘을 세울려면 먼저 전체 경우를 어떻게 나눌 것인지 생각해야 한다.이 부분이 동적 계획법에서 가장 생각 해 내기 어려운 부분 문제를 정의하는 과정이다. 모든 경우의 수를 보면 위와 같은데, 어떻게 기준을 세우냐면 가장 마지막에 들어가는 블럭을 본다.그러면 1개가 세로로.. 공감수 2 댓글수 0 2019. 3. 4.
동적 계획법 (Dynamic Programming) 동적 계획법 (Dynamic Programming) 은 각 단계에서 해결해야 할 일련의 문제들이 상호 관련성을 맺고 있을 경우에, 어느 단계에서 하나의 결정이 이루어지면 그 결정은 그 다음 단계의 문제를 결정하는 데 영향을 미치게 되고 그 결과 달성하고자 하는 목표에도 영향을 미치게 되기 때문에 이러한 문제를 해결하기 위해서 필요한 알고리즘이다. 대표적인 예로 [피보나치 수] 가 있다. 피보나치 수는 1 1 2 3 5 8 ... 형식으로 이루어져 있는 수열을 의미하는데,초기값인 첫번째 항과 두번째 항은 1이고, n-2 번째 항과 n-1 번째 항을 더해서 n번째 항을 구한다.n 번째 피보나치 수열을 구하는 코드는 위와 같다. 하지만 피보나치 수를 구하는 알고리즘을 위의 코드 같이 재귀적으로 짜면 문제가 발.. 공감수 1 댓글수 0 2019. 3. 3.
분할정복법 (Divide & conquer) 분할정복법은 문제를 여러 개로 분해하여 해결한 후 풀린 부분 문제들을 거꾸로 조합하여 원래의 문제를 푸는 방식이다.대표적인 예로 합병, 퀵 정렬이 있는데, 합병 정렬에서는 정렬을 반으로 나눠서 숫자를 비교해서 합치는 것이 분할정복법의 원리라고 할 수 있고,퀵정렬도 마찬가지로 pivot 보다 작은 왼쪽부분, pivot 보다 큰 오른쪽 부분을 구해서 pivot 의 자리를 찾아가는 과정이 분할정복법이라 할 수 있 다. 출처 : Algorithm LABS 공감수 0 댓글수 0 2019. 3. 3.
이진탐색 (binary search) (1) 재귀적 구현 이진탐색은 처음부터 끝까지 한개씩 확인하면서 찾는 선형탐색의 시간복잡도 보다 훨씬 빠른 의 시간복잡도를 가지고 있는 함수다. 하지만 이진탐색의 시간복잡도가 의 성능을 가지려면 전제조건이 필요한데, 배열이 정렬 되어있어야 한다. 이진탐색은 정렬되있는 배열에서 중간값을 확인하여 중간값보다 작으면 작은쪽을, 크면 큰쪽에서 다시 이진탐색을 수행하는 탐색이다. 이진탐색의 재귀적과 비재귀적 두가지 방법으로 구현할 수 있는데, 여기에선 재귀적으로 구현을 해볼것이다. 이미지 출처 : https://anster.tistory.com/152 위의 사진에서 만약에 내가 찾는 숫자가 76이라고 가정해보자. 1. 처음에 중간값 47을 찾고 47은 내가 찾는 76보다 작기 때문에 오른쪽에서 다시 이진탐색을 한다. 47보다 작은 .. 공감수 3 댓글수 0 2019. 2. 2.
퀵정렬 (quick sort) 퀵정렬도 합병정렬과 마찬가지로 시간복잡도가 으로 빠르게 정렬할 수 있는 효율적인 정렬이다. 이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=hero1014&logNo=20191727330&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dimages%26cd%3D%26ved%3D2ahUKEwjX0NO0upzgAhUx7GEKHbbxC8AQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252Fhero1014%252F20191727330%26psig%3DAOvVaw2SoIOMtqZXX83.. 공감수 1 댓글수 0 2019. 2. 2.
합병정렬 (merge sort) 선택, 삽입, 버블정렬의 시간 복잡도는 이지만 합병정렬의 시간 복잡도는 으로 더 빠르게 정렬할 수 있다. 합병정렬의 절차를 그림으로 보게 되면 이렇게 된다. 이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=itperson&logNo=220833815418&categoryNo=89&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dimages%26cd%3D%26ved%3D2ahUKEwitzbP5upzgAhWXMt4KHYBVCpQQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252FP.. 공감수 1 댓글수 0 2019. 2. 2.

문의안내

티스토리
로그인
고객센터

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