전체 글 (79) 썸네일형 리스트형 방향 비순환 그래프(DAG, Directed Acyclic Graph) 지금까지 그래프(Graph)란 무엇인지 간략하게 살펴보고 인접행렬과 인접리스트를 통해 그래프를 구현해보기도 하였다. 그리고 그래프를 순환(traversal) 하기위해 방향있는 그래프던 없는 그래프던 똑같이 적용할 수 있는 너비우선탐색(BFS, Breadth First Search) 과 깊이우선탐색(DFS, Depth First Search) 알고리즘도 알아보았다. 이번 시간에는 DAG(Directed Acyclic Graph)에 대해서 알아볼텐데 DAG란 유향 비순환 그래프 or 유향 비사이클 그래프 or 방향 비순환 그래프 or 방향 비사이클 그래프 or 방향성 비사이클 그래프처럼 다양하게 번역되어지는데 핵심은 그래프 간선(에지)에 방향이 있고 처음 출발한 노드(정점) v에서 시작하여 끝내 다시 v로 .. 퀵정렬(Quick Sort) 퀵정렬은 매우 효율적인 정렬 알고리즘이며 데이터 배열을 특정 규칙에 의해 분할 하면서 정렬을 하는 분할정복(Divide & Conquer) 에 기반한다. 분할단계에서는 배열은 다음과 같은 조건이 만족되도록 2개의 부분으로 나누는데 그 중 하나는 지정된 값보다 작은 값들로 다른 하나는 지정된 값보다 큰 값들로 이루어지도록 분할한다. 여기서 지정된 값을 보통 피벗(pivot)이라고 불린다. 즉, 분할되기전 배열에서 임의의 기준값이 될 피벗을 하나 선택한다. 피벗을 배열중에 어떤 놈을 선택할지는 나중에 설명하겠다. 지금은 그냥 배열에 아무값이나 선택한다고 생각하면 된다. 지금은 일단 배열의 맨 끝에 있는 놈을 피벗으로 선택한다. 다음 그림에서 ①번은 아직 정렬되지 않은 배열데이터를 나타내고 ②번은 맨 끝에 있.. 부르트포스(Brute Force) 일반적으로 SW를 개발하면서 결정 문제(decision problem), 탐색 문제(search problem), 카운팅 문제(couting problem), 최적화 문제(optimization problem), 함수형 문제(function problem) 문제등 다양한 문제해결(Problem Solving)이 필요하다. 문제해결을 위해 단순한 자료구조나 알고리즘을 이용하면 되는 경우도 있지만 한개이상의 알고리즘을 복합적으로 사용하여 풀어야 하는 경우도 많이 있다. 부르트포스(Brute Force) 란 위와 같은 다양한 문제해결을 위해 어떤 방식으로 접근할 것인가? 인데 결론 부터 말하면 문제해결을 위해 모든 가능한 경우의 수를 모두 뒤져서 해를 얻는 한마디로 좀 무식한 방법 이다. 대표적으로 어떤 해커.. 백준 4150 - 피보나치 수 (BigInteger) ▷문제 : https://www.acmicpc.net/problem/4150 4150번: 피보나치 수 문제 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력하는 프로그램을 작성하여라. 예제 입력 1 복사 100 예제 출력 1 복사 354224848179261915075 힌트 해당 테스트 데이터의 모든 정답은 1000자를 넘지 않는다. ( f(20) = 6765 이므 www.acmicpc.net Note 피보나치 수를 구하는 알고리즘을 먼저 알아야 하는데 (재귀)피보나치 수열(Fibonacci Sequence) 를 .. 백준 10757 - 큰수 (문자열조작) ▷ 문제 : https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 첫째 줄에 A와 B가 주어진다. (0 0 2 10의.. 백준 9442 - Sort Me (정렬, 룩업테이블) 문제 : https://www.acmicpc.net/problem/9442 9442번: Sort Me The input will contain one or more datasets. Each dataset will start with a line containing an integer n and a string s, where s is a permutation of the English uppercase alphabet, used as the Gorellians' alphabet in the coming year. The next n lines (1 www.acmicpc.net Note Sort Me 문제는 정렬 문제이긴 한데 정렬을 하기위한 비교함수와 문자열 비교함수를 직접 구현해야만 하는 문제이다. .. 백준 2947 - 나무조각 (버블정렬) ▷문제 : https://www.acmicpc.net/problem/2947 2947번: 나무 조각 문제 동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다. 동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치 www.acmicpc.net Note 이 문제는 알고리즘(Algorithm) → 정렬(Sort) → 거품정렬(Bubble Sort) 를 문제로 풀어 쓴 .. 무방향 그래프(Undirected Graph) 구현 그래프(Graph) 란 무엇인지 어느정도 확인을 하였는데 그럼 이런 G = (V,E)로 표현되는 그래프를 프로그래밍에서 어떻게 표현할수 있을까?를 고민해야 한다. 그래프를 프로그래밍에서 표현하기위한 방법은 크게 2가지 방법이 존재하는데 하나는 인접행렬(Adjacency matrix)이고 다른 하나는 인접리스트(Adjacency list)이다. ▲ [출처] https://algorithmtutor.com/Data-Structures/Graph/Graph-Representation-Adjacency-List-and-Matrix/ 여기서는 2가지 모두 살펴볼것이고 인접행렬부터 알아보도록하자. 인접행렬(adjacency matrix) 인접행렬은 그래프를 N * N 행렬(matrix)로 정점과 에지를 표현하기 위.. 이전 1 2 3 4 5 6 7 ··· 10 다음
