개발하는 개구리

🐸 문제 정보 16960번: 스위치와 램프 첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 18.47m 📝 풀이 스위치에 연결된 램프의 번호를 딕셔너리 형태로 변경한다. 램프번호 : 개수 스위치를 하나씩 순회하면서, 해당 스위치가 꺼져도 모두 켜져있는지 확인한다. 이 문제에 핵심은 2차원 리스트를 {램프번호 : 개수} 형태의 딕셔너리로 변경하는 것이었다. 파이썬의 내장 모듈이 워낙 강력해서... Counter와 리스트 컴프리헨션으로 쉽게 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import ..

🐸 문제 정보 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🤖 알고리즘 스택 ⏱️ 풀이 시간 18.22m 📝 풀이 왜인지 모르겠지만 엄청 유명한(?) 문제였던걸로 기억한다. 문제 제목을 엄청 많이 들어봤는데, 사실 생각보다 어렵지 않은 문제였다. 문자열을 돌면서 폭탄 문자열의 길이만큼 비교해보고, 만약 폭탄 문자열이 들어간 상태라면 그만큼 pop하면 된다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline string = list(input()..

🐸 문제 정보 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 47.30m 📝 풀이 슬라이딩 윈도우의 정석 같은 문제였다. 풀이 자체가 복잡하지 않은데도, 처음에 k개까지 초기 설정하는 부분에서 헛디뎌서 검색까지했다. 0부터 k-1번 접시까지 개수를 딕셔너리에 초기화한다. 이 때, 쿠폰 접시의 경우 기본적으로 1개를 추가해준다 이후 반복문을 돌면서 start가 n에 닿기 전까지 k개를 슬라이딩 윈도우하며 비교한다. 이 때,..

🐸 문제 정보 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 🤖 알고리즘 분할정복 ⏱️ 풀이 시간 35.34m 📝 풀이 진짜 정말 오랜만에 분할정복 문제였다. 상당히 오래 고민하고... 종이에 많이 적어보면서 풀었다. 우선 기본적인 풀이 흐름은 아래와 같다. 주어진 그래프를 4등분으로 분할 r, c 위치가 어디에 있는지 확인 후, 해당 사분면 이전의 사분면에 속한 수의 개수 더하기 r, c 위치를 분할된 그래프에 맞게 갱신 n이 1이 될 때 까지 반복 이제 흐름에 따라 자세한 방법과 식은 아래와 같..

🐸 문제 정보 5883번: 아이폰 9S 사람 9명이 줄을 서있고 각 사람이 원하는 용량의 크기는 2, 7, 3, 7, 7, 3, 7, 5, 7 이다. 용량 3을 원하는 사람을 줄에서 빼버리면, 줄은 2, 7, 7, 7, 7, 5, 7가 되고, 7을 원하는 사람이 4명이 연속된 구간이 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 12.32m 📝 풀이 처음에 2차원 DP로 풀어야하나 했으나(LCS..?) LCS 개념과는 약간 다른 것 같아 구현으로 풀어봤더니 풀렸다. 구현으로 풀면 간단하게 풀 수 있는 문제였다. set을 이용해서 용량 종류 파악하기 용량 종류를 하나씩 빼서 새로운 배열을 할당하고, 해당 배열에서 연속된 용량의 길이 구하기 마지막에 정답을 한 번 더 갱신해주는 것이 중요하다..

🐸 문제 정보 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 11.48m 📝 풀이 문제 내용이 너무 웃겼닼ㅋㅋㅋ 심지어 문제 자체도 괜찮아서 즐겁게 풀 수 있었다. 0, 0 부터 시작하면서 사방으로 이동하는 BFS 함수를 만든다 해당 함수의 경우, 이전에 방문 여부 대신 비용을 비교한다. 해당 지점까지 필요한 비용이 더 적은 경우에만 방문한다. 때문에 가격을 비교하는 배열의 초기값은 sys.maxsize로 설정했다. 🧑‍💻 나의 답 # pypy3 impo..

🐸 문제 정보 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 🤖 알고리즘 DFS ⏱️ 풀이 시간 38.36m 📝 풀이 cycle을 찾으면 되는 문제인 것은 알겠으나... 구현하는 것이 생각보다 어려웠던 문제였다ㅠㅠ DFS로 푸는데, 이번에 확인할 노드를 인자로 전달 받아서, 시작했던 노드와 다시 만나면 res에 해당 노드를 넣어주는 방식으로 풀었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) g..

🐸 문제 정보 3005번: 크로스워드 퍼즐 쳐다보기 첫째 줄에 R과 C (2 ≤ R, C ≤ 20)가 주어진다. R는 행의 개수, C는 열의 개수이다. 그 다음 R개의 줄엔 C개의 문자가 포함되어 있다. 각 문자는 영어 알파벳 소문자 또는 '#'이며, '#'인 경우에는 막혀 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 21.34 📝 풀이 처음에 문제 이해도 안되고, BFS로 풀어야하나 하고 조금 고민하느라 시간이 오래 걸렸다. 그냥 십자말풀이라고 적어놓지... 왜 크로스워드 퍼즐이라고 적어놨을까.... 여튼 풀이 방법 자체는 간단했다. 행과 열을 문자열로 각각 분리 각 행과 열에 대해서 #으로 split 길이가 1 이상이라면 substring 조건에 충족하므로, res 배열에 담기 re..

🐸 문제 정보 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 31.25m 📝 풀이 그리디처럼 풀면서 최적의 방법을 찾다가... 계속 틀리길래 '이게 맞나'란 생각이 들었다. 알고보니 그냥 생구현으로 풀 수 있는 아주 쉬운 문제였다ㅠㅠ 처음에는, 단어를 정렬해서 사전 순 앞에 나오는 문자의 인덱스를 뒤에서 부터 찾아내고 잘라서 넣는.. 과정을 거쳤다. 틀린 풀이 더보기 import sys input = sys.stdin.readline word = input().rstrip()..

🐸 문제 정보 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 14.41m 📝 풀이 처음에 괜한 도전정신으로 힙으로 풀어보려다가 숫자 개수 보고 정신차리고 제대로 풀었다. 간단한 투포인터 문제이고, 두 리스트에 맨 처음부터 움직이는 인덱스를 두어 값을 비교하면서 하나씩 채워나가면 된다. 어차피 둘 다 정렬된 배열이기 때문에, 한 리스트에서 인덱스가 끝에 도착하면 나머지 리스트의 나머지 값은 그냥 더해주면 된다. 🧑‍💻 나의 답 # pypy..