개발하는 개구리

🐸 문제 정보 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 🤖 알고리즘 오일러 경로 (유니온 파인드 + 그래프 탐색) ⏱️ 풀이 시간 60m+ (중간에 오일러 경로의 조건을 찾아보느라 길어졌다.) 📝 풀이 오일러 경로는 한 붓 그리기와 같다. 오일러 경로가 성립하기 위해서는 총 두가지 조건에 만족해야한다. 모든 정점이 연결되어있어야한다. 차수(연결된 노드 수)의 두 규칙 중 한개를 만족해야한다. 모든 노드의 차수가 짝수이다. 두 노드의 차수는 홀수, 나머지 노드는 짝수이다. ..

🐸 문제 정보 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 🤖 알고리즘 그리디, 구현 ⏱️ 풀이 시간 12.59m 📝 풀이 예제를 직접 손으로 그려보면 그리디라는 것을 쉽게 파악할 수 있었다. 각각 최대값과 최소값을 찾는 순서는 아래와 같다. 둘다 기본적으로 주어진 입력에 대해 앞에서부터 순회한다. 최대값 M이 나오면 stack에 담는다. K가 나오면 K를 포함한 stack의 길이(n) 만큼 5 * (10 ^ (n - 1))를 문자열로 바꿔 정답 문자열에 더해준다. 마지막에 stack에 담겨진 M을 모두 1로 치환하여 정답 문자열에 더해준다. 최소값 M이 나오면 stack에 담는다. K..

🐸 문제 정보 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 🤖 알고리즘 힙 ⏱️ 풀이 시간 06.24m 📝 풀이 heapq를 이용하면 간단히 풀 수 있는 문제였다. 파이썬 heapq는 최소힙 구조이기 때문에, 음수를 붙여서 저장하고 출력할때 다시 음수를 붙여서 원래대로 바꾸는 형태로 구현했다. 🧑‍💻 나의 답 # pypy3 import sys import heapq input = sys.stdin.readline q = [] for _ in range(int(input().rstrip..

🐸 문제 정보 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 🤖 알고리즘 수학 ⏱️ 풀이 시간 15.12m 📝 풀이 단순한 스택 문제라고 생각했는데, 기울기를 비교해야하는 수학 문제였다. 오히려 스택보다 조건 자체는 쉽다. 오른쪽으로 이동하면서 이전까지 나왔던 최대 기울기보다 큰 기울기가 나와야만 1개를 추가해준다. A와 B 빌딩 서로 볼 수 있기 때문에 두 요소 모두 1을 추가해야한다. 이런식으로 모든 요소를 탐색하면 되는 문제였다. 🧑‍💻 나의 답 # pypy3 import sys input = sys...

🐸 문제 정보 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 14.41m 📝 풀이 처음에 순열로 풀어야하는 문제라고 생각해서... 도대체 어떻게 풀어야하지?! 고민했는데 다시 천천히 생각해보니 그냥 Counter 써서 뒤에 뭐올지 백트래킹해도 될 것 같다고 느꼈다. 이유는 문자열 길이가 10까지밖에 안돼서... 이미 예제에 나와있는 경우가 최악의 경우였다. 🧑‍💻 나의 답 # pypy3 import sys from collections import Counter input =..

🐸 문제 정보 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 30.20m 📝 풀이 그냥 BFS로 절대 통과 못할 줄 알았는데... 시간이 간당간당하게 맞은 것 같다. 구현이랑 섞인 BFS의 대표적인 문제 같은 느낌이었다. 나의 경우, 바이러스를 올릴 수 있는 노드와, 벽의 노드를 입력 때 미리 저장해두고 바이러스를 올릴 수 있는 노드에서 m개 만큼의 조합으로 BFS를 돌린 후, 벽의 노드를 제외한 노드가 모두 방문처리 되었는지 확인했다. 코드가 꽤 복잡하게 짜여진 것 같..다.. ..

🐸 문제 정보 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 17.15m 📝 풀이 아주 오래전에.. 2년 전에 풀었던 문제인 것 같다. 알고리즘이 열려있어서 우연찮게 DP라는 걸 봐버렸는데ㅠ 처음에 그리디로 풀려다가 DP로 풀어야하나?! 하고 괜히 고민하느라 더 오래걸렸다. 그냥 그리디로 풀면 쉽게 풀 수 있는 문제였다. 남은 설탕 무게가 5의 배수라면, 5로 나눈 몫만큼 개수 더해주고 반복문 탈출 기본적으로 남은 무게에서 3키로씩 빼주면서 반복 반복문 탈출 후, 남은 무게가 0키로..

🐸 문제 정보 22868번: 산책 (small) 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 26.22m 📝 풀이 문제를 보고 이분탐색으로 풀어야된다는 것은 알았으나... 정확한 아이디어가 떠오르지 않아 검색의 힘을 빌렸다. 처음에는 mid와 근사한 값에 공유기를 위치시키는 형태로 이분탐색을 생각했었는데, 그게 아니라 mid는 두 집 사이의 거리로 두고, 그 거리만큼 공유기를 두었을 때 비치할 수 있는 공유기의 개수로 정답을 파악하는 형식이었다. 이때 start와 end의 값을 평소처..

🐸 문제 정보 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 🤖 알고리즘 유니온 파인드 ⏱️ 풀이 시간 16.43m 📝 풀이 유니온 파인드의 정석같은 문제였다. 그래프가 연결되어있는지 찾아야하는데, 시간이 조금 걸렸던 이유는 마지막에 parent[a]와 parent[b]를 비교했다.. find(a)와 find(b)로 고쳐서 통과할 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline def find(x): if par..

🐸 문제 정보 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 35.48m (failed) 📝 풀이 DP는 어렵다... 점화식이 안떠올라서 결국 검색으로 아이디어를 얻었다. 3차원 DP 리스트 선언 [row][col][직전 방향] 현재 방향과 다른 방향의 직전 요소들 중, 최솟값을 현재 요소와 더해줌 이 때, 각 행의 0번째 열과 마지막 열의 경우, 직전 방향에 유의해야함 0번째 열은 직전 ↘ 방향이 없다 마지막 열은 직전 ↙ 방향이 없다..