문제 접근 () 와 같이 내부가 없는 괄호는 레이저이다. 이외의 괄호들은 쇠막대를 표현한다. 이 부분을 보자. 스택에는 (, (, ( 3개가 들어가 있는 상태에서 레이저가 들어온다. 스택에 무언가 들어가 있다는 것은, 쇠막대기의 끝이 아직 발견되지 않았다는 뜻이고 이는 곧 레이저에 의해 영향을 받는다는 의미가 된다. 하나의 막대가 잘리면 두개가 된다. 따라 레이저가 들어올 때 현재 스택의 길이만큼 카운트를 추가해주면 된다. 이때 주의사항으로는 쇠막대기의 시작 지점에서 카운트를 1씩 미리 해줘야한다. 정답 코드 #10799번: 쇠막대기 import sys str = sys.stdin.readline().rstrip() stack = [] count = 0 for i in range(0, len(str)-1..

문제 설명 문제 접근 reverse(), delete()는 각 O(N)의 시간이 걸린다. 따라 70만 합 조건을 고려하여 계산했을 때 시간초과가 난다. D가 첫 번째 수를 버리는 것이므로 deque의 pop(popleft)를 사용해 시간을 줄일 수 있다. 이는 평균적으로 O(1)의 시간이 걸린다. R 또한 해결해야 하는데 두번 뒤집기(RR) = 처음과 똑같은 상태, 세번 뒤집기(RRR) = 한번 뒤집기(R) 라는 것을 이용한다. 뒤집은 횟수만 기억하였다가, 마지막에 홀수인지 짝수인지 판단만 하면 된다. 그러나 뒤집힌 상태에서 D가 수행되는 경우 이는 pop 또는 popleft (처음 부분 삭제 or 마지막 부분 삭제)로 나뉠 수 있다. 이를 R이 몇번째 등장하였는지 카운트하여 D가 수행되는 시점에서 뒤집..

문제 설명 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때..

문제 접근 간단히 생각해보면 오른쪽 -> 왼쪽으로 레이저를 쏴주므로 탑 리스트를 역순회하면서 오른쪽보다 큰 값인지 확인해야 한다. 6->5->4->7 과 같이 순회하는 경우 6,5,4 높이의 탑은 모두 7에서 수신한다. 따라 아직 수신되지 못한 신호를 보낸 탑들을 저장해 두어야 하는데 스택이 적합하다. 하나의 탑을 체크할때마다 스택의 top을 계속 확인하면 될것 같다. 스택이 비지 않았다면 top에 쌓여있는 걸 현재 탑의 높이와 비교하면서, 현재탑보다 낮은 것이 쌓여있다면 그것들은 다 pop하고 정답 배열에 추가하거나 바로 출력하면 된다. 위 작업을 하고 나서 스택에 현재 탑을 넣어준다. 중요한 부분은, 스택에 쌓여 있는 탑들과 현재 탑을 비교하고, pop하는 거까지는 문제가 없어도 그 스택에 쌓인 탑들..

문제 접근 이중포문을 돌리면 쉽게 풀 수 있지만, 시간초과가 날 것 같아 계산을 해봤다. 파이썬 기준 제한시간 1초 => 1*3+2 = 5초, 5 * 2000만번(연산) = 약 1억번 연산이 가능 n이 최대 10만이므로 O(n^2)의 알고리즘을 적용할 경우 최악의 경우 10,000,000,000(백억번)의 연산을 해야 한다. 즉 시간초과가 나므로 다른 방법을 사용하는데, 투 포인터 방법이 정석인 것 같고 파이썬의 경우 in 연산자로 푸는 것도 가능하다. 정답 코드 1 (투 포인터) import sys n = int(sys.stdin.readline()) a = sorted(list(map(int, sys.stdin.readline().split(" ")))) x = int(sys.stdin.readlin..

문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 ..

문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력 첫째 줄에 문자열 ..

그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘은 "현재 상황에서의 최적해를 선택하는 방식"이다. 백트래킹을 통해 추가적인 점검을 하지 않고, 현재 선택지 이외에는 검증을 하지 않는다. 하지만 그 해가 항상 최적해라는 보장을 할 수 없다는 한계가 존재한다. 위와 같은 최소 가중치 문제에서, 그리디 알고리즘을 적용하면 7과 10중에 7을 선택하고, 12와 15중에 12를 선택하여 7 + 12 = 19의 가중치를 해로 갖게 된다. 그러나 그림을 보면 알 수 있듯이 실제 최소 가중치는 10 -> 5를 선택하는 15이다. 그리디 알고리즘을 적용했을 때, 매 선택마다 부분 최적해는 구했지만, 전체 최적해를 구하지 못한 것이다. 따라서 그리디 알고리즘은 항상 최적해를 보장하지 못한다고 할 수 있다..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 예제 입력 5 4 1 5 2 3 5 1 3 7 9 5 예제 출력 1 1 0 0 1 문제 접근 m_arr.forEach(m => { if(n_..

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다..