Twinparadox Factory

깊이 우선 탐색과 너비 우선 탐색에 대해 간단하게 비교하여 정리하고자 한다. 두 알고리즘은 생각보다 알고리즘 문제 풀이에서 많이 볼 수 있고, 각각의 응용 방식을 통해 나오는 코딩 테스트 문제가 많기 때문에 참고해두는 것이 좋고, 기본적인 구현 방식은 알고 접근하는 것이 좋다. 기본적인 구현 코드는 백준 온라인 저지의 1260번 DFS와 BFS 을 구현하는 코드이다. DFS(Depth-First Search) Stack으로 구현할 수 있고, 함수 호출도 Stack처럼 이뤄지기 때문에 대부분 재귀 함수로 구현된 코드들이 많다. DFS는 미로 찾기로 치면, 막히는 곳까지 계속 파고 드는 Leaf-wise한 방식이다. 분기점이 나오면 길 하나를 선택하고 더 이상 진행하지 못하는 시점까지 진행한다고 보면 이해하..

2학년 당시, 교재로 사용했던 책이다. 생능출판에서 나온 'C언어로 쉽게 풀어쓴 자료구조'라는 책의 10장 그래프 파트에 있었던 이론적인 문제들을 복습하면서 풀어봤는데, 풀면서 나온 자료를 올린다. 골치 아파하는 대학생들을 위해 조금의 참고자료가 되었으면 하지만, 이를 그대로 복사 붙여넣기 하는 것은 자기 실력 발전에 전혀 도움되지 않는다는 사실만을 알았으면 좋겠다. 혹시라도 답이 틀린 부분이 있거나, 의문이 남는 부분이 있다면 언제든지 댓글은 환영합니다. 1. 다음 중 그래프에 대한 설명으로 틀린 것은? (4) 그래프에는 사이클이 존재하면 안 된다. 2. 인접 행렬 adj_mat[][]에서 어떤 정점 v의 진출 차수를 알고 싶으면 어떻게 하면 되는가? (1) 인접 행렬의 v번째 행의 값들을 전부 더한다..

해싱과, 해시테이블 그리고 충돌을 처리하는 체이닝 기법에 대해서 한 번 정리해보자.이 글을 시작하기에 앞서, 스택오버플로우의 많은 자료들 그리고 위키피디아, 각종 유튜브 강의를 참고했다는 사실을 먼저 알립니다. 해시와 해시함수 해시 함수(Hash Function)는 데이터의 효율적인 관리를 위해 길이가 각기 다른 데이터를 고정 길이로 매핑하는 함수다. 이 때 매핑하는 과정을 해싱(Hashing)이라고 하며, 매핑하기 전의 데이터를 키(Key), 매핑 후의 데이터를 해시 값(Hash Value; 때로는 Value)이라 한다. 해시의 목적 해시 테이블(Hash Table)해시 테이블은 데이터의 해시 값을 테이블 내 주소로 이용해먹는 탐색 알고리즘으로, 잘 구현하면 이진 탐색보다 빠르게 처리할 수 있다. 암호..

