문제요약 (2800. 괄호 제거) 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 풀이를 위한 부연 설명 괄호의 위치를 스택을 통해 구현한다 각 괄호의 쌍을 뽑아내야하므로 스택을 사용한다. 괄호 쌍을 "포함한다/포함하지 않는다" 이 두 가지 경우에 대한 모든 수를 알아보기 위해 조합을 사용한다. 파이썬 itertools의 combinations를 이용해 경우의 수를 구한다. 여러 가지 같은 경우가 나올 수 있으므로 set()으로 답을 넣는다. 조합에 대한 자세한 개념 설명과 연..

문제요약 (1918. 후위표기식) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이를 위한 부연 설명 연산자의 우선순위를 기준으로 스택에 쌓아야한다. 괄호 처리에 유의해야한다. 스택에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다. [구버전] [Python] 03. 스택과 큐 📌 스택이란? 📚 스택 알아보기 📃 스택 (stack) 데이터를 임시 저장할 때 사용하는 자료구조 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식 푸시(push) : 스택에 데이터를 넣는 작업 팝(pop) ..

문제요약 (16113. 시그널) 1. 시그널은 "."과 "#"으로 이루어져 있다. 2. 시그널을 해독한 결과에는 반드시 숫자가 1개 이상 있다. 3. 시그널에 등장하는 모든 "#"은 올바른 숫자 패턴에 포함되어 있다. 4. 숫자와 숫자 사이에는 1열 이상의 공백이 있다. 여기서 공백은, 열의 성분이 모두 "."인 열을 의미한다. 5. 0부터 9는 아래와 같이 나타난다. 역시 "#"을 검은색, "."을 흰색으로 표시했다. 여러가지 예제들을 넣어보면서 구현이 맞는지 확인해봐야한다. 스스로 반례를 찾는게 중요하지만 시간이 없거나 정말 모르겠다면 (https://www.acmicpc.net/board/view/64923) 이 링크를 참고하길 바란다. 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자..

문제요약 (1931. 회의실 배정) 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 그리디 알고리즘을 사용해야한다는 생각을 반드시 해야한다. 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이를 위한 부연 설명 회의..

문제요약 (11286.절대값 힙) 배열에서 절댓값이 가장 작은 값을 출력한다. 절대값이 같은 경우에는 가장 작은 수(음수)를 먼저 출력한다. 파이썬에서 절댓값을 구하는 함수는 abs()이다. 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이를 위한 부연 설명 우선순위 큐 ( Priority Queue ) 원소들의 우선순위별로 정렬한다. 원소의 우선순위를 설정하여 값을 추가하는 put과, 값을 반환하는 get이 있습니다. 우선순위 큐를 이용하면 문제에서 해당하는 값을 넣을 수 있습니다. ..

문제요약 (2252. 줄 세우기) 키 순서가 주어질 때 키를 비교한 순서를 출력하라. 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이를 위한 부연 설명 같은 순서가 나올 때 관계가 없이 출력된다는 점에서 위상 정렬이 사용된다. 반드시 순환관계가 없는지 확인해야한다. 위상정렬에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다. [코테 알고리즘] 그래프 이론 / 관련 문제 본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문..

문제요약 (1976. 여행 가자) n개의 도시가 어떻게 연결되어 있는지와 여행 계획이 주어져있을 때, 여행 계획에 맞춰 도시들을 여행 할 수 있는지 판별하시오. 이때 같은 도시를 여러번 방문하는 것도 가능하다. 노드들의 연결된 상태를 물어보는 문제 이므로 유니온 파인드로도 문제를 풀 수 있다. 그러나 필자는 처음 생각한 문제 풀이 방법이 BFS이기도 하고, BFS로 풀어보고자 하는 마음이 생겨 BFS로 풀었다. 만약 유니온파인드로 푼 문제 풀이를 보고 싶다면 아래 링크()로 들어가길 바란다. 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것..

문제요약 (1717. 집합의 표현) 0부터 n까지 있는 집합이 있다. 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인지 확인하는 연산 두 가지가 주어질 때 각각에 맞는 출력을 제시하시오. 집합을 알맞게 연결해 같은 집합에 속하는지 확인해야하는 문제입니다. 이때 사용할 수 있는 유니온 파인드 알고리즘입니다. 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이를 위한 부연 설명 유니온 파인드 union과 find 두 가지 연산으로 구성되어 있는 알고리즘 unio..

문제요약 (1325. 효율적인 해킹) 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오. 문제에 대한 해답이 맞는데 자꾸 시간 초과가 나는 경우, PyPy3로 언어를 바꾸고 제출해보도록 하는 것도 방법이다.. 필자도 구글링하고 코드 수정만 엄청 많이 했었다. (..

문제요약 (1929. 소수 구하기 ) M 이상 N 이하의 소수를 모두 구해 출력한다. 소수를 구하는 여러가지 방법 중 에라토스테네스의 체를 이용해 구해보자 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이를 위한 부연 설명 에라토스테네스의 체의 원리 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성 2부터 숫자를 시작해 숫자가 지워지지 않은 경우 현재 선택된 숫자의 배수에 해당하는 수를 탐색하며 지운다. 단, 처음 선택된 수는 지우지 않는다. 리스트를 반복한다. n = a * b ( a > b) 라는 것은 n = b * a와 같다. 즉..