[백준] 10799 번 쇠막대기 (스택)

백준 10799번 문제입니다. 이젠 괄호만 봐도 스택이 생각나버리는...😞 이번 문제는 이해하는게 너무 오래 걸리고 어려워서 글을 작성하게 되었습니다. 문제 해결 아이디어 괄호 문제의 포인트는 괄호를 스택에 넣고 쌍이 맞게 되면 pop()을 통해 빼내는 방식으로 해내는 것입니다. "(" 기호가 들어오게 되면 쇠막대기가 있거나 or 레이저로 시작점을 자르는 경우가 됩니다. "(" 기호가 들어오고 ")" 기호가 바로 들어오는 경우 -> 레이저로 자르게 되는 경우 (막대의 오른쪽 끝) ")" 만 들어온 경우 -> "(" 기호는 막대의 시작점이 된다. (막대의 왼쪽 끝) 위의 두 아이디어를 가지고 문제의 그림을 다시 봅시다. ()로 괄호가 완성된 시점에서 레이저를 통해 막대를 자를 수 있습니다. 첫 번째 괄호 ..

• format_list_bulleted 알고리즘과 자료구조/매일매일 알고리즘
• · 2024. 4. 4.
• textsms

[백준] 11726번 DP - 파이썬 (오버플로우)

백준 11726번 타일링 문제입니다. DP 문제의 특징은 전에 계산된 식의 결과값을 다시 사용함으로써 메모리 효용성을 기대하는 것이죠. 그래서 문제에 대한 반복적인 규칙을 찾아 점화식을 만들어 푸는 방법으로 접근해야합니다. 문제 분석 $2*n$ 크기의 직사각형을 $1*2$ 혹은 $2*1$ 의 타일로 채우는 방법은 두 가지 경우의 수로 나눌 수 있습니다. 마지막 직사각형이 $1*2$ 타일이 한 개 들어가는 경우 마지막 직사각형으로 $2*1$ 타일이 두 개 들어가는 경우 첫 번째 경우는 마지막은 $1*2$ 타일로 놓고, $2*(n-1)$ 크기의 직사각형을 채우는 방법의 수와 같죠. 두 번째 경우는 마지막에 타일이 두 개가 들어가기 때문에 $2*(n-2)$ 크기의 직사각형을 채우는 방법의 수와 같아집니다. 그..

• format_list_bulleted 알고리즘과 자료구조/매일매일 알고리즘
• · 2024. 4. 1.
• textsms

[백준] 10828번 스택

함수 하나씩 만들어가면서 천천히 풀이하면 되는 문제 스택 자체를 구현하는 문제이다 괄호문제에서 설명했듯이, Stack 은 Last in Frist Out (LIFO) 구조를 띈다. 쉽게 생각하면 한쪽 면이 막힌 원통을 생각하면 된다. 따라서 마지막에 들어간 원소가 제일 먼저 나올 수 있는 구조가 되는 것이다. 코드는 아래처럼 작성했는데, input() 함수를 사용하는 것 보다 import sys sys.stdin.readline().strip() 이용하는 것이 속도면에서 빠르다고 한다. (그래서 처음에 단순히 input 으로 입력을 받았다가 시간초과에 걸렸다.) input() 과 sys.stdin.readline().strip() 에서 시간 차이가 발생하는 이유 input() 은 사용자로부터 한 줄을 입..

• format_list_bulleted 알고리즘과 자료구조/매일매일 알고리즘
• · 2024. 1. 23.
• textsms

[백준] 9012번 괄호

스택 공부하면서 풀이했는데 익숙하다 했더니 아카데미에서 배웠던 문제이다 (ㅋㅋ) Stack 자료구조를 이용하면 풀이할 수 있다. Stack 자료구조는 Last in First Out(LIFO) 구조를 말하고 Stack을 하나 만들어서 stack = [] 형태로 두고 풀이하면 된다 *** 처음에 고안했던 방법은 (틀렸지만) list로 input을 받아서 list의 원소들을 보면서 list[0]과 list[-1]이 다르면 쌍으로 묶어서 pop 하고, 같은 경우 하나만 pop 해서 다른 리스트에 넣으면 어떻게 되지 않을까... 라는 생각을 했지만? indexing에서 부터 out of range 오류가 나서 Stack으로 풀이하였다... *** Pseduo-code 먼저 pseudo-code를 작성해보면, 1..

• format_list_bulleted 알고리즘과 자료구조/매일매일 알고리즘
• · 2024. 1. 23.
• textsms