16. 다음의 코드에서 잘못된 곳을 찾아라.main(){ int i, a[10];for(i=0;i

1. C언어에서 배열에 대하여 다음 중 맞는 것은?답 : (2) 배열의 이름은 포인터와 같은 역할을 한다. 오답노트(1) 3차원 그 이상의 배열도 가능하다.(3) 배열의 인덱스는 0에서 시작한다.(4) 선언한 다음, 실행 도중에 크기를 변경하는 것은 불가능하다. 2. 다음 중 배열에 관한 문장 중 문법에 맞지 않는 것은?답 : (4) char *pb[30]="I am a student"; 해당 배열은 2차원 배열인데, 1차원 배열 초기화 방식을 사용하여 문제가 생긴 것. 3. float a[100]으로 선언되 배열의 시작 주소를 1000번지라고 할 때, 배열의 10번째 요소의 주소는 몇 번지인가?답 : (4) 1040번지 1000+4*10 4. 구조체에 관한 내용 중 틀린 것은?답 : (2) 구조체 변수..

어떤 것들은 심심할 때마다 다시 공부하곤 하는데, 자료구조도 그 중 하나다. 개인적으로 공부하면서 정리한 것들이고 답이 틀렸을 수도 있기 때문에 지적은 언제나 환영한다. #include #pragma warning(disable:4996) #define MAX_DEGREE 101 typedef struct { int degree; float coef[MAX_DEGREE]; } Polynomial; Polynomial read_poly() { int i; Polynomial p; printf("다항식의 최고 차수를 입력하시오: "); scanf("%d", &p.degree); printf("각 항의 계수를 입력하시오 (총 %d개): ", p.degree + 1); for (i = 0; i b.degree)..

어떤 것들은 심심할 때마다 다시 공부하곤 하는데, 자료구조도 그 중 하나다. 개인적으로 공부하면서 정리한 것들이고 답이 틀렸을 수도 있기 때문에 지적은 언제나 환영한다. 1. int a[10][20]에서 배열이 차지하는 메모리 공간의 크기는 얼마인가? int형은 4바이트라고 하자.(4) 800 바이트, 10x20x4 2. float a[100]으로 선언된 배열의 시작 주소를 1000번지라고 할 때, 배열의 10번째 요소의 주소는 몇 번지인가?(4) 1040번지, 1000+10x4 3. 다음 배열 중에서 크기가 가장 큰 배열은?메모리 크기 기준(2) double array2[10]; 10x8 = 80바이트인덱스 크기 기준(3) char array3[40]; 40 4. 크기가 10인 배열 two[]를 선언하..

모든 쌍의 최단 경로를 구하는 방법을 찾고 싶다면, 다익스트라(Dijkstra) 알고리즘을 모든 정점(Vertex)에 대한 최단경로를 구하거나 다익스트라가 제한되는 경우(음의 가중치가 존재하는 경우)에는 벨만-포드(Bellman-Ford) 알고리즘을 모든 정점(Vertex)에 대해서 사용하면 된다. 플로이드-워셜(Floyd-Warshall) 알고리즘은 앞서 말한 두 알고리즘과는 다르게 처음부터 모든 정점 사이의 최단 경로를 구하는 알고리즘이다. 위 그림은 i에서 j로 가는 방법을 표현한 것으로, k를 경유하는 경우와 그렇지 않은 경우에 대한 것이다. 위 문자의 의미는 1부터 k까지만 경유할 수 있는 상황에서 i에서 j까지 갈 수 있는 모든 경로 중, 가장 짧은 경로의 거리로, 동적계획법(Dynamic P..

앞선 글에서(링크) 이야기했던 대로, BuildHeap Algorithm은 다음과 같은 순서로 알고리즘이 진행된다. 가장 먼저 i=[n/2]=15로 시작하여 DownHeap을 호출해, i가 1이 될 때까지 총 15회 DownHeap을 호출한다.이 때 i에 대응되는 노드를 '시작 노드'라고 했을 때, DownHeap은 시작 노드의 값을 자식 노드들의 값과 비교해 힙 조건이 만족되는 순간까지 시작 노드의 값을 아래 쪽으로 자리를 바꾸며 이동시키는 작업을 실시한다. 즉, 시작 노드를 루트 노드로 간주하여 부분 힙를 구성하고,그 부분 힙을 합쳐나가는 과정을 거치는 것이다. 힙을 만드는 알고리즘 BuildHeap의 시간 복잡도가 O(n)인 이유는 아래와 같이 증명할 수 있다. n=31(노드 수 31개)인 경우, ..

힙(혹은 히프)은 최솟값(또는 최댓값)을 빠른 시간에 접근하게 만들어진 자료구조로, 최댓값을 접근하려면 최대힙을, 최솟값을 접근하려면 최소힙을 사용한다. 두 힙은 대칭적인 관계를 갖고 있기 때문에, 하나를 이해하면 다른 힙은 쉽게 이해할 수 있다. 힙에 대해 정확히 모르는 사람들을 위해서 이해를 돕기 위한 그림과 힙의 조건에 대해서 이야기를 잠깐 하겠다. 힙은 위 그림처럼, 각 노드의 값이 자식 노드들의 값보다 크거나 작은(클 경우 최대힙, 작을 경우 최소힙) 완전이진트리를 뜻한다. 거의 대부분이 정렬 파트를 다루면서 힙 정렬을 통해 이 구조에 대해서 아는 경우가 대부분이다. 오늘은 힙이 어떤 식으로 생겼는지 보는 것보다는, 힙 자료구조를 구성하는데 요구되는 시간복잡도가 O(n)인 것에 대해서 이야기를 ..