개발하는 개구리

🐸 문제 정보 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 11.48m 📝 풀이 문제 내용이 너무 웃겼닼ㅋㅋㅋ 심지어 문제 자체도 괜찮아서 즐겁게 풀 수 있었다. 0, 0 부터 시작하면서 사방으로 이동하는 BFS 함수를 만든다 해당 함수의 경우, 이전에 방문 여부 대신 비용을 비교한다. 해당 지점까지 필요한 비용이 더 적은 경우에만 방문한다. 때문에 가격을 비교하는 배열의 초기값은 sys.maxsize로 설정했다. 🧑‍💻 나의 답 # pypy3 impo..

🐸 문제 정보 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 🤖 알고리즘 DFS ⏱️ 풀이 시간 38.36m 📝 풀이 cycle을 찾으면 되는 문제인 것은 알겠으나... 구현하는 것이 생각보다 어려웠던 문제였다ㅠㅠ DFS로 푸는데, 이번에 확인할 노드를 인자로 전달 받아서, 시작했던 노드와 다시 만나면 res에 해당 노드를 넣어주는 방식으로 풀었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) g..

🐸 문제 정보 3005번: 크로스워드 퍼즐 쳐다보기 첫째 줄에 R과 C (2 ≤ R, C ≤ 20)가 주어진다. R는 행의 개수, C는 열의 개수이다. 그 다음 R개의 줄엔 C개의 문자가 포함되어 있다. 각 문자는 영어 알파벳 소문자 또는 '#'이며, '#'인 경우에는 막혀 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 21.34 📝 풀이 처음에 문제 이해도 안되고, BFS로 풀어야하나 하고 조금 고민하느라 시간이 오래 걸렸다. 그냥 십자말풀이라고 적어놓지... 왜 크로스워드 퍼즐이라고 적어놨을까.... 여튼 풀이 방법 자체는 간단했다. 행과 열을 문자열로 각각 분리 각 행과 열에 대해서 #으로 split 길이가 1 이상이라면 substring 조건에 충족하므로, res 배열에 담기 re..

🐸 문제 정보 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 31.25m 📝 풀이 그리디처럼 풀면서 최적의 방법을 찾다가... 계속 틀리길래 '이게 맞나'란 생각이 들었다. 알고보니 그냥 생구현으로 풀 수 있는 아주 쉬운 문제였다ㅠㅠ 처음에는, 단어를 정렬해서 사전 순 앞에 나오는 문자의 인덱스를 뒤에서 부터 찾아내고 잘라서 넣는.. 과정을 거쳤다. 틀린 풀이 더보기 import sys input = sys.stdin.readline word = input().rstrip()..

🐸 문제 정보 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 14.41m 📝 풀이 처음에 괜한 도전정신으로 힙으로 풀어보려다가 숫자 개수 보고 정신차리고 제대로 풀었다. 간단한 투포인터 문제이고, 두 리스트에 맨 처음부터 움직이는 인덱스를 두어 값을 비교하면서 하나씩 채워나가면 된다. 어차피 둘 다 정렬된 배열이기 때문에, 한 리스트에서 인덱스가 끝에 도착하면 나머지 리스트의 나머지 값은 그냥 더해주면 된다. 🧑‍💻 나의 답 # pypy..

🐸 문제 정보 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 14.58m 📝 풀이 최근에 투포인터랑 슬라이딩 윈도우를 많이 풀어서 쉽게 풀 수 있었다. start = 0, end = k로 시작한다. (어차피 k개는 필수로 들어가야하기 때문) 이때 사이에 있는 1의 값은 미리 카운트하여 선언한다. end가 n이 될 때까지 아래 조건에 따라 인덱스를 움직이며 계산한다. 1의 개수가 k개와 같다면 현재 거리를 res와 비교하여 최솟값으로 저장한다 start 인덱스에..

🐸 문제 정보 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 🤖 알고리즘 누적합 ⏱️ 풀이 시간 13.22m 📝 풀이 그래프를 그려보고 누적합 테이블을 구하는 원리와, 답을 찾는 원리를 알아냈더니 쉽게 풀 수 있었다. 누적합 테이블 구하기 pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] 구간 합 구하기 pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 ..

🐸 문제 정보 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 28.16m 📝 풀이 백트래킹으로 풀면 되는 문제였다. 새로운 배열을 복사해서 전달해주는 방식보다는, 기존 배열 하나에서 재귀 시킨 후 다시 원상 복구 해주는 방식으로 진행했다. 아래 조건만 잊지 않으면 어렵지 않게 풀 수 있는 문제였다. 계란을 첫 인덱스부터 탐색하지만, 이미 깨져있는 경우나 본인인 경우는 패스해주는 것 깰 계란이 없으면 그냥 넘겨줄 것 본인이 이미 깨져있으면 그냥 넘겨줄 것 🧑‍..

🐸 문제 정보 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 🤖 알고리즘 DFS ⏱️ 풀이 시간 07.51m 📝 풀이 MST 같아 보이지만 DFS 문제이다. 입력 값을 바탕으로 양방향 그래프를 만들어주고, 방문했는지 체크할 visited도 만든다. 이후 그래프를 돌면서, 연결된 노드는 모두 방문처리하고, 방문하지 않은 노드에서 다시 dfs를 시작할 경우 결과 값에 1 더해준다. 🧑‍💻 나의 답 # pypy3 import sys input = sy..

🐸 문제 정보 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 36.01m 📝 풀이 문제가 엄청 복잡해보여서... 무조건 시간초과 or 메모리초과 날거라고 생각했는데 다행히 그렇게 복잡한 문제는 아니었다. 영역 구분할 때 초기 값에 uni를 넣어주는 것을 깜빡해서 1트는 실패했다ㅠ 입력값을 BFS 돌면서 영역 구분 구분된 영역을 돌면서, 사방에 바다가 있는 경우 bfs 시작 dist 리스트를 통해, 다른 영역까지의 거리를 1씩 더해줌 만약 돌다가 다른 영역 만나면 현재 저장된 거..