개발하는 개구리

🐸 문제 정보 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 🤖 알고리즘 정렬 ⏱️ 풀이 시간 26.48m 📝 풀이 직관적으로 떠오르는대로 정렬하면 금방 풀 수 있었는데 괜히 꼬아서 보다가 삽질해버렸다.. 풀이방법은 아래와 같다. 점수 합계 정산을 위한 딕셔너리 / 제출 횟수를 알기 위한 리스트 / 마지막 제출 시간을 알기 위한 리스트 초기화 딕셔너리의 경우, key는 팀 ID / value는 문제 당 점수 리스트 문제에서 지시한대로, 아래 순서에 따라 정렬 후 본인 팀 ID의 인덱스 + 1 팀 별 점수 합계 내림..

🐸 문제 정보 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 25.15m 📝 풀이 오름차순으로 정렬했음에도 0번 인덱스부터, 그리고 해당 인덱스를 제외하고 투포인터를 진행해야한다는 것을 놓쳤다. 아마 정답률이 낮은 것도 나같은 사람이 많아서지 않을까 싶다. 입력 숫자 리스트 오름차순 정렬 0번 인덱스부터 끝까지 순회 특정 인덱스에 해당하는 숫자를 제외하고, 투포인터를 이용해서 해당 숫자를 만들어 낼 수 있는지 검사 start는 0부터, end는 해당 숫자를 제외한 리스트의 마지막 인덱스부터 만약 s..

🐸 문제 정보 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 15.53m 📝 풀이 비교적 간단한 투포인터 문제였다. 마지막까지 전부 통과한 경우에 길이를 출력하는 것을 잊어 약간의 시간이 더 걸렸다. start와 end 모두 0부터 시작 end를 하나씩 뒤로 이동하며 딕셔너리에 담기 end 인덱스에 해당하는 숫자의 개수가 k보다 많다면, 우선 end - start를 res와 비교하여 더 큰 값 넣기 start를 뒤로 하나씩 이동하며 딕셔너리에서 해당 인덱스의 숫자를 ..

🐸 문제 정보 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 dfs ⏱️ 풀이 시간 22.22m 📝 풀이 처음에 그냥 가중치 그래프 보자마자 허겁지겁 bfs로 풀어버렸다.. 15분 쯤 되어서야 뭔가 이상함을 감지하고 dfs로 변경했다. 하지만 dfs도 n과 m의 범위가 커지면 통과하지 못할 것 같다는 생각이 들었는데, 아니나 다를까 문제에 표기된 알고리즘은 DP였다. 아마 Large에서는 DP로 풀어야 통과되지 않을까 싶다. 우선 이 여기에서는 간단하게 방향을 잡아..

🐸 문제 정보 25757번: 임스와 함께하는 미니게임 첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들 www.acmicpc.net 🤖 알고리즘 해시를 사용한 집합과 맵 ⏱️ 풀이 시간 05.08m 📝 풀이 너무 간단한 문제였다. 동일인과는 게임을 여러번 할 수 없기 때문에 입력을 모두 set에 넣어 중복을 제거하였고, 각 게임마다 임스를 제외한 숫자를 담은 딕셔너리를 통해 최대 몇 판의 게임을 할 수 있는지 구했다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, game = li..

🐸 문제 정보 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 🤖 알고리즘 벨만포드 ⏱️ 풀이 시간 26.27m 📝 풀이 벨만포드 알고리즘을 이용하면 쉽게(?) 풀 수 있는 문제였다. 그럼에도 오래걸린 이유는 INF 값의 처리 때문이었다... 여튼 해당 몬제에서 유의할 점은 아래와 같다. 도로의 경우, 양방향이기 때문에 시작점과 끝점 총 두번을 append 해줘야한다. 웜홀은 단방향이지만, 가중치가 음수이다. 어느점에서 시작해도 상관없다. cycle이 발생하는지 여부에 따라 음수 가중치로 끝날지 ..

🐸 문제 정보 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 🤖 알고리즘 이진탐색 ⏱️ 풀이 시간 19.00m 📝 풀이 용액의 점수는 오름차순으로 입력된다. 때문에 start는 0, end는 n-1 인덱스로 잡고 시작한다. 두 점수의 합이 최소값이 되는 순간까지 이진탐색을 실행한다. 만약 두 점수의 합이 0이라면, 이보다 작을 수는 없기 때문에 거기서 멈춘다. 이분탐색은 계속 풀어도 뭔가 붕뜨게 이해되는 느낌이다... 더 더 많이 풀어봐야 할 것 같다. 🧑‍💻 나의 답 # pypy3 import sys..

🐸 문제 정보 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 20.06m 📝 풀이 이 문제의 핵심은 S -> T가 아닌, T -> S로 가야한다는 점이었다. 처음에 S -> T로 가는 백트래킹 코드로 시간초과가 났지만, 같은 로직의 T -> S로 가는 함수를 작성하여 통과할 수 있었다. S -> T의 경우, 두 문자열을 비교한다고는 하지만 T로 가며 무한으로 발산되는 형태임에 반해 T -> S의 경우, 문자을 하나씩 지우기 때문에 ..

🐸 문제 정보 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 🤖 알고리즘 자료구조 ⏱️ 풀이 시간 03.49m 📝 풀이 이런 단순 자료구조 문제의 경우 언어별로 난이도가 너무 달라지기 때문에 아마 실전에서는 안나오지 않을까 싶다. 설명 그대로 최소힙(파이썬에서는 heapq)을 통해 단순히 push, pop하는 문제였다. 🧑‍💻 나의 답 # pypy3 import sys, heapq input = sys.stdin.readline q = [] for _ in range(int(input()..

🐸 문제 정보 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 🤖 알고리즘 이진탐색 ⏱️ 풀이 시간 16.22m 📝 풀이 이진탐색 문제였다. 칭호의 이름과 상한점을 리스트에 넣은 후, start는 0부터, end는 n - 1부터 시작해서 이진탐색을 진행하면 된다. 문제에 이미 비내림차순(==오름차순)으로 정렬되어 입력된다고 적혀있기 때문에, 칭호에 대해서 정렬을 하지 않아도 된다. 마찬가지로 end 역시 입력으로 주어지기에 len으로 길이를 구할 필요 없다. 다른 사람..