개발하는 개구리

🐸 문제 정보 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 18.31m 📝 풀이 쉬운 구현 문제였다. 뒤에서부터 순회하면서 아래 조건대로 정답 리스트에 (인덱스 + 1)을 추가해주면 되는 문제였다. 왼쪽에 나보다 큰 사람이 없다면, 정답 리스트 가장 왼쪽에 (인덱스 + 1) 추가 왼쪽에 나보다 큰 사람이 있지만, 내 순서가 정답 리스트의 길이보다 작다면, 내 순서가 될 자리에 (인덱스 + 1) 추가 왼쪽에 나보다 큰 사람밖에 없다면, 정답 리스트 가장 오른쪽에 (인..

🐸 문제 정보 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 🤖 알고리즘 우선순위 큐 ⏱️ 풀이 시간 22.33m 📝 풀이 구현처럼 풀다가 실패해서 검색으로 아이디어를 얻었다. 우선순위 큐로 푸는 문제였고, n*n이기 때문에 큐의 범위를 n만큼 유지한다면 마지막 줄까지 돌았을 때 0번째에 위치한 원소가 n번째 큰 수가 되었다. 오늘은 집중이 잘 안되는 날이다ㄷㄷ 🧑‍💻 나의 답 # pypy3 import sys, heapq input = sys.stdin.readline n = int(input().rstrip()..

🐸 문제 정보 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 failed 📝 풀이 dp로 풀다가 도저히 모르겠어서 찾아보니 그리디였다........ 그리디로 푸는 방법은 생각보다 간단했다. 직전 전구만 비교하되, 첫 번째 전구의 경우에는 직전 전구가 없기 때문에 첫번째 전구를 건들지 않고 시작한 경우와 / 첫번째 전구를 건들고 시작한 경우 두개로 나눠서 비교하면 되는 문제였다. 🧑‍💻 나의 답 import sys input = sys.stdin..

🐸 문제 정보 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 🤖 알고리즘 스택 (이라고 적혀있지만 구현에 가깝다) ⏱️ 풀이 시간 30.25m 📝 풀이 보자마자 스택 문제인 것은 알았지만, 스택보다는 구현에 가까운 문제였다. 가장 높은 지점을 기준으로, 왼쪽 오른쪽에서 최대값은 의미가 없다는 것을 알아야했다. 때문에 입력 값에서 가장 높은 지점의 인덱스를 찾은 후, 그 지점을 기준으로 왼쪽 오른쪽 각 1회씩 탐색하면서 스택 형태로 값을 더해주면 되는 문제였다. 문제에서 모든 인덱스에 h가 있..

🐸 문제 정보 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에서 하나씩 지우며, 길이를 구해서 출력한다. 이전 글에서 사용한 키워드는 지우지 않는다. 🧑‍💻 나의 ..