지식보부상님의 공부 일지

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net  #define _CRT_SECURE_NO_WARNINGS#include #include #define MAX_QUEUE_SIZE 1000typedef struct { int queue[MAX_QUEUE_SIZE]; int rear, front;}QueueType;void error(char *message) { fprintf("stderr", message); ..

다항식을 표현하기 위해서는 구조체 선언이 필요하다. 구조체에서는 계수와 지수를 저장하는 필드가 필요하다. 또한 다항식의 특성상 지수의 내림차순으로 정렬하는 것이 좋기 때문에 중간에 원소를 잘 삽입할 수 있어야 하므로 linked list(연결 리스트)로 구현하는 것이 좋다. 따라서 다항식을 표현하기 위한 구조체 정의는 다음과 같다. 1 2 3 4 5 6 typedef struct _polyNode { int coef; int expon; struct _polyNode* link; }polyNode; typedef polyNode *polyPointer; cs 다항식의 덧셈과 뺄셈의 계산은 expon이 동일한 경우만 coef의 계산을 수행하도록 하면 된다. 그렇다면 두 개의 다항식을 입력으로 받아 두 다항..

배열의 큰 단점이 중간에 원소를 삽입하려면 cost가 매우 크다는 것이다. 중간에 자리를 만들기 위해서 나머지를 오른쪽으로 모두 옮겨야 한다. 같은 맥락으로 중간의 원소를 삭제할 때 원소를 삭제한 후 나머지 원소들을 모두 왼쪽으로 옮겨야 해서 cost가 크다는 단점이 있다. 연결 리스트(linked list)를 사용하면 이러한 문제들을 어느정도 해결할 수 있다. linked list는 다음과 같이 정의한다. 1 2 3 4 5 6 typedef struct _listNode { int data; // 여러 요소들 struct _listNode* link; }listNode; typedef listNode *listPointer; cs 예시 프로그램을 만들어보자. 다음과 같이 연결하기 위해서는 다음과 같이 ..

우리가 일반적으로 수식을 표현하기 위해 나타내는 방법은 중위 표기법(infix)이다. 중위 표기법은 숫자와 같은 피연산자 사이에 덧셈, 곱하기 기호와 같은 이항 연산자가 위치하도록 하는 방식이다. 반면 컴파일러는 후위 표기법을 이용하여 계산을 수행한다. 후위 표기법(postfix)는 계산할 피연산자를 뒤에 이항 연산자가 위치하도록 하는 방식이다. 예를 들어 infix로 2 + 3*4 + 5/6 과 같은 식이 있다면 postfix로는 234 * + 56 / + 와 같이 나타낸다. infix로 나타낸 수식을 postfix로 바꾸는 것은 어렵지 않다. 우선 계산 순서에 따라 괄호를 작성한다. 위의 2 + 3 * 4 + 5 / 6 을 예시로 들면, ( ( 2 + ( 3 * 4 ) ) + ( 5 / 6 ) ) 이..

우선 미로를 표현하기 위해서 1은 막힌 길, 0은 갈 수 있는 길이라고 가정한다. n x m 크기의 미로를 표현하기 위해서 2차원 배열을 정의한다. 또한 해당 위치에서 다음 위치로 이동할 수 있는 방법은 총 8가지 이다. 위처럼 현재 위치가 [i][j] 라면, 다음으로 이동할 수 있는 곳은 분홍색으로 색칠한 곳이다. 따라서 이동할 수 있는 방향을 구조체 배열로 선언할 수 있다. 1 2 3 4 5 6 7 typedef struct { short int vert; short int horiz; }offsets; offsets move[8]; cs 다음과 같이 선언한 후 dir (index) move[dir].vert move[dir].horiz 0 -1 0 1 -1 1 2 0 1 3 1 1 4 1 0 5 1..

[6] 큐(Queue) 에서 본 큐에 원소를 add하는 함수와 delete하는 함수를 보면 큐의 rear과 front 만 조정하는 것이고 실제로 원소를 삭제하는 것이 아니라 큐가 점차 오른쪽으로 이동하게 된다. 따라서 원소를 넣고 삭제할수록 큐가 완전히 다 차지 않았음에도 QueueFull() 에러가 발생할 수 있다는 것이다. 따라서 원형 큐를 이용하면 큐를 효율적으로 이용할 수 있다. 위는 원형 큐에 원소 A를 넣은 것이다. front는 처음 넣은 원소보다 원소보다 하나뒤에, rear는 가장 나중에 넣은 원소를 가리키도록 한다. 원형 큐에 원소 B를 넣으면 다음과 같이 rear는 원소 B를 가리키고, front는 원소 A 보다 하나 앞을 가리키게 될 것이다. 원소를 더 넣어 큐를 완전히 채워 보면 위와..

큐(Queue)는 스택(Stack)과 다르게 FIFO(First-In-First-Out) 리스트로, 먼저 들어온 원소가 먼저 나가는 자료구조이다. 가장 앞쪽(먼저 들어온)의 원소를 가리키는 부분을 front 라고 하고, 가장 뒤쪽(나중에 들어온)의 원소를 가리키는 부분은 rear라고 한다. 원소를 넣을 땐 add, 뺄 때는 delete 라고 한다. 예시를 보면 더 쉽게 이해할 수 있다. front는 f, rear는 r이라고 표현하였다. 큐에 A를 넣으면 다음과 같다. 큐에 B를 넣으면 rear 는 B가 되고, front는 A가 된다. 큐에 C를 넣으면 다음과 같이 C는 rear가 되고, A는 front가 된다. 이번에는 delete를 하면 다음과 같이 A는 삭제되어 리턴되고, B가 front, C는 그대..

스택(Stack)은 LIFO(Last-In-First-Out) 리스트이다. 즉, 가장 나중에 들어온 원소가 가장 처음 나가도록 한다. 스택에 원소가 들어오는 것을 push 라고 하고 스택에서 원소가 나가는 것을 pop 이라고 한다. 또한 스택에서 가장 마지막에 들어온 원소, 즉 가장 위에 있는 원소를 top 이라고 한다. 예시를 보면 더 쉽게 이해할 수 있다. A 원소를 스택에 push 하면, 원소 A는 top 이 된다. B를 스택에 push 하면 A위에 B가 쌓이고, 원소 B가 top이 된다. C를 스택에 push 하면 B위에 C가 쌓이고, 원소 C가 top이 된다. 이번엔 스택에서 pop 하면 스택은 다음과 같이 A와 B만 쌓여 있고 C는 리턴된다. 한번 더 스택에서 pop 하면 스택은 다음과 같이 ..

KMP(Knuth, Morris, Pratt) 패턴 매칭 알고리즘은 O(n)의 시간 복잡도를 갖는 알고리즘으로, 특정 패턴이 문자열에 존재하는지 확인하는 함수이다. KMP 패턴 매칭 알고리즘을 알기 위해서는 실패함수를 알아야한다. 실패함수(failure function) 실패함수 f( j ) 는 j 번째 index 에서 접두사와 접미사가 일치하는 최대의 길이를 의미한다. 접두사와 접미사가 일치하는 최대 길이가 존재하지 않으면 -1로 설정한다. 예를들어 패턴 p가 p = abcabcacab 라고 하자 당연히 f( 0 ) = -1 이다. 다음으로 f( 1 )을 보면 패턴에서 인덱스 1보다 작은 부분이 인덱스 1과 동일하게 일치하는 부분이 없으므로 마찬가지로 f( 1 ) = -1 이다. 마찬가지로 f( 2 )..

매직 스퀘어는 n×n 행렬에서 행과 열, 대각선의 합이 모두 같은 행렬을 의미합니다. 위는 같이 행, 열 대각선의 합이 모두 65로 동일한 매직 스퀘어 입니다. Coexter는 매직 스퀘어를 만드는 방법을 제안했습니다. 우선 첫번째 행의 가운데에 1을 넣고, 왼쪽 대각선 쪽으로 올라가면서 2, 3, ... 을 넣다가 square 바깥으로 나가게 되면 반대편으로 이동하여 계속 왼쪽 대각선쪽으로 올라갑니다. 만약 이미 숫자가 채워져 있다면 바로 밑에 칸부터 다시 시작합니다. 이를 C언어로 구현해볼까요? 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626..