Problem Solving
백준 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..
백준 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과 같다면 스택에서 마지막으로..
백준 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**..
백준 1700: 멀티탭 스케줄링 - 그리디
https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 사용할 전기용품을 플러그에 꽂기 전에 세 가지 경우를 생각해야합니다. 이미 꽂혀 있는 경우 멀티탭에 빈 공간이 있는 경우 멀티탭에 있는 것을 뽑고, 새로운 것을 꽂아야 할 경우 1번의 경우 그냥 넘어가주면되고, 2번의 경우는 꽂고 넘어가주면 됩니다. 3번의 경우는 제일 마지막에 사용되거나, 앞으로 사용하는 일이 없는 것을 찾아 바꿔줍니다. 플러그에 꽂힌 전기용품을 기준으로 for문을 돌면서 현재 ..
백준 1439: 뒤집기 - Greedy
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 처음에 stack에 1을 넣어주고, 문자열을 하나씩 보면서 값이 바뀌면 stack에 1을 추가합니다. ex) 001100111000 => [1, 1, 1, 1, 1] = [0그룹, 1그룹, 0그룹, 1그룹, 0그룹] 혹은 [1그룹, 0그룹, 1그룹, 0그룹, 1그룹] 값이 바뀌지 않았다면 모두 0이거나 1이기 때문에 뒤집어줄 필요가 없기 때문에 0을 출력합니다. 값이 바뀌었다면 stack 길이에서..