개발하는 개구리

🐸 문제 정보 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 60m+ 📝 풀이 생각보다 어려운 문제였다ㅠㅠ 처음에는 투포인터를 이용해서 앞부터 순회하며, start가 1커진다면 이전 start에서 구한 수열 - 1 개로 초기화되는 방식(dp + 투포인터)으로 구현하였으나 start와 end가 같아지는 시점에서 예외처리가 너무 많아 포기하게 됐다. 검색을 통해 end에서 start를 빼주면서 개수를 더해주는 아이디어를 얻었는데, 풀고나서 보니 대부분의 사람들이 dictionary를..

🐸 문제 정보 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 failed 📝 풀이 오랜만에 failed... 문제를 보고 DP라는 것은 알았으나, 도저히 점화식과 아이디어가 떠오르지 않았다. 그리고 결국 검색해서 풀이를 살펴보니 LIS(가장 긴 증가하는 부분수열) 문제라는 것을 깨달았다. 유사한 문제는 이전에도 풀어본 적 있는데, 이 문제가 도대체 왜 LIS 문제지? 라고 생각했으나 이 문제의 입력에서 도출되는 가장 긴 증가하는 부분 수열은 곧 제대로 된 위치에 있는 아이들과 같기..

🐸 문제 정보 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 🤖 알고리즘 다익스트라 ⏱️ 풀이 시간 07.49m 📝 풀이 다익스트라 + 최단경로 구하기의 정석같은 문제였다. 별 다른 구현 없이, 다익스트라 알고리즘만 구현할 수 있으면 풀 수 있었다. 해당 알고리즘은 이전에 정리해둔 포스팅이 있으니 아래에서 참고하면 좋을 것 같다. 최단 경로 찾기 with Python 🌊 최단 경로 찾기 알고리즘 🐸 이해하기 최단경로 찾기 알고리즘? 노드 간 가중치가 주어질 때, 시작 노드부터 모든 노드까지의 최소값을 구하는 알고리즘..

🐸 문제 정보 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 30m + (체크를 못했다...) 📝 풀이 조금 신기한..? 이상한..? 문제였다. 슬라이딩 윈도우로 푸는데, 조건문으로 검사하지 않고 모든 경우에서 적용할 수 있도록 코드를 작성하면 시간초과가 발생했다. 틀린 코드는 아래에서 볼 수 있다. 더보기 import sys input = sys.stdin.readline n, d, k, c = map(int, input(..

🐸 문제 정보 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이 발생하는지 여부에 따라 음수 가중치로 끝날지 ..