Dalin's Archive

문제 풀러 가기 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net ✅문제 풀이 처음에는 뭔가 수학적인 규칙이 있나 생각하다가(나누기한 나머지 등..) 예제를 풀어봤는데 안맞았다ㅠ 문제 분류를 보니 '큐'가 있어서 아이디어가 떠올랐다. 그냥 원이 돌 듯이.. 큐로 구현하면 되는 것이었다. python deque를 사용했다. 앞쪽으로도, 뒤쪽으로도 요소를 삽입/삭제할 수 있다. 원으로 돌 때도 맨 뒤에 있던 것 다음에 맨 앞에 있는 걸로 오니까.. deque로 이걸 구현할 수 있었다.(맨 앞에서 꺼내서, 맨 뒤로 넣기) K번째 사람이 제거되면, deque에서 제거했다. 출력 형식이 특이해서 주의해야 한다!..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 ✅ 2년 전, 1년 전에도 도전했다가 어제 오늘 푼 문제이다!! 😍😍 2년 전, 1년 전에는 조금 무식한(?) 방법으로 풀었다. import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) arr = list(input().strip()) cursor = len(arr) # 커서는 문장 맨 뒤에 위치 N = int..

백만년만에 문제 풀이..ㅎㅎ 넘 재밌다. ✅문제 풀이 1026 보물 백준 길이 N인 정수 배열 A와 B가 있다. A 배열을 마음대로 배열할 수 있다. A 배열과 B 배열의 같은 인덱스에 있는 숫자를 곱한 값을 S라고 하는데, S 의 최솟값을 구하는 문제이다. 조금 생각해 보니, S 최솟값을 구하려면 A 배열에서 큰 값 순서대로 & B 배열에서 작은 값을 순서대로 곱하면 되는 게 떠올랐다. 예제로 테스트해보니 맞는 것 같았따. B배열은 재배열하면 안된다고 쓰여있는데, 사실 상관 없다. A배열을 재배열해서, 인덱스가 같은 B배열의 숫자를 조정하는 게 포인트니까..! B배열이 고정되어 있다고 해도, A 배열을 조정해서 원하는 숫자와 매칭시킬 수 있으니까..!! 그래서 A 배열을 오름차순 정렬, B 배열을 내림..

문제 보러가기! 닻과매 님이 올리신 백준 문제집을 보고 너무 풀고 싶어져서, 오랜만에 풀었다 ㅎㅎ 정말 접근 아이디어가 재미있었다! N-1 개의 스위치를 눌러서 모든 램프를 켤 수 있는지 판단해야 했다. N-1개의 스위치로도 모든 램프를 켤 수 있으려면, 어느 한 스위치에 연결된 램프들은 모두 다른 스위치와 연결되어 있어야 한다는 아이디어가 중요했다 ! 상세한 설명은 주석으로..ㅎㅎ # N-1 개의 스위치를 눌러서 모든 램프를 켤 수 있으면? # 어느 한 스위치에 연결된 램프들은 모두 다른 스위치와 연결되어 있어야 함. # 그러면 1 출력, 아니면 0 출력 from collections import defaultdict N,M =map(int,input().split()) lamps_connect_swi..

와아아아~~ 엄청 오랜만에 문제를 풀었다 !!!! 문제 보러가기 풀이 😍 떡 종류는 1-9번! N일 동안 떡 팔러 가는데, 그날 파는 떡의 종류들은 매일 달라진다. 전날의 떡과 오늘의 떡은 꼭 달라야 한다. 떡을 줄 방법이 있으면, 매일 호랑이한테 줄 떡을 순서대로 출력한다. 떡을 줄 방법이 없으면, -1을 출력한다. 처음에는 백 트래킹을 생각했다. 호랑이한테 줄 수 있는 떡의 경우들로 가지를 뻗어보다가, 처음으로 정답까지(N일 동안 호랑이한테 다른 떡 주는 경우) 가면 그만 탐색하면 되겠다고 생각했다 !! 또 N이 최대 1000이니까 그 정도면 dfs 를 돌릴 수 있다고 생각했다! dfs 함수를 만들고 그 인자로 며칠인지(day), 그 동안 호랑이한테 준 떡들(history)을 넘겼다. 매일 호랑이한테..

