Development Artist

백준 단계별 풀기에서 큐,덱 세 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 1. 원을 이룬다는 것은 Circular Queue를 생각하면 된다. 논리상 구조는 실질적으로 인덱스 0과 7이 붙어 있지는 않지만 붙어있는 것처럼 간주하겠다는 것이다. 2. 요세푸스 문제를 예로, N=3 이라면 3, 6, 9, 12 의 순서대로 정수값들을 뺀다. 그렇다면, queue의 front값을 읽어 해당 순서를 제외하고는 다시 queue에 넣어주면 된다. 3 6 9 번째 숫자들은 출력을 해주고 pop을 통해 빼준다. 이..

백준 단계별 풀기에서 큐,덱 두 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1. for문으로 i=1부터 해서 N까지 숫자들을 queue에 push한다. 2. 하나가 남을때 까지 = queue의 사이즈가 1이 될 때 까지. 따라서 while문으로 하고 조건은 queue.size() > 1로 한다. #include #include using namespace std; int main() { ios_base::sync_w..

백준 단계별 풀기에서 큐,덱 첫 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. 큐의 구조는 위의 그림과 같다. 선입선출, 즉, 먼저 들어간 데이터가 먼저 나오는 방식으로, 스택의 선입후출과는 다른 개념이다. 스택에서는 아랫 부분이 막혀있었다면, 큐의 경우는 고속도로의 터널을 생각하면 될 듯하다. 흔히들, 사람들의 줄서기의 예시를 많이 든다. 먼저 와서 줄을 기다린 사람이 먼저 기다림을 해소..

백준 단계별 풀기에서 스택 6번째 마지막 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net '시간 초과'로 인해서 꾀나 고생한 문제였다. 처음으로, 프로그램의 결과물을 만들어내는 것뿐만 아니라, 효율적인 프로그래밍은 어떤 것인가에 대한 고민을 해보았던 문제였다. 처음 디자인한 것은, N만큼 숫자를 받으면 vector 변수(a)와 stack 변수(b)를 선언하고 각각 push하였다. 또, 결과값을 저장할 vector변수(c)를 선언하였다. a는..

백준 단계별 풀기에서 스택 5번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제를 보고 바로 이해하기 어려웠다. 입출력 예제를 보면서 결과를 따라가본 후에야 어떤 문제인지 알게 되었다. 기존에 풀었던 스택 문제와는 난이도가 있었다. 이전 문제들은 문제를 보고 바로 어떤식으로 풀어야 겠다라는 그림이 바로 그려졌었는데, 이번은 아니였다. 1...

백준 단계별 풀기에서 스택 4번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 이 문제는, 정말 애를 많이 먹은 문제였다. 런타임에러, 출력초과, 틀렸습니다를 엄청 많이 보았기 때문이다. 접근 자체는 어렵지 않았다. 이전의 괄호 문제를 풀어 보았다면, [ ] 괄호가 하나 더 추가 된 것이였다. 그래서 ( [ 일때는 스택에 넣고, ) ] 일때는 스택의 empty 여부와 스택의 top을 확인하여 ( [ 이면 po..

백준 단계별 풀기에서 스택 3번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이 문제에서는 규칙을 찾는 것이 꾀나 중요할 것이다. 처음으로 생각 했던 것은, '('의 개수와 ')' 개수가 같으면 VPS일 것이다 라고 생각했다. 하지만 ( ) ) ( ( ) 의 경우를 보자. 개수는 3개, 3개로 같으나, 가운데의 ')' 와 '('는 짝을 이루지 못한다. 따라서, 개수가 같은 것이 VPS를 모두..

도입 백준 단계별 풀기에서 스택 2번째 문제이다. 풀이 문제를 잠깐 생각을 해본다. 큰 그림을 그리는 것이 중요하다. 첫 번째는, 스택의 개념이다. 10828 문제에서 설명해 놓은 것이 있다. 링크를 첨부하겠다. jmcunst.tistory.com/4 [Baekjoon, C++] 10773번 : 제로 백준 단계별 풀기에서 스택 2번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다... jmcunst.tistory.com 두 번째는, for문이다. K개의 정수를 받을 것이다. 반복적으로 받아야 받을 때 마다 처리할 수 있다. 정수를 받을 때..

도입 백준 단계별 풀기에서 스택 1번째 문제이다. 해당 문제를 읽고 나서 큰 그림을 한번 짜 본다. 보통 어떤 문제에 직면했을 때, 이런 식으로 시작하는 습관이 있다. 첫 번째로, '스택은 무엇인가?'에 대한 고민이다. 문제에서 나오는 push, pop, size, empty, top의 명령은 stack 자료 구조에서 사용하는 명령들이다. 따라서, 스택이라는 것이 무엇인지 알아야 한다. 스택(stack)이란, 영어에서 '쌓다'라는 의미를 가진다. 스택을 다룰 때는 다음과 같은 구조를 떠올리면 된다. bottom이 막혀 있는 것이 특징이다. 우리가 a에서 j까지의 알파벳을 순서대로 스택에 넣는다고 가정하면, 스택 구조에서는 아래와 같이 들어가게 된다. 만약 여기서 내가 g를 빼고자 하면 어떻게 해야 할까?..

2021.01.05 2021년 새해가 다가왔다. 이제 어느덧 4학년이 되었고, 졸업이라는 것이 흐릿하게 보이기 시작한다. 아직도 꿈이 명확하지 않고 찾아가고 있는 중이지만, 적어도 내가 좋아하는 것들을 할 수 있기를 희망한다. 작년 한 해 동안, 협업을 통해 프로젝트를 꾀 많이 진행했다. 팀원들과 소통하면서 의견을 나누고, 피드백을 하고, 필요할 땐 설득하고, 결과물을 만들어 갈 때, 내 자신이 엄청난 집중을 하고 있다는 것을 발견했다. 끝나고 난 지금에 와서 어떻게 밤을 그렇게 새가면서 했는지 모르겠지만, 나한테는 굉장히 소중한 경험이었다. 대학교를 다니면서, 내 전공을 공부하면서, 이것을 완전히 즐기고 있다는 생각을 해본 적이 없었다. 내가 좋아하는 다른 무엇인가가 존재할 것 같았고, 실제로 긴 휴학..