개발하는 개구리

🐸 문제 정보 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 43.56m 📝 풀이 처음에 당연히 BFS라고 생각하고 푸는 바람에 어마어마하게 시간이 소요됐다. 이후에 DP + 누적합인 것을 알았음에도 풀이 방법이 바로 떠오르지 않았다. 사실 DP 문제들 중에서는 점화식을 찾기 쉬운 편의 문제였음에도 이렇게 시간이 오래 걸린다는 것은... DP에 대한 연습이 부족하다는 것은 당연하고, DP는 연습해도 실전에서 못풀 가능성이 높다는게 무슨 소리인지 느낄 수 있었다. 누적합으로 (0,0..

🐸 문제 정보 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1

🐸 문제 정보 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 06.23m 📝 풀이 보자마자 그리디 같다고 느껴졌다. 도시를 정방향으로 순회하면서, 주유소 리터 당 값의 최소값을 새로 갱신해준다. 현재까지 나온 리터 당 최소 값을 다음 도시로 이동하는 거리만큼 곱해서 더해준다. 간단한 그리디 문제였다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline INF = sys.maxsize n = int(input().r..

🐸 문제 정보 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤖 알고리즘 SQL ⏱️ 풀이 시간 - 📝 풀이 처음에 같은 상품에 대해서 합치는 건줄 알고 조금 헤맸다. 각 테이블에서 해당 조건으로 SELECT하고 UNION으로 합하면 되는 문제였다. 🧑‍💻 나의 답 (SELECT DATE_FORMAT(SALES_DATE, '%Y-%m-%d') AS SALES_DATE, PRODUCT_ID, USER_ID, SALES_AMOUNT FROM ONLINE_SALE WHERE YEAR(SALES_DATE) = 2022 AND MONTH(SALES_DATE) = ..

🐸 문제 정보 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤖 알고리즘 SQL ⏱️ 풀이 시간 - 📝 풀이 아래 몇 가지에 대해서만 유의하면 되는 문제였다. (REST_INFO는 A, REST_REVIEW는 B로 치환하였다) B의 REVIEW_SCORE는 AVG()로 평균을 구한다. 평균 값은 ROUND()로 소수점 둘째 자리에서 반올림한다. 올림은 CEILING() 버림은 FLOOR() A의 REST_ID로 GROUP BY한다 GROUP BY 과정에서 A의 ADDRESS가 '서울' 이라는 문자를 포함해야한다. LIKE '서울%'로 서울 뒤에 있는 문자..

🐸 문제 정보 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 08.05m 📝 풀이 직전 문제와 같이, 간단한 그리디 문제였다. 처음에 문제 이해를 잘못해서 약간의 시간이 더 소요되었다. 스택을 통해 연속된 0 또는 연속된 1의 개수를 파악한다 연속된 수의 개수가 더 작은 수의 개수를 출력한다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline nums = [0, 0] stack = [] for le in list(map(in..

🐸 문제 정보 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 06.12m 📝 풀이 아주 간단한 그리디 문제였다. 풀이 순서는 아래와 같다. 점수를 뒤에서부터 순회한다. 현재 요소가 직전 요소보다 크거나 같다면, 직전 요소보다 1 작은 수를 대입한다. 이 때 현재 요소의 원래 값과 직전 요소보다 1 작은 수의 차이가 점수를 감소시키는 횟수이며, 이것의 총합이 답이다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = ..

🐸 문제 정보 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 60m + 📝 풀이 문제가 난해하고 지문이 불친절해서 진짜 코테를 보는 것 같았다. 인덱스로 접하는 경우가 많은 것 같아, 처음에는 리스트로 풀다가 후에 회전 문제를 고치면서 deque로 바꿨다. 단계를 잘 나누어서 풀어야하는 것 같다. 벨트와 로봇 큐를 시계 방향으로 1만큼 회전 역순 순회하면서 로봇 이동 현재 자리에 로봇이 있어야함 시계 방향 다음 자리에 로봇이 없어야함 시계 방향 다음 자리..

🐸 문제 정보 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 10.06m 📝 풀이 BFS의 정석 같은 문제였다. 딱히 구현이 추가되거나 복잡하게 꼬여있는 것 없이, BFS 이론만 적용해서 풀 수 있는 문제였다. 도달하지 못하는 곳에는 -1을 넣어줘야하는게 복잡해 보일 수 있지만, 오히려 -1로 새로운 지도 배열을 선언해놓고 BFS 돌면서 값을 채워준다면 도달하지 못하는 곳에 자연스럽게 -1이 남게된다. 🧑‍💻 나의 답 # pypy..

🐸 문제 정보 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 34.18m 📝 풀이 단순한(?) 구현 문제였다. 일단 모든 문자를 딕셔너리로 처리하며, 단어 안에 해당 문자의 개수를 저장했다. 그리고 첫 번째 단어, 즉 기준이 되는 단어의 길이를 확인하여 기준 점수로 저장했다. 이후 과정은 아래와 같다. 두 번째 단어부터 반복을 돈다. (이 때 임시 점수 변수를 선언한다) 기준이 되는 단어와 같은 단어는 +1, 없거나 다른 단어는 -1을 해준다. 기준 점수와 임시 점수를 비..