개발하는 개구리

🐸 문제 정보 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 🤖 알고리즘 이진탐색 ⏱️ 풀이 시간 19.00m 📝 풀이 용액의 점수는 오름차순으로 입력된다. 때문에 start는 0, end는 n-1 인덱스로 잡고 시작한다. 두 점수의 합이 최소값이 되는 순간까지 이진탐색을 실행한다. 만약 두 점수의 합이 0이라면, 이보다 작을 수는 없기 때문에 거기서 멈춘다. 이분탐색은 계속 풀어도 뭔가 붕뜨게 이해되는 느낌이다... 더 더 많이 풀어봐야 할 것 같다. 🧑‍💻 나의 답 # pypy3 import sys..

🐸 문제 정보 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 20.06m 📝 풀이 이 문제의 핵심은 S -> T가 아닌, T -> S로 가야한다는 점이었다. 처음에 S -> T로 가는 백트래킹 코드로 시간초과가 났지만, 같은 로직의 T -> S로 가는 함수를 작성하여 통과할 수 있었다. S -> T의 경우, 두 문자열을 비교한다고는 하지만 T로 가며 무한으로 발산되는 형태임에 반해 T -> S의 경우, 문자을 하나씩 지우기 때문에 ..

🐸 문제 정보 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 🤖 알고리즘 자료구조 ⏱️ 풀이 시간 03.49m 📝 풀이 이런 단순 자료구조 문제의 경우 언어별로 난이도가 너무 달라지기 때문에 아마 실전에서는 안나오지 않을까 싶다. 설명 그대로 최소힙(파이썬에서는 heapq)을 통해 단순히 push, pop하는 문제였다. 🧑‍💻 나의 답 # pypy3 import sys, heapq input = sys.stdin.readline q = [] for _ in range(int(input()..

🐸 문제 정보 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 🤖 알고리즘 이진탐색 ⏱️ 풀이 시간 16.22m 📝 풀이 이진탐색 문제였다. 칭호의 이름과 상한점을 리스트에 넣은 후, start는 0부터, end는 n - 1부터 시작해서 이진탐색을 진행하면 된다. 문제에 이미 비내림차순(==오름차순)으로 정렬되어 입력된다고 적혀있기 때문에, 칭호에 대해서 정렬을 하지 않아도 된다. 마찬가지로 end 역시 입력으로 주어지기에 len으로 길이를 구할 필요 없다. 다른 사람..

🐸 문제 정보 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 14.40m 📝 풀이 구현 치고는.. 그렇게 어려운 편은 아닌 문제였다. n이 0인 경우에 1이 출력되어야하는 케이스를 고려하는 것이 포인트였던 것 같다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, record, p = list(map(int, input().rstrip().split())) if n == 0: print(1)..

🐸 문제 정보 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 38.02m 📝 풀이 BFS임에도 이렇게 오래 걸린 이유는.. 처음에 백트래킹으로 풀었고 + 순서에 따라 답이 달라지는거에 대해 고려하지 못했다. 생각해보면 단순한 BFS문제 같지만, 거리를 계산할 때 순서가 아래와 같아야한다. *2 시간이 늘어나지 않기 때문에 우선순위가 가장 높음 -1 +1 1번은 그렇다 쳐도, 2번 3번에 대한 해답은 질문 게시판을 뒤지다가 알아냈다! 글 ..

🐸 문제 정보 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 🤖 알고리즘 다익스트라 ⏱️ 풀이 시간 30.05m 📝 풀이 최근에 공부한 최단거리 포스팅을 읽어보면 쉽게 풀 수 있는 문제였다. 모든 거리 지점을 노드라고 생각하고, 각 지점에서 다음 지점까지 가중치 1씩을 기본으로 설정했다. 그리고 지름길이 있는 부분에 간선을 추가하여 다익스트라를 돌리면 되는 문제였다. 최단 경로 찾기 with Python 🌊 최단 경로 찾기 알고리즘 🐸 이해하기 최단경로 찾기 알고리즘? 노드 간 가중치가 주어질 때..

🐸 문제 정보 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 🤖 알고리즘 문자열 ⏱️ 풀이 시간 25m 📝 풀이 처음에 딕셔너리로 풀었다가 25점을 받고 그냥 문자열로 풀었다. 관건은, 1은 왼쪽에서부터 지우고 0은 오른쪽에서부터 지우는 것이었다. 문자열로 풀면 간단한데, 파이썬 리스트에서 우측부터 index를 찾는 메서드가 없다는 사실에 약간 충격 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline nums = list(input().rstrip(..

🐸 문제 정보 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 17.29m 📝 풀이 투포인터로 풀어야하는 문제인가..?하고 5분정도 삽질하다가 그리디로 해결했다. 생각보다 시간초과도 안나고 단순하게 풀 수 있는 문제였다. 왼쪽부터 오른쪽으로 탐색 이때 테이블 리스트에는 왼쪽과 오른쪽에 k개 만큼 추가 요소가 있어야 함 2번의 탐색 단계에서 의미 없는 조건문이 필요하지 않도록 현재 인덱스에 'P'가 나온 경우 주변 검색 현재 인덱스부터 좌k 우k 에 'H'가 있다면, 그 'H..

🐸 문제 정보 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 50.34m 📝 풀이 실버 3에서 이렇게 많은 시간을 쓰다니... 약간 멘탈이 갈렸다. 분명 맞게 푼 것 같은데 중간에 아이디어가 잘못되었다는 것을 깨닫고 고치다가 결국 검색으로 아이디어를 얻었다. 사실 단순한데, 한글자씩 비교해가며 순서에 맞게 포함되었는지 확인하는 방법이었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline prev = 0 nums = inpu..