전체 글
백준 20922: 겹치는 건 싫어 - 투 포인터
https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 이 문제는 투포인터를 통해 풀 수 있습니다. 포인터 두 개 (p1, p2)를 선언한 하고, p2를 옮겨가며 현재 p2가 가리키는 숫자가 총 몇 번 나왔는지 count 해줍니다. (dictionary 활용) 현재까지 나온 숫자 중 중복되는 것이 K가 넘을 때까지 p2를 옮겨주고, 넘게 되면 반복문에서 나와 한 칸 앞으로 p2를 되돌려줍니다. (초과되기 바로 직전에 p2가 위치함) 최대 길이를 ..
백준 22862: 가장 긴 짝수 연속한 부분 수열 (large) - 투 포인터
https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 이 문제는 투포인터를 통해 풀 수 있습니다. 포인터 두 개 (p1, p2)를 선언한 후 p2를 홀수의 개수가 K가 넘을 때 까지 늘려줍니다. (p2의 위치를 옮기다가 리스트의 길이를 넘어가는 것도 처리) K개를 넘었다면 바로 한 칸 전으로 옮겨주어 K개를 넘기 바로 직전에 p2를 위치합니다. 그 후 p1과 p2사이에 있는 짝수의 개수를 계산합니다. (p2의 위치 - p1의 위치 + 1 - 홀수의 개수) 그러고 나서 p1의 값을 ..
백준 1431:시리얼 번호 - 정렬
https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 다음 세 가지 조건으로 정렬을 합니다. 1. 시리얼의 길이 2. 자리수의 합 3. 사전 순 다중 조건으로 정렬을 하기 위해서는 sorted의 key를 통해 커스터마이징을 할 줄 알아야 합니다. (lambda도 사용할 줄 알아야합니다.) key=lambda x: (조건1, 조건2, 조건3) 과 같이 사용하면 왼쪽부터 조건으로 잡고 정렬을 해줍니다. 조건 1 = len(x) -> 시리얼의 길..
백준 5427: 불 - BFS
https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 전체 와일문 도는 것이 1초이고 현재까지 몇 초인지 변수에 저장해둡니다. 그 뒤 불을 번지게 하고 상근이를 이동시킵니다. (queue 첫 번째의 time 값이 위에서 저장해둔 시간 변수가 아니게 될 때가지만) 불을 킬 때는 벽인지 아닌지만 검사해야하고, 상근이를 이동 시킬 때는 불이 번진 위치인지도 확인해주어야 합니다. 만약 상근이가 2차원 배열 테두리에 도달하게 되면 탈출에 성공하게 됩니다. # Pypy3 ..
백준 1021: 회전하는 큐 - 덱(Deque)
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net python의 deque를 사용하면 쉽게 풀리는 문제입니다. 뽑고자 하는 숫자가 앞에서 더 가까운지 뒤에서 더 가까운지 확인한 후 rotate시킵니다.(같다면 해당 숫자를 왼쪽으로 이동시킵니다. 오른쪽으로 이동시킬 경우 맨 뒤에서 맨 앞으로 이동시켜야되는 과정이 추가로 붙기 때문) from sys import stdin from collections import deque input = std..
백준 2493: 탑 - 스택
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 입력 값의 뒤에서 부터 확인을 합니다. 만약 스택이 존재한다면, 스택의 마지막 부분이 현재 확인하고 있는 값보다 작지 않을 때 까지 pop 해줍니다. 그 후 현재 확인하고 있는 값을 스택에 넣어줍니다. 몇 번째 건물에서 레이저를 수신하는지 알아야하기 때문에 인덱스 정보도 같이 넣어줍니다. 입력 값들이 6 9 5 7 4 라면 처음에는 스택이 비어 있으므로 바로 스택에 넣어줍니다. stack -> ..
백준 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 입력 값을 한 배열에 두고 첫 번째 인덱스를 target으로 둡니다. ex) 4 3 6 8 7 5 2 1 target = 4 스택에 1부터 n까지의 숫자를 넣으면서 스택의 마지막 부분이 target과 같은 지 확인해 줍니다. stack -> 1 2 3 4 4 == target target과 같다면 스택에서 마지막으로..
백준 1417: 국회의원 선거 - 그리디, 우선순위 큐
이 문제는 정렬을 이용해서 풀어도 되지만 우선순위큐를 이용하는 것이 시간복잡도 측면에서 더 효율적입니다. 1. 정렬을 이용해서 풀 경우 반복문을 돌 때 마다 자신을 제외한 수들을 내림차순으로 정렬한 후, 해당 값에서 -1을 한 후 자신의 값은 +1 합니다. 이 과정을 반복하다가 최대 값이 자신의 값보다 작게되면 break를 합니다. 하지만 정렬을 이용해서 풀게되면 반복문을 돌 때마다 시간복잡도 nlogn의 작업을 해야합니다. 2. 우선순위 큐를 이용해서 풀 경우 자신을 제외한 수들을 max heap 형태로 만들어 놓고 반복문을 돌 때마다 pop을 한 후 값을 비교합니다. 만약 pop한 결과 값이 자신의 값보다 크다면 해당 값에서 -1을 한 후 다시 큐에 넣고, 자신의 값은 +1을 합니다. 우선순위 큐에서..
백준 1789: 수들의 합 - 그리디
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 1부터 +1씩 증가한 수를 원하는 수가 되거나 수를 넘게 될 때 까지 계속해서 더해줍니다. 만약 원하는 수가 되면 카운트 횟수를 그대로 출력하면 됩니다. ex) 원하는 수가 6일 경우 1 + 2 + 3 -> 3개 만약 원하는 수를 초과하게 될 경우 count에서 -1을 해준 값을 출력합니다. ex) 원하는 수가 4일 경우 1 + 2 + 3 = 6 6에서 2를 빼면 4, 결국 1+3한 경우이고, 답은 2 얼마만큼 초과를 했던지 그 수는 지금까지 더한 숫자 중 하나 일테고, 우린 그 값이 무엇인지 알아갈 필요가 없습니..
백준 1520: 내리막 길 - DFS, DP
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS를 통해 구현하 되 메모이제이션을 하지 않는다면 시간초과가 날 것입니다. 특정 좌표에서 가고자 하는 좌표까지 갈 수 있는 경우의 수를 계속해서 배열에 저장해준다면, 다음 번에 그 좌표를 만났을 때 재귀를 돌지 않고 바로 값을 받을 수 있게 되므로 시간을 많이 단축 시킬 수 있습니다. import sys input = sys.stdin.readline sys.setrecursionlimit(10**..