개발하는 개구리

🐸 문제 정보 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이 숫자와 문자의 혼용인데, 여기서 숫자만 추출하기 위..

🐸 문제 정보 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 모듈이 있었다. 이 모듈은 조합을 뽑아주는게 아니라, 조합의 경우의 수를 ..

🐸 문제 정보 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 20.59 📝 풀이 간단한 조건이 추가된 이분탐색 문제였다. 크게 어려운 것 같진 않았는데 여전히 어느 상황에서 start와 end 값을 뭘로 바꾸어야하는지 헷갈린다. 사실 나무 길이를 구하는 과정 때문에 시간초과가 당연히 날거라고 생각했는데 이게 안나네...? 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, m = ..

🐸 문제 정보 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 🤖 알고리즘 정렬 ⏱️ 풀이 시간 05.38m 📝 풀이 이제 파이썬 정렬은 웬만하면 쉽게 풀 수 있다..! 단어를 딕셔너리로 관리하면서, 단순히 조건대로 정렬해줬다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, m = list(map(int, input().rstrip().split())) words = {} for _ in..

🐸 문제 정보 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 예전에 한 번 풀었던 문제인데도 기억을 못해서 오래걸렸다.. 알파벳 26개에 대해, 가르쳤는지 여부를 알 수 있는 26개의 요소 리스트를 선언한다. 각 알파벳에 대해서 True(가르침)을 넣어보고 학생이 총 알 수 있는 단어의 개수를 파악한 뒤, 해당 알파벳을 False(가르치지 않음)으로 바꿔보면서 백트래킹을 실시한다. 🧑‍💻 나의 답 # pypy3 import sys input = ..