개발하는 개구리

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

🐸 문제 정보 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤖 알고리즘 SQL ⏱️ 풀이 시간 - 📝 풀이 요 며칠 SQL 문제를 아주 공장처럼 풀고 NCS도 풀어보느라 글을 못올렸는데, 이 문제는 너무 어려워서 아카이빙 해두는게 좋을 것 같아 올리게 되었다. 기억해두면 좋을 내용은 아래와 같다. LEFT OUTER JOIN으로 할인 정보를 조인했지만, 할인하지 않는 경우에는 NULL로 붙게된다. 때문에 IFNULL 을 통해 할인이 없는 경우에 할인율을 0으로 치환해야한다. DURATION_TYPEC이 숫자와 문자의 혼용인데, 여기서 숫자만 추출하기 위..