기록보관소

https://www.acmicpc.net/blog/view/56

스택 수열 문제는 스택으로 입력으로 주어지는 수열을 만들 수 있는지 확인하며 그렇다면 push, pop의 순서를 출력하는 문제이다. 이 문제를 풀기 위해 스택을 선언하였으며, 문제에서 주어진 입력을 단서로 삼아 push, pop의 사용 여부를 조사하였다. n까지의 자연수가 오름차순으로 스택으로 입력되므로 스택에 입력된 숫자의 가장 큰 값이 입력으로 받아진 숫자보다 작다면 스택에 push를 한 후 pop을 하고, 크다면 기존에 스택에서 pop을 하여 입력된 숫자를 출력하는 지 확인해야 한다. 즉 어느 시점에서 스택을 활용하여 숫자를 출력하기 위해서는 다음과 같은 두 가지 방법 중 하나를 선택해야 한다는 사실을 이용해야 한다. 1. 오름차순으로 정렬된 순열의 숫자를 차례로 스택에 push한 후 1개의 숫자를..

균형잡힌 세상 문제는 스택을 활용하여 해결할 수 있습니다. 지문 중 '짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.'라는 문구가 LIFO 자료구조인 스택의 사용을 암시하고 있습니다. 따라서 괄호 문제와 비슷하게 풀 수 있으나 소괄호와 대괄호를 구분하는 부분만을 추가해주면 됩니다. 주의할 점은 마지막에 .을 붙임으로써 프로그램을 끝낼 수 있다고 하였는 데 .뒤에 어떠한 문자열이 없다고 맹신하여서는 안된다. 즉 EOF를 조건으로 끝내도록 하면 틀릴 수도 있다는 것이다. 작성한 코드는 다음과 같다. #include //https://ark-hive.tistory.com/ char character; //소괄호, 대괄호 구분, top=0이 되어야 함. 괄호 사이의 문자열의 균형..

괄호 문제는 스택의 특성을 활용하여 해결할 수 있는 문제입니다. 괄호의 문장이 완결되기 위해서는 여는 괄호와 닫는 괄호의 짝이 맞아야 합니다. 여는 괄호일 때 스택에 push하고 닫는 괄호일 때 스택에 pop을 함으로써 괄호의 짝이 맞는지 확인할 수 있습니다. 편의상 스택까지 구현하지 않고 스택의 가장 윗 원소를 표시하는 top만 선언하여 여는 괄호일 때 +1 닫는 괄호일 때 -1이 되도록 하였습니다. 이 때 주의할 점은 괄호 문장을 검색하는 중 top이 -1이 되면 그것은 닫는 괄호의 짝이 맞지 않는다는 뜻이며 즉시 탈출해서 NO를 출력해야 합니다. 그렇지 않으면 괄호의 짝이 맞지 않아도 top이 0이 되는 경우에 잘못된 값을 출력하게 됩니다. 실제로 pop함수를 구현하지 않아서 생기는 문제이므로 직접..

이 문제는 스택을 활용하는 문제이다. 0이 입력으로 들어왔을 때 stack을 pop하는 조건을 가진 문제로 조건에 따라 stack을 채우고, 마지막에 스택에 있는 모든 원소를 더하여 출력함으로써 풀 수 있다. 작성한 코드는 다음과 같다. #include //https://ark-hive.tistory.com/ int k; int temp; int stack[100020]; int top; int sum; void pop() { if (top == 0) { printf("%s\n", "underflow"); } else { top -= 1; } } void push(int num) { top = top + 1; stack[top] = num; } int main(void) { scanf("%d",&k); ..

이 문제는 스택에 대한 개념에 관한 문제이다. 스택 이론에 대해 제대로 숙지하고 있다면 크게 어려운 부분이 없다. 다만 입력을 받는 부분이 약간 까다로울 수 있다. getchar()를 통해 입력버퍼의 문자를 1개씩 개행문자가 등장할 때까지 읽고 실행해야 할 함수를 판단한다. 주의할 점은 입력버퍼의 가장 마지막에 getchar 함수는 EOF를 출력한다는 점이다. N을 scanf로 받는다면 scanf는 개행문자를 입력받지 않으므로 &*c를 통해 개행문자를 제거하거나 잉여 getchar를 통해 개행문자를 삭제해야 정상적으로 동작하게 된다. 작성한 코드는 다음과 같다. #include //https://ark-hive.tistory.com/ char num; int N; char str[100]; int sta..

