개발하는 개구리

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

🐸 문제 정보 1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 60+m 📝 풀이 이틀동안 풀지 못했다... 처음에 시도했던 방법은 3차원 DP였는데, 해당 분에 뛴 경우와 쉰 경우를 분리해서 마지막에 지침지수가 0인 경우 최대값을 구했다. 하지만 이렇게 풀면 어떻게해도 메모리 초과가 난다... 정말 많이 틀렸다.. 올바른 풀이 방법은 아래와 같다. DP로 풀되, 2차원이면 충분하다. 우선 지침지수가 0인 경우, 즉 dp[i][0]에는 직전에 쉬고 현재 분에도 쉰 거리를 대입한다. dp[..

🐸 문제 정보 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 🤖 알고리즘 브루트포스 (라고 적혀있지만 사실상 구현) ⏱️ 풀이 시간 38.51m 📝 풀이 처음에 문제 이해를 잘못했다. 스위치를 그냥 단순히 껐다 키는 문제라고 생각하고... 5분만에 풀면서 골드 4가 왜이리 쉽지? 생각했다. 1번 테케부터 틀리는거 보고... 아.. 풀이법은 아래와 같다. 첫 번째 행 부터 탐색하며, 아래 조건을 만족하면 해당 행은 스위치 조작으로 밝힐 수 있는 행이다. 행 속 0의 개수가 k보다 작다. 행 속 0의 개..

🐸 문제 정보 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 🤖 알고리즘 브루트포스 ⏱️ 풀이 시간 11.23m 📝 풀이 으악 처음에 순열을 구하면서 n이 아닌 예제처럼 3을 넣어놓고.. 왜안되지 하고 있었다. 간단하게 순열을 구해서 모두 검사하면 되는 문제였다. python의 itertools를 사용하면 아주 쉽게 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys from itertools import permutations input = sys.stdin.readline n, k..

🐸 문제 정보 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 🤖 알고리즘 누적합 ⏱️ 풀이 시간 47.56m 📝 풀이 구현이 껴있는 누적합 문제였다. 문제를 읽자마자 누적합으로 풀어야한다는 것은 바로 알았으나, 이를 구현해내기까지 조금 헤맸다. 헤맨 이유는 '상대의 패도 밑장 뺄 수 있다' 라는 전제 때문이었다. 문제에 전혀 명시가 안되어있고, 마치 내 패에서 밑장을 뺄 수 있는 것처럼 작성되어있지만, 상대에 패에서도 밑장을 뺼 수 있음을 알아야 한다. 홀수 인덱스끼리, 짝수 인덱스끼리 누적합을 구해서..

🐸 문제 정보 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 🤖 알고리즘 DP (라고 하지만, 그냥 수학으로 풀었다.) ⏱️ 풀이 시간 약 10m (중간에 맥 업데이트 오류때문에 잠깐 멈추고 체크를 안함..) 📝 풀이 보자마자 조합문제다! 싶었다. mCn 으로 풀면 되지만, 문제는 itertools의 combinations를 이용하면 세 번째 테케에서 엄청나게 오래 걸린다. 그래서 직접 수를 구해야하나? 싶었지만, math.comb 모듈이 있었다. 이 모듈은 조합을 뽑아주는게 아니라, 조합의 경우의 수를 ..