https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 재민이와 재현이의 역할을 잘 파악하면 된다. 재민 : 장부 관리 재현 : 잘못된 수를 외침 → 이로 인해 재민이는 가장 최근에 쓴 수를 지움 문제 해결 방법 재현이가 0을 외치면 스택 마지막 요소를 삭제한다. 0을 외치지 않으면 제대로 부른 것이니, 해당 숫자를 스택에 추가한다. 소스 코드 import sys input = sys.stdin.readline N =..
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 1. A에 2를 곱하기 2. A의 가장 오른쪽에 1을 추가하기 위 두 가지 방식만 써서 A를 B로 만드는 문제이다. 하지만 나는 B를 A로 만들어서 연산의 최솟값을 구했다. B에서 A를 만들어야겠다고 생각한 가장 큰 이유는, A의 가장 오른쪽에 1을 추가하는 시기를 결정하기 어렵기 때문이다. B를 2로 나누면서 가다 보면 일의 자리 수가 1인 경우가 발생하고, 이때 1을 삭제해 주면 같은 로직으로 구현된다. 이 방법을 통해 B에서 A를 찾아나갔고, 해당 연산의 최솟값을 구했다. 소스 코드 import sys input =..
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 문자열들이 .(점)으로 구분되어 주어졌을 때, 각 문자열이 갖는 소괄호와 대괄호가 짝지어져 입력되었는지 확인하는 문제이다. 괄호 문제를 보자마자 스택으로 접근해야겠다는 생각이 들었고, 문제 해결 방법은 아래와 같다. 입력받은 문자열을 문자단위로 접근한다. 만약 열린 괄호인 경우, 스택에 추가한다. 만약 닫힌 대괄호인 경우, 스택의 마지막 괄호가 열린 대괄호인지 확인한다. 스택..
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 두 개의 괄호 "("와 ")"로 이루어진 문자열들 중 괄호의 모양이 올바르게 구성된 문자열을 구하는 문제이다. 예전에 같은 문제를 풀었던 기억이 있는데, 정답 처리가 안되어 있는 것으로 봐서는 다른 문제인 것 같다. 괄호 처리 문제는 전형적인 스택 문제라고 생각한다. 풀이 과정 N의 크기만큼 반복문을 돌린다. 모든 과정은 이 반복문 안에서 진행된다. 반복문이 돌아갈 ..
https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 물통이 3개로 고정되어 있고 물을 옮길 수 있는 경우 역시 고정되어 있었기 때문에 고려해야 할 경우의 수가 정해져 있다고 생각했다. A가 비어있을 때 C에 들어있는 물의 양을 찾고자 했다. 하지만 이 문제를 어떻게 탐색으로 풀어야 할지 모르겠어서 답안을 참고했다. 이 문제는 완전탐색(BFS)을 통해 고려한 경우의 수는 하나씩 제외시키면서 풀어야 한다. 고려한 방식을 제외시키는 ..
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제를 간단히 정리하면 과제를 최대한 미루면서 가장 높은 점수를 받기이다. 즉, 마감일이 4일 남았으면 1, 2, 3일 남은 과제들을 하는 것이 이득이다. 4일 남은 과제의 점수가 제일 높다고 해서 1일차에 4일 남은 과제를 해버리면 1일 남은 과제의 점수를 날리게 된다. 어차피 모든 과제는 하루가 소요되기 때문에 마감일과 점수만 판단하면 된다. 내가 처음에 시도한 방법은 아래와 같다. (잘못된 방법) 점수 내림차순으로 정렬한 뒤 0번 인덱..
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 시험기간이라 그런지 알고리즘 푸는 게 더 재밌다..ㅠ 이 문제는 처음에 이해를 못해서 건너뛰었다가 다른 투포인터 문제를 푼 후에 다시 도전한 문제다. 처음에 착각한 부분이 있었는데, 4도 다른 수로 표현이 가능하길래 2 + 2가 되는 줄 알고 1 + 1 = 2도 가능할 줄 알았다. 그런데 문제를 잘 읽어보면 라고 명시되어 있다. 즉, 4는 2+2가 아니라 1+3이 가능해서 "좋다"에 포함되는 것이다. 이후 문제를 다시 잘 파..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 처음에 정렬로만 풀었다가 시간초과가 났다. 이후 두 수를 고른다는 조건을 파악하여 투 포인터로 풀었다. 위 문제들이랑 결이 비슷해서 어렵지 않게 풀 수 있었다. 입력받은 숫자들을 빈 배열에 추가해 준다. 배열을 정렬한다. 인덱스를 늘리며 두 수의 차를 구한다. 두 수의 차가 m 미만인 경우, right 인덱스에 1을 더하여 더 큰 차이가 나도록 만든다. 두 수의 차가 m 이상인..