문제 보러 가기!! 풀이🤗 이분 탐색!!! 으로 풀었다. 이분 탐색에서 구하는 값은 '총 심사하는 데 걸리는 시간' 즉 ans 이다. 최솟값은 1, 최댓값은 (가장 짧은 심시 시간 X 심사할 사람의 수)로 했다. 그 시간을 구한 뒤에, 그 시간 동안 상근이와 친구들이 모두 심사 받을 수 있는지 봤다. (calculate_screening_cnt 함수) 모두 심사받을 수 있다면 답이 될 수 있는 건데, 더 짧은 시간에 심사 받을 수도 있기 때문에 return을 하지는 않았다. 모두 심사받을 수 없다면, 이 값을 늘려줘야 한다. 코드❤️ import sys input = sys.stdin.readline N, M = map(int, input().split()) times = list(int(input())..

문제 보러가기!! N 자리 신기한 소수를 찾는 문제이다. 신기한 소수란, 왼쪽에서부터 첫째자리만 봐도 소수이고, 첫째 둘째 자리를 봐도 소수이고, 1-3자리를 봐도 소수이고, ... 1-N자리를 봐도 소수인 수이다. 예를 들어서, 2393은 2도 소수, 23도 소수, 239도 소수, 2393도 소수이다! N은 최대 8이니까 크기가 9인(0번째 인덱스는 편의를 위해서 안 씀) 2차원 리스트를 만들었다. 1 자리 신기한 소수는 쉽게 구할 수 있으니 미리 구해서 첫번째 리스트에 넣었다. 2, 3, 5, 7 그 이후부터는 N자리 신기한 수까지 차례 차례 신기한 수를 찾았다. 방법은 다음과 같다. 2자리 신기한 소수를 찾으려면 왼쪽에 1자리 소수를 두고, 오른쪽에 한자리 수를 붙인 뒤에 그 수가 소수인지 확인하면..

문제 풀러 가기!! 큐, 구현 문제였다.! 큐를 두개 만들어서 풀었다. 하나는 문서 중요도들만 내림차순으로 담은 큐(1번 큐라고 하겠다), 하나는 tuple(문서 중요도, 문서 번호)로 묶어서 담은 큐(2번 큐라고 하겠다)! 처음 프린터 큐에서 M번째 문서를 몇 번째로 프린트했는지를 구하는 것이라서, 문서 번호(처음 프린터 큐에서 몇 번째로 위치하는지)를 저장해야 한다. 두번째 큐의 맨 앞에 있는 것을 뽑으면(popleft) 인쇄할 차례가 된 문서가 된다. 그 문서의 중요도가 그때 있는 문서들 중에서 가장 높으면(첫번째 큐의 맨 앞 원소를 확인하기), 프린트를 했다고 본다. 프린트를 했으면 첫번째 큐에서도, 두번째 큐에서도 맨 앞에 있는 원소를 빼주면 된다. 프린트를 하지 않으면, 두번째 큐의 맨 앞 원..

문제 풀러 가기!! 설명 🤔😊 조합 + 구현 + BFS로 풀었다 ㅎㅎ 벽을 꼭 3개 새로 세워야 한다.-> 어디에 세울까?? N, M이 최대 8이니까 최대 64칸이 나온다. 64칸 중에 3칸에 벽을 세우는 경우를 구한다. 즉 조합으로 어디에 벽을 새로 세울지 구했다. 이 경우들을 쭉~~ 봐줬다. 빈칸에만 새로 벽을 세울 수 있으니 빈칸인지 확인하고, 빈칸이면 벽을 세웠다. 벽을 세운 후, 바이러스가 퍼져나가는 걸 시뮬레이션했다. 이때 BFS를 사용했다. 마지막으로 빈 칸 수를 세고, 정답을 업데이트하면 된다! 코드 👏💖 import sys from itertools import combinations from collections import deque from copy import deepcopy in..

백준으로 문제 보러 가기~ 인트로(TMI) 저번 주부터 회사에 다니기 시작했다! 나는 주로 React를 다뤘는데, 회사에서는 Vue를 사용한다.. 그래서 Vue 공부를 하느라고 문제를 별로 못 풀었다 ㅠㅠㅠ 그러다 푸니까 넘 재밌었다!!!! 쉬운 줄 알았는데 시간 초과가 많이 나서 신경을 썼다...재밌는 DFS문제였다!! 풀이 세로 R칸, 가로 C칸 표 모양의 보드에 대문자 알파벳이 써있다. 좌측 상단에서 시작해서, 상하좌우 4칸 중 한 칸으로 갈 수 있다. 매번 다른 알파벳을 지나면서, 가장 많이 이동하는 칸 수를 구하는 문제였다!! 이동하는 모든 경우를 고려해야 하고 R, C 가 20 이하여서.. DFS로 풀 수 있을 거라고 생각했다. 처음에는 방문했던 알파벳인지 체크하는 것을 set으로 했는데, 시..