[백준] 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

이진탐색 - Binary Search

정렬된 원소 리스트에서 시작한다. 리스트에 원하는 원소가 있으면 그 원소의 위치를 반환하고, 아니면 null 값을 반환한다. 매 번 남은 숫자 중의 가운데 숫자를 말하고, 대답에 따라 그 보다 큰 숫자 혹은 작은 숫자들을 한 번에 없앤다. n개의 원소를 가진 리스트에서 이진탐색을 이용하면 최대 $ log_2n$ 번 만에 대답을 찾을 수 있다. low = 0 high = len(list) -1 mid = (low + high) // 2 guess = list[mid] # 추측한 값이 작을 때 if guess item : high = mid - 1 알고리즘의 속도는 빅오 표기법에 의해서 O(연산횟수)로 표기할 수 있는데..

• format_list_bulleted 알고리즘과 자료구조/이론?
• · 2024. 1. 12.
• textsms

유클리드 호제법 - 최대공약수와 최소공배수

Python 에서 최대공약수와 최소공배수를 구할 수 있는 방법은 다양하게 존재한다. 그 중에서도 최소 시간을 이용할 수 있는 "유클리드 호제법" 에 대해 알아보고자 한다. 유클리드 호제법 (Euclidean Algorithm) 또는 유클리드 알고리즘이라고 불리는 이 방법은 2개의 자연수 또는 정수의 최대 공약수와 최소 공배수를 구할 수 있는 방법이다. 호제법 : 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 방법 예를 들어 a, b (단, a>b) 인 두 수가 존재할 때, a를 b로 나눈 나머지를 r 이라고 하면 a 와 b의 최대공약수는 b와 r의 최대공약수와 같다. 계속해서 나머지를 구해가면서 최종적으로 나머지로 나누어 떨어질때 까지 나누면 되는데 (최종적으로 나누어 떨어진 나머지가 최대공약수가 ..

• format_list_bulleted 알고리즘과 자료구조/이론?
• · 2024. 1. 11.
• textsms