카드 2 문제는 큐를 활용하는 문제이다. 카드 덱의 위쪽은 head, 카드 덱의 아래쪽을 tail로 생각하면 간단하게 해결할 수 있다. 카드를 바닥에 버리는 것은 pop을 하는 것으로, 위쪽의 카드를 아래쪽으로 넣는 것을 pop 후 push로 생각할 수 있다. 이러한 과정을 카드가 1장이 남을 때까지 반복하여 마지막에 큐에 남은 원소를 출력하면 된다. 작성한 코드는 다음과 같다. #include #define size 1000000 //http://ark-hive.tistory.com int N; int queue[size]; int head, tail; int pop() { head += 1; head %= size; return queue[(head+size- 1)%size]; } void push(..
큐 2 문제는 자료구조 큐를 활용하여 해결할 수 있는 문제이다. 자료구조 큐에 대한 학습을 하였다면 어려움없이 무난하게 풀 수 있는 문제이다. 큐에 대한 내용은 다음 링크에 확인할 수 있다. 2021.07.07 - [알고리즘/이론] - [알고리즘/이론]큐 [알고리즘/이론]큐 원소를 삽입할 때 Enqueue, 원소를 제거할 때 Dequeue를 한다. 큐는 FIFO(first in, first out, 선입선출)의 특성을 같는다. 큐는 머리(head)와 꼬리(tail)을 갖는 데, 원소는 꼬리로 삽입되고 머리에서 제거된다 ark-hive.tistory.com 구현할 때 주의할 점은 getchar 함수를 사용할 때 다음과 같이 괄호를 써주어야 한다는 점이다. 연산자의 우선순위규칙 때문에 비교연산이 우선 수행된..
원소를 삽입할 때 Enqueue, 원소를 제거할 때 Dequeue를 한다. 큐는 FIFO(first in, first out, 선입선출)의 특성을 같는다. 큐는 머리(head)와 꼬리(tail)을 갖는 데, 원소는 꼬리로 삽입되고 머리에서 제거된다. tail은 원소가 삽입될 위치를 가리키며 head는 삭제될 원소를 가리킨다. 따라서 head=tail이면 큐는 비어있으며, 이때 원소를 삭제하려고 하면 underflow가 발생한다. head=tail+1 또는 head=1일 때 tail이 배열의 마지막 원소를 가리키는 상태이면 큐가 가득찬 상태이며, 이때 원소를 삽입하려고 하면 overflow가 발생한다. 수행시간 Enqueue와 Dequeue에는 O(1)만큼의 시간이 걸린다.
오큰수 문제는 스택을 활용하여 풀 수 있는 문제이다. 입력의 수가 1000,000이기 때문에 O(N^2)의 알고리즘으로는 풀 수가 없다. 스택을 활용하면 O(N)으로 풀 수 있게 된다. 아이디어는 다음과 같다. 수열을 순차적으로 탐색하면 어떤 수의 다음 수로 작거나 같은 수가 올 수 있고 혹은 큰 수가 올 수 있다. 작은 수가 오게 된다면 그것은 어떤 수의 오큰수가 되지 못하기 때문에 어떤 수의 오큰수를 바로 결정하지 못하고 다음에 결정할 수 있도록 어떤 수를 저장해야 한다. 큰 수가 온다면 그것은 오큰수가 될 수 있기에 어떤 수의 오큰수를 결정한 후 이전에 저장한 오큰수를 결정하지 못한 다른 수들에 대해 판단을 하여야 한다. 가만히 살펴보면 저장되는 수는 내림차순으로 저장되며 오큰수를 판별할 때는 오름..
스택 수열 문제는 스택으로 입력으로 주어지는 수열을 만들 수 있는지 확인하며 그렇다면 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 정점을 저장합니다. 따라서 무방향 그래프의 경우 리스..
스타트와 링크 문제는 N명의 사람들을 두 집합으로 나누고 각 집합별로 능력치 합을 구하여 가장 적은 집합 간의 능력치 합의 차를 출력하는 문제입니다. 집합을 나누는 데 모든 가능한 경우의 수를 탐색하기 위해 백트래킹 기법을 사용하였습니다. 이때 주의해야 할 점은 자칫 똑같은 집합을 두 번 중복하여 계산할 수 있다는 점입니다. A집합에 있는 원소들이 그대로 B집합에 있는 상황입니다. 이러한 불필요한 연산을 방지하기 위해서는 어느 특정한 원소를 특정한 집합에만 존재한다고 미리 가정하여야 합니다. 예로 들어서 1을 기준으로 둘 때 모든 경우는 1을 포함한 집합과 포함하지 않는 집합으로 이루어져 있다는 것을 확인할 수 있습니다. 이때 1이 A집합에만 존재한다고 가정하면 똑같은 원소의 종류로 분할된 상황에서 B집..
연산자 끼워넣기 문제는 BOJ 14888번 문제이자 삼성 SW 역량 테스트 기출문제입니다. 가능한 모든 연산자의 순열을 찾기 위해서 백트래킹 기법을 활용하여 완전 탐색을 하는 것이 문제의 핵심입니다. 아래의 풀이에서는 연산자 배열을 정의한 후 0번 인덱스부터 N-2번 인덱스까지 순서대로 4가지 연산자를 채우며 가능한 모든 연산자 수열을 찾는 백트래킹 함수를 설계하였습니다. 문제를 풀면서 느낀 부분은 백트래킹 함수를 통해 완전 탐색을 할 때는 모든 경우를 일정한 기준에 따라 빠짐없이 분류할 수 있다면 문제를 쉽게 할 수 있다는 점입니다. 추가적인 팁으로 int형 변수에서 max와 min의 초기값을 설정할 때 간단하게 987654321, -987654321로 대입하면 int형의 최대, 최소 수의 범위를 기억..
병렬프로세싱에서 부딪히는 문제점은 병렬 하드웨어를 성능향상에 활용하는 병렬처리프로그램이 많지 않다는 것이다. 병렬처리프로그램은 작성하는 데 많은 어려움을 겪는다. 병렬 프로세서가 처리할 수 있도록 프로그램을 조각내고, 이를 균등하게 맞추어야 하며, 각 프로세서 간 통신에 의한 오버헤드를 고려하는 등 여러 요소에서 제약을 맞추어야 병렬 프로세서을 이용해 성능을 향상시킬 수 있다. 최근에는 특별히 작성된 병렬 프로그램이 아닌 기존의 순차 프로그램이 단일 프로세서 내에서 명령어 수준의 병렬성(instruction-level parallelism, ILP) - 슈퍼스칼라, 비순차실행 등을 활용하여 빠르게 실행될 수 있기 때문에 극단적인 성능 향상의 경우가 아니라면 병렬 프로그램을 힘들게 작성해야 필요를 느끼지 ..
- Total
- Today
- Yesterday
- C++
- 이진탐색
- 취미
- 영화
- BOJ
- 베릴로그
- 영어 어휘
- BFS
- 이분법
- C언어
- 애니메이션
- 백준
- 구현
- 완전탐색
- 스택
- Git
- Verilog
- 건이의 특제 떡국 끓이기
- 재귀함수
- 메이플스토리
- Push
- 알고리즘
- recursive
- 백트래킹
- 너비우선탐색
- 구조체
- gem5
- backtracking
- 정렬
- 큐
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |