s0n9h2

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 처음에 경우를 너무 많이 나눠야 하는거 아닌가 고민됐는데 알고리즘 분류를 보니까 브루트 포스를 사용하면 됐다. 그런데 브루트 포스 문제 저번에 한 번 풀어봤지만 어떻게 구현해야 할지 감이 안와서 난 결국 product(중복조합)을 사용했다. 제출했더니 천천히 올라가길래 맞았나 했는데 96%에서 틀렸습니다가 떴다... 이럴수가 근데..

문제 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 실버 III인데 아래 채점 결과를 보면 알겠지만 생각보다 어렵게 풀었다.. 끝까지 첫 번째 방법을 고수했으면 못 풀었을 것 같기도 하다... 스터디 전까지 못 풀어서 스터디원들의 풀이를 듣고 고쳐서 풀었다. 나는 아래처럼 조합을 모두 구해서 각 조합별로 가능한 가짓..

문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 사용 언어 Python3 풀이 과정 요즘 코딩 테스트를 많이 보며 확실히 느낀 코테 빈출 "문자열" 문제!! 뭔가 이제는 느낌이 다 비슷하다. 저번의 PPAP와 또 비슷한 느낌이었다. 처음엔 나는 저번에 공부한 re 라이브러리를 이용해서 정규식을 써볼까 했는데 문제의 조건을 보니 문자열 길이가 100만까지였다..ㅎㅎ 처음 생각한 방식은 단순무식하게 정규표현식 혹은 replace..

문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 골드 IV 문제 내 힘으로 풀어보겠다고 6시간을 쓴 날에 대하여...🤦‍♀️ 여느 때처럼 문제 설명은 짧고 명료했다. 어떻게 구현해야 할지 느낌도 왔다! 그런데 막상 처음 제출까지 (설렁 설렁 풀며 딴 짓도 좀 했지만) 3시간 정도 걸린 것 같고... 18% 쯤에서 틀렸습니다가 떠서 다시 고치는 데 3시간은 걸린 것 같다 ㅋ 시간을..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 사용 언어 Python3 풀이 과정 일단 이 문제도 그래프 탐색으로 착각하기 좋은 문제였다. 라인에서도 그런 문제가 있었는데... 이중 리스트를 사용하면 무조건 그래프 탐색이라는 편견(?)이 생겨버린 모양이다. 탈출하자 문제를 다시 천천히 읽으면서 어떻게 풀지 생각해보니 그냥.. 단순 조합을 이용한 완전 탐색도 가능해보여서 그대로 풀어봤고, 중간에 좀 헷갈린 부분은 자꾸..

문제 https://www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net 사용 언어 Python3 풀이 과정 요즘 코딩 테스트를 많이 보다 보니 내가 부족한 부분을 알았는데 그건 바로 정규표현식...! 파이썬으로 문자열 파싱은 이제 익숙하지만 복잡한 문자열 규칙에 해당하는지 확인하려면 if문을 쪼개고 쪼개는 것보단 정규표현식이 훨씬 간단하고 구현하기도 쉽다. 사실 보안을 공부하면서 Snort 룰 때 처음 정규표현식을 접했는데 그 때문에 정규표현식을 괜히 복잡한..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 사용 언어 Python3 풀이 과정 오랜만에 그래프 탐색다운 그래프 탐색 문제를 풀었다. 기본적인듯 생각해야 해서 처음엔 고민 좀 했다가 감은 잡았는데 list랑 함수를 재활용하려다가 엄청 꼬였다...ㅎㅎ 그래서 스터디 팀원들과도 고민해봤는데 재활용하기에 좋은 문제는 아닌 것 같다는 판단을 내리고 오늘 처음부터 다시 풀었다. from collections import deque fro..

문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 사용 언어 Python3 풀이 과정 오랜만에 DP 문제 중에 좀 빠르게 풀었던 것 같다. 문제를 파악하자마자 든 생각은 "나 이거 비슷한거 어디서 풀었는데..?"였고 뒤져보니 예전에 푼 계단 오르기가 거의 유사한 문제였다. 그리고 나서 이 문제를 푸려는데 연속으로 3잔을 마시지 않는 방법을 어떻게 처리했는지 생각이 안 나서 결국 계단 오르기 문제에서 내가 풀었던 답변을 참고했다. from sy..

