https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net # 스택문제이다. https://www.acmicpc.net/problem/9935 BOJ 9935번: 문자열 폭발과 같은 알고리즘으로 풀면된다. # 문자열 s를 입력받고 s의 첫문자부터 stack에 넣는다. 넣는 과정에서 stack[-1]이 'P'이고 현재 스택의 마지막 4개의 원소가 'PPAP'이면 del stack[-4: ]를 통해 'PPAP'를 날려주고 'P'를 stack에 넣어주는 것을 반복한다. # 모든 과정이 끝난뒤 stack에 'PP..
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net # deque를 사용해서 풀어야 하는 문제이다. 1. 풍선안에 있는 숫자들을 s로 입력받고 인덱스와 함께 dq에 저장한다. s = [3, 2, 1, -3, -1]이면, dq = [[1, 3], [2, 2], [3, 1], [4, -3], [5, -1]]이 된다. 2. dq에 원소가 존재하는 동안 반복문을 돌며 dq의 첫번째 원소를 pop해서 answer에 index를 넣어준다. dq의 하나의 원소만 남았다면, 그 원소의 인덱스..
https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net # 스택문제이다. 1. 우선 줄이 6개이므로 st에 빈 배열 6개를 선언해준다. 2. N만큼 반복문을 돌며 줄 번호와 프렛번호를 입력받는다. 3. 만약 st[line-1]에 원소가 존재한다면, 이미 그 줄을 누르고 있는 상태이다. 따라서 p(프렛번호)와 그 줄에서 가장 높은 음인 st[line-1][-1]을 비교해서 p가 더 작으면 그 줄에 있는 높은 음을 ..
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net # stack문제이다. # 처음에 모든 인원들을 모두 stack에 넣고 풀어봤는데, 중간중간 필요할때 stack에 넣고 바로 빼는 상황이 필요해서 다시 풀었다. 1. idx가 N이 될때까지 반복문을 돌며 만약 stack안에 원소가 존재하고 stack[-1]이 end(간식 받아야 할 사람)이면 end를 1증가 시켜주고 stack.pop()을 해준다. stack[-1]이 end가 아니면 studen..
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net # 2017 삼성SW역량 테스트에 출제된 문제이다. # BT함수는 백트래킹을 이용해 N//2명으로 이루어진 '링크'팀을 구해서 answer에 append해준다. # lst는 전체 인원중에서 answer에 있는 '링크'팀을 빼면 '스타트'팀이 자동으로 구해지기 때문에 set자료형을 사용하였다. 1. lst에 1번부터 N번까지 선수들을 넣고 BT(1, 1, [0])을 실행해 answer에 '링크'팀이 될 수 있는 모든 경..
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net # 이전에 푼 로또문제와 똑같다. # 단지 answer에 들어간 후보들 중 자음과 모음의 개수를 구해 자음이 2개이상, 모음이 1개이상인 후보들만 출력해주면 된다. import sys input = sys.stdin.readline def BT(prev, len, letters): if len == L: answer.append(letters.copy()) return for i in range(pre..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net # 백트래킹 문제이다. # k와 숫자들 num을 입력받은 뒤, BT함수로 백트래킹을 실행한다. # BT함수에서 len이 6이면, 숫자6개를 모두 뽑았으므로 answer에 nums.copy()를 append해주고 함수를 종료한다. # 이미 뽑은 숫자를 또 뽑을 수 없으므로, prev변수를 통해 현재 뽑은 숫자의 다음 인덱스부터 nums에 append되도록 했다. import sys inp..
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net # 크루스칼을 이용한 MST로 풀었다. 1. 우선 N개의 좌표를 모두 입력받은 뒤, 좌표들끼리의 길이를 dist함수로 구한다. 2. graph에 (i, j, dist(i, j))를 넣어준다음 dist(i, j)순으로 오름차순 정렬해준다. 3. 이미 연결되어 있는 통로들은 union 해준 뒤 graph에서 연결이 안되어있는 통로들을 연결하며 answer에 길이를 더해준다...
모르는 사이에 조금씩 조금씩..
