기록보관소

균형잡힌 세상 문제는 스택을 활용하여 해결할 수 있습니다. 지문 중 '짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.'라는 문구가 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..

스타트와 링크 문제는 N명의 사람들을 두 집합으로 나누고 각 집합별로 능력치 합을 구하여 가장 적은 집합 간의 능력치 합의 차를 출력하는 문제입니다. 집합을 나누는 데 모든 가능한 경우의 수를 탐색하기 위해 백트래킹 기법을 사용하였습니다. 이때 주의해야 할 점은 자칫 똑같은 집합을 두 번 중복하여 계산할 수 있다는 점입니다. A집합에 있는 원소들이 그대로 B집합에 있는 상황입니다. 이러한 불필요한 연산을 방지하기 위해서는 어느 특정한 원소를 특정한 집합에만 존재한다고 미리 가정하여야 합니다. 예로 들어서 1을 기준으로 둘 때 모든 경우는 1을 포함한 집합과 포함하지 않는 집합으로 이루어져 있다는 것을 확인할 수 있습니다. 이때 1이 A집합에만 존재한다고 가정하면 똑같은 원소의 종류로 분할된 상황에서 B집..

연산자 끼워넣기 문제는 BOJ 14888번 문제이자 삼성 SW 역량 테스트 기출문제입니다. 가능한 모든 연산자의 순열을 찾기 위해서 백트래킹 기법을 활용하여 완전 탐색을 하는 것이 문제의 핵심입니다. 아래의 풀이에서는 연산자 배열을 정의한 후 0번 인덱스부터 N-2번 인덱스까지 순서대로 4가지 연산자를 채우며 가능한 모든 연산자 수열을 찾는 백트래킹 함수를 설계하였습니다. 문제를 풀면서 느낀 부분은 백트래킹 함수를 통해 완전 탐색을 할 때는 모든 경우를 일정한 기준에 따라 빠짐없이 분류할 수 있다면 문제를 쉽게 할 수 있다는 점입니다. 추가적인 팁으로 int형 변수에서 max와 min의 초기값을 설정할 때 간단하게 987654321, -987654321로 대입하면 int형의 최대, 최소 수의 범위를 기억..

이번 문제는 스도쿠를 푸는 문제입니다. 스도쿠의 규칙에 위배되지 않도록 빈칸을 적절하게 채움으로써 간단하게 문제를 해결할 수 있었습니다. 스도쿠의 빈칸을 채우기 위해 모든 경우를 탐색하는 백트래킹 기법을 사용하였습니다. 빈 칸의 좌표를 저장한 후 빈 칸의 개수만큼의 높이를 가진 트리를 탐색하는 재귀함수를 통해 백트래킹을 구현하였습니다. 재귀함수를 한번씩 통과할 때마다 빈 칸이 한 개씩 채워지며 모든 빈 칸이 채워지면 스도쿠를 출력하도록 하였습니다. 문제에서 제약조건으로 c언어의 경우 80ms 내에 처리하도록 하였으며, 작성한 코드는 76ms에 스도쿠를 처리할 수 있었습니다. 백트래킹을 빠르게 실행하기 위해서는 필요없는 경우를 무시하는 가지치기가 필요합니다. 재귀 함수에서 스도쿠를 출력하자 마자 프로그램이..

이 문제는 N*N 체스판에서 N개의 퀸을 놓을 수 있는 경우를 계산하는 아주 유명한 문제이다. 이 문제를 풀기 위해 N개의 퀸을 놓는 경우를 모두 조사하는 방식으로 진행하였고 따라서 백트래킹 기법을 사용하였다. 백트래킹은 트리 형태로 모든 경우를 탐색하는 기법이므로 재귀함수의 형태로 구현할 수 있고 재귀 함수의 탈출 조건에 문제에서 원하는 답을 얻기 위한 마지막 처리를 추가하는 식으로 코드를 작성할 수 있었습니다. N*N 체스판을 배열로 선언하여 직접 퀸을 체스판에 배치하고 퀸의 이동가능방향에 다른 퀸이 존재하는 지 확인하는 방식으로 문제를 해결할 수 있지만 이번에는 배열 사용을 줄이는 방향으로 코드를 작성해보았습니다. 가로, 세로, 대각선 방향으로 오직 1개의 퀸만이 놓일 수 있다는 사실에서 아이디어를..