가장 최근에 삽입된 원소부터 삭제되는 동적 집합 자료 구조(후입선출, LIFO, Last in First out) 원소를 삽입하는 연산은 push, 원소를 추출하는 연산을 pop이라고 한다. 스택의 top은 가장 최근에 삽입된 원소를 가리킨다. top = 0 이면 스택을 비어있다는 것이며 이때 pop을 실행하면 스택 부족(underflow) 오류가 발생한다. 반대로 스택이 가득찬 상태에서 원소를 삽입하면 스택 포화(overflow) 오류가 발생한다. push, pop의 수행시간 모두 O(1)의 수행시간이 걸린다.

그래프를 깊이 검색하는 알고리즘이다. 최근에 발견되었으나 아직 조사되지 않은 간선을 가진 정점에서 나오는 간선을 조사하고, 그 간선들의 조사가 끝나면 그 정점이 유래한 정점으로 되돌아가 해당 정점에서 나오는 간선을 조사한다. 출발점으로부터 도달가능한 모든 정점을 발견할 때까지 검색이 계속되며, 발견되지 않은 정점이 있다면 다른 출발점을 선택하고 검색을 반복한다. 너비 우선 검색과 달리 출발점이 여러 개가 있는 것으로 생각하지만 이는 알고리즘의 응용할 때 필요가 반영된 결과이다. 검색을 하면서 새로운 원소를 발견하면 그 원소에는 직전원소를 기록하며, 이를 통해 직전원소 부분 그래프를 형성할 수 있다. 너비 우선 검색과 달리 출발점이 여러 개가 될 수 있기 때문에 깊이 우선 트리의 개수 또한 여러 개가 될 ..

BFS는 간단한 검색 알고리즘으로 많은 그래프 알고리즘의 원형이 되는 알고리즘이다. 발견된 정점과 발견되지 않은 정점 사이의 경계선을 균일하게 확장시켜나간다는 사실에서 너비 우선 검색이라는 이름이 유래하게 되었다. 즉, 거리가 k인 정점을 모두 탐색한 후에 k+1의 거리를 갖는 정점을 탐색한다는 뜻이기도 한다. 특징적인 부분으로 이 알고리즘은 그래프 내의 하나의 출발점에서 도달이 가능한 모든 정점을 체계적으로 검색하는 알고리즘이다. (검색이란 그래프 내의 정점을 방문하기 위해 간선을 규칙에 맞춰 따라가는 행위이다.) 또한, 출발점에서 도달이 가능한 모든 정점을 포함하는 너비 우선 트리를 만들며, 이때 각 정점까지의 단순 경로는 출발점에서 특정 정점까지의 거리를 의미한다. (거리란 정점과 정점 사이의 최소..

인접 리스트, 인접 행렬로 그래프를 표현할 수 있습니다. 이 두 방식은 방향, 무방향 그래프 모두에 적용할 수 있습니다. 대개 간선의 개수가 적으면 인접 리스트로 표현하며, 간선의 개수가 많은 경우 인접 행렬로 표현합니다. 보통 두 정점을 연결하는 간선이 있는지 빠르게 확인할 때는 인접 행렬을 사용합니다. 인접 리스트 표현법(adjacency-list representation)에서는 V개의 리스트로 그래프의 간선을 표현합니다. 각각의 리스트는 그래프 내의 하나의 정점에 대해 연결된 다른 정점들을 포함합니다. 무방향 그래프의 경우, (u,v)에 대해 u의 리스트와 v의 리스트 각각에 서로의 정점을 저장하고, 방향 그래프의 경우, u의 리스트에 대해 v 정점을 저장합니다. 따라서 무방향 그래프의 경우 리스..