개발하는 개구리

🐸 문제 정보 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 failed 📝 풀이 이번 문제는 점화식을 끝내 찾지 못하고 검색의 힘을 빌려 풀었다. DP는 DP인걸 알아도 점화식이 안떠오르면 손도 델 수 없는게 너무 슬프다... 풀이는 다른 블로그를 참고했다. 간단히 요약하자면 아래와 같다. 기본적으로 1로만 구성된 경우는 각 숫자마다 1개씩 존재함 숫자 2부터는, (본인 - 2)에서 숫자 1로만 구성된 경우가 곧..

🐸 문제 정보 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 23.15m 📝 풀이 언뜻 보면 굉장히 쉬운 구현 문제이지만, 엄청난 함정이 하나 있었다. (아닐지도 모른다) 나는 처음에 딕셔너리를 이용해서 풀었는데, 예시로 나와있는 테스트 케이스는 통과되지만 4%쯤에서 틀리게된다. 이유는 같은 레벨의 다른 닉네임의 사람이 들어오는 경우, 딕셔너리에 있는 리스트가 덮어씌워지기 때문이다. 만약 비슷하게 풀었고 틀린다면 아례 반례를 입력해보는 것도 좋을 것 같다. 여튼 이 문제는 딕셔너..

🐸 문제 정보 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 32.36m 📝 풀이 오랜만에 찐 구현 문제였다. 드디어...!!! 구현하면서 안써본 파이썬 메서드를 써봤는데 좋았다. zip() 각 iterable에서 동일한 인덱스의 요소를 묶어서 튜플을 생성한다. 예를 들어, 두 개의 리스트를 zip으로 묶으면 각 리스트에서 같은 인덱스의 요소들이 순서대로 튜플로 묶이게 된다. list1 = [1, 2, 3] list2 = ['a', 'b', 'c'] # zip을 사용하여 두 리스트 묶기 zipped = zip(list1, list2) # (1, 'a') # (2..

🐸 문제 정보 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 36.01m 📝 풀이 문제집을 거의 다 풀어가니까 자꾸 푼 알고리즘이 겹쳐서 나오는 것 같다. 물론 이번 문제는 많이 어려웠다..! 역시 문제 이해를 잘못했기 때문이다. 특정 구간에 있는 모든 문자의 개수가 동일한 경우를 찾아야한다고 생각했다... 다시 한 번 문제를 제대로 이해해야겠다는 다짐을 했다. 문제를 제대로 이해하면 풀이 아이디어 자체는 크게 어렵지 않다. 입력된 문자열에서 각 문자가 등장하는..

🐸 문제 정보 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 30m+ 📝 풀이 교환이라는 단어의 뜻이 명확하게 서술되어있지 않아서 한 번 이상하게 풀었다가 다시 풀었다. 이 문제에서 말하는 교환은, 단어 안에서 각 글자간 위치를 변경하는 경우를 말한다. (질문 게시판에 나와 같은 사람이 꽤 있었다...) 우선 문제는 슬라이딩 윈도우로 풀면 그렇게 어렵지 않다. 입력받은 문자열에서 a의 개수를 센다 문자열에서 a개씩 슬라이딩 윈도우하며, 해당 위치에 b의 개수의 최소값..

🐸 문제 정보 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 🤖 알고리즘 해시를 사용한 집합과 맵 ⏱️ 풀이 시간 05.01m 📝 풀이 set을 이용하면 쉽게 풀 수 있는 문제였다. set은 검색과 삭제에 있어서 시간복잡도가 O(1)이기 때문에, 중복이 어차피 없는 이 문제에서는 set을 이용하면 시간 초과 없이 풀 수 있다. 키워드를 set에 담는다 사용한 키워드를 set에서 하나씩 지우며, 길이를 구해서 출력한다. 이전 글에서 사용한 키워드는 지우지 않는다. 🧑‍💻 나의 ..

🐸 문제 정보 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(..