문제 https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 나는 처음에 이 문제의 설명을 이해하기가 너무 어려웠다... 대체 왜 설명을 저렇게밖에 못했는지 의문이다. 일단 비내림차순으로 정렬한다길래 내림차순이 아닌 수열중에 랜덤을 말하는건가? 했는데 정렬이라는 말이 있어서 결국 오름차순으로 정렬한다는 말이었다. 그리고 다음 설명도 헷갈렸는데 결국 오름차순한 수열의 L번째 인덱스부터 R번째 인덱스의 합을 의미하는 것이었다. 따라서 처음에는 다음과 같이 코드를 짰는데 시간 초과가 났다. from sys imp..

문제 https://www.acmicpc.net/problem/4097 4097번: 수익 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10 www.acmicpc.net 사용 언어 Python3 풀이 과정 간단한 DP 문제이다. 점화식이 쉬운 건 그래도 풀 수 있는 것 같다. 그런데 다른 DP 문제에서 부분합을 구하기 위해 for문을 사용했던 게 생각나서 dp 리스트를 따로 만들고 지금까지의 합과 새로운 값을 더한 값을 비교해 저장하려 했는데 이건 이중 for문을 사용할 필요도, dp 리스트를 따로 만들 필요도 없었다. 그래서 생각..

문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 사용 언어 Python3 풀이 과정 그래프 탐색 문제였고 문제를 읽어보니 이제 DFS보단 BFS를 사용해야할 것 같은 느낌이 들었다. 물론 DFS로도 풀 수는 있겠지만 풀고 나서 보니 대부분의 사람들이 정말 BFS로 풀었더라! 문제는 되게 짧았는데 코드로 구현하는 방법에 대한 고민과 몇 가지 조건을 처리해주는 방식이 고민됐다. 일단 나는 정답을 기..

문제 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 사용 언어 Python3 풀이 과정 스터디 시즌3가 시작되고 첫 모임을 위한 두 문제 중 한 문제. 사실 오늘이 모임날인지 오늘 알아서 당황했다. 그래서 시간 부족으로 이 문제를 제대로 풀지 못했는데,, 감사하게도 스터디 시간에 다시 풀어볼 기회가 생겨서 집중해서 뚱땅거려본 결과 버저비터로(?) 문제 풀기에 성공했다! 처음 두 숫자를 A, B라고 할 때 k번째 날의 떡 개수는 A와 ..

문제 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 사용 언어 Python3 풀이 과정 스택은 이제 잘 알고 친숙한 자료형이라고 생각했는데 문제로 풀려니 또 바로 풀리진 않았다. 사실 문제를 이해하는데에도 시간이 좀 걸렸는데 (문제 설명이 불친절한 것 같다) 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓는다는게.. +를 하면 1부터 스택에 들어가고 -를 하면..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 "배낭 문제 알고리즘"의 기본 중의 기본 문제였다. 그래서 문제 이름도 평범한 배낭! 그런데 문제 유형은 코딩 테스트에서 몇 번 접해본 것 같았다. 이게 배낭 문제라는 알고리즘으로 취급되는지 몰랐을 뿐. 그래서 이번 기회에 확실히 공부해두려 했는데 생각보다 이해가 좀.. 어려웠다는..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 사용 언어 Python3 풀이 과정 우왕 이 문제는 생각보다 엄청 빨리 풀었다. 처음 문제를 읽고 나서는 이게... 무슨 그래프 탐색인가 싶었는데 다시 읽어보니 그냥 나눠 생각하면 쉽게 풀 수 있을 것 같은 느낌?! 바로 분할 정복을 사용하는 문제였다. 이 문제는 재귀로 풀든 분할정복으로 풀든 4등분이 핵심이기 때문에 나는 먼저 4등분에 초점을 맞추고 나눠진 구역이 1, 2, 3, ..

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 제목부터 힙을 사용하라고 암시하고 있다. 그런데 어떤 힙? 우선순위 큐! 따라서 구글링을 통해 heapq 구현법을 찾아서 아래까지는 쉽게 구현했다. from heapq import heappop, heappush from sys import stdin, stdout input = stdin.readline print = st..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 사용 언어 Python3 풀이 과정 처음에는 어디까지가 숫자이고 문자인지 구분하는 방법을 고민하면서 인덱스를 사용하는 방법, 스택을 사용하는 방법 등을 고민했는데 아무리 생각해도 가장 편한 방법은 split이고... 그런데 +와 - 두 가지이기 때문에 고민하다가 모든 숫자를 뺐을 때 가장 작은 수가 되기 때문에 일단 -를 기준으로 나눴다. 그런 다음 각각의 원소에 또 +가 포함된 경우가..