본문 바로가기

스택11

[Programmers] 짝지어 제거하기 https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문자를 짝끼리 비교하여 같은 문자면 지우는 과정을 반복하면, 지워지는 문자가 있을 때 처음부터 다시 과정을 반복해야하므로 시간 복잡도 측면에서 매우 비효율적이다. 따라서, 스택(stack) 자료 구조의 후입선출(LIFO) 원리를 활용해 문제를 해결한다. 구현 주어진 문자열에 대해 앞에서부터 문자 하나씩 잘라서, 현재 스택의 top과 비교해 두 문자가 같으면 문자 하나를 스택에.. 2023. 12. 28.
[Baekjoon] 10830번: 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해결 과정 착안 문제에서 행렬을 곱하는 횟수 $B$가 매우 커서 단순하게 행렬 하나씩 곱하며 계산하면 제한 시간 내에 문제를 해결할 수 없으므로, 자기 자신 행렬을 제곱할 때마다 지수가 2의 거듭제곱으로 증가하는 것을 활용하고자 하였다. 구현 우선 임의의 $n \times n \space (1 \le n \le 5) $ 크기의 정사각행렬 $M_1, M_2$를 곱하여 결과를 도출하는 함수를 구현하고 테스트한.. 2023. 12. 4.
[Programmers] 괄호 회전하기 https://school.programmers.co.kr/learn/courses/30/lessons/76502 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 스택(stack) 자료 구조를 활용하여 다음과 같은 과정을 통해 괄호 문자열 여부를 판단하고, 해당 과정을 회전된 문자열에 대해서 반복 수행함으로써 괄호 문자열의 수를 카운팅한다. '(', '{', '[' 문자가 주어지는 경우: 스택에 해당 문자를 추가한다. ')', '}', ']' 문자가 주어지는 경우: 스택이 비어있거나 스택의 top에 위치한 문자가 괄호로 짝지어지지 않는.. 2023. 9. 7.
[Programmers] 올바른 괄호 https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 스택(stack) 자료 구조의 원리에 따라 '(' 문자가 들어오는 수 만큼 문자를 카운팅하고, ')' 문자가 들어오는 수 만큼 카운팅한 횟수를 다시 낮추는 방식을 활용하고자 하였다. 구현 함수를 실행하여 괄호 문자를 카운팅을 하는 동안 아래와 같은 경우는 문제에서 요구하는 올바른 괄호가 아니다. 문자열을 따라 첫 문자부터 마지막 문자까지 카운팅을 완료하고 난 뒤의 카운트가 0.. 2023. 8. 27.
[Baekjoon] 11047번: 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 해결 과정 착안 동전의 수를 최소화하기 위해 가능한 한 가장 높은 단위의 화폐부터 사용하여 주어지는 금액을 맞추고자 하였다. 구현 보유하고 있는 동전의 가치가 오름차순으로 주어지므로, 스택(stack) 자료 구조를 사용해 입력받는 순서로 동전의 가치가 맞추고자 하는 금액보다 작은 경우 이를 스택에 넣도록 구현하였다. 입력이 완료.. 2023. 6. 13.
[Baekjoon] 1874번: 스택 수열 https://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 문제 해결 과정 착안 수열을 만들 수 있는지 확인하는 별다른 방법이 떠오르지는 않아, 문제에서 제시한 과정을 그대로 구현하여 문제를 해결하고자 하였다. 구체적으로는 아래와 같이 구현하고자 했다. 스택이 비어있거나 Top에 위치한 요소가 현재 수열의 항보다 작으면 push를 반복 (위 반복이 끝난 후) 스택의 Top에.. 2023. 6. 12.

티스토리툴바