개발하는 개구리

🐸 문제 정보 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 15.14m 📝 풀이 처음에 숫자 야구 규칙을 직접 코드로 구현해야하나..? 하고 헉 했는데, 알고보니 그냥 순열에서 조건 맞지 않는 요소를 제거하는 문제였다. 파이썬이니까 permutation 쓰고, set으로 시간복잡도를 조금이라도 줄이고자 했다. 🧑‍💻 나의 답 # pypy3 import sys from itertools import permutations input = sys.stdin.readline n ..

🐸 문제 정보 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 12.49m + a 📝 풀이 골3치고 너무 쉬워서 후딱 풀었는데... 뭔갈 놓친건지 계속 틀리다가 겨우 고쳐서 맞았다ㅠㅠ 풀이자체는 아이디어가 떠오르는대로, 숫자를 하나씩 스택에 넣지만, 앞에 해당 수보다 작은 수가 있다면 k번까지 pop 해주는 식으로 풀었다. 핵심은 이 pop 횟수에 따라 결과 출력이 달라진다는 점이었다. 때문에 k값 자체에 변동을 줘서, k가 0일 경우와 아닐경우를 분리해서 출력했더니 맞았다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.st..

🐸 문제 정보 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 24.36m 📝 풀이 간단한 백트래킹 문제인데도, 재귀 내부 로직이 잘 안떠올라서 정답을 참고했다ㅠㅠ 임의의 수열을 만드는 재귀 함수인데, 다 풀고나니 그냥 permutation 써도 됐겠다는 생각이 들었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) nums = list(map(int, input().rstrip().spli..

🐸 문제 정보 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🤖 알고리즘 유니온파인드 ⏱️ 풀이 시간 failed 📝 풀이 너무 오랜만에 유니온 파인드라 결국 예전에 작성해뒀던 아카이브를 찾아봤다ㅠㅠ 예전 벨로그에서 작성했던 유니온 파인드 관련 글이다. velog velog.io 유니온 파인드로 각 노드 별 연결 여부를 찾아내면 나머지는 쉽게 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline def find(x): if parent[x] != ..

🐸 문제 정보 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 12.43m 📝 풀이 시간복잡도 무조건 터질거라고 생각했는데 바로 성공해서 읭 한 문제였다. 문제 수가 15개 밖에 안되니까, 문제 내용대로 직관적인 백트래킹 함수를 작성했다. (현재 인덱스, 현재까지의 합, 최소, 최대)를 인자로 전달하는 백트래킹 함수 합이 L과 R 사이이고, 최대 - 최소가 X보다 크거나 같다면 res 갱신 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, l, r, x = list(map(int, input().rstrip().split())) a ..

🐸 문제 정보 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 32.00m 📝 풀이 처음에 2차원 리스트 보이자마자 BFS로 풀었다가 메모리 터지고... 백트래킹으로 풀어야한다는 것을 알게됐다. 이런 2차원 리스트 주어졌을 때 그냥 생각 안하고 BFS로 푸는 습관좀 고쳐야겠다. 백트래킹으로 푸는 경우 풀이는 아래와 같다. 집의 인덱스와, 민트초코 우유가 있는 인덱스 모두를 찾기 집의 인덱스부터 시작해서, 민트초코 우유의 인덱스로 하나씩 이동해보기 이때, ..

🐸 문제 정보 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이 될 때 까지 반복 이제 흐름에 따라 자세한 방법과 식은 아래와 같..