막내의 막무가내 프로그래밍 & 일상

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 프로그래머스 LV3 동적계획법(DP) 문제 등굣길을 풀어봤습니다. 집에서 학교까지 웅덩이를 피해 갈 수 있는 모든 최단 경로의 수를 구하면 되는 문제였습니다. 집은 1,1 학교는 n,m 에 있고 최단 거리만 계산하면 되므로 상하좌우가 아닌 우측과 하단으로 이동만 하면 됩니다. row와 col 인덱스로 이루어진 이중 배열을 만들고 값으로는 해당 지점까지 오는데까지의 ..

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 백준 BFS 유형의 백준 2146 다리만들기 문제입니다. 여러개의 섬이(1) 있는데 바다에(0) 최소의 다리 개수를 설치하여 여러개의 섬들 중 두 개의 섬을 이을 수 있게 하려는 문제 입니다. BFS를 살짝 응용한 문제입니다. 처음에 너무 비효율적으로 자원을 소비하는건가 했는데 통과되었습니다. 풀이를 간략히 설명하면, 1. 섬마다 번호가 똑같으므로 바로 BFS로 다른 섬을 찾아 연결하기가 힘듭니다. 그러므로 섬에 각..

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 백준 이분탐색 유형 문제입니다. 지방마다 갖고 있는 예산이 다른데 국가에서 총 예산 M 이하를 걷으려고합니다. 총 M이하의 예산이하라는 조건에서 지방마다 최대 얼마를 걷을 수 있는지 구하는 문제입니다. N의 개수를 보아 완전탐색으로 풀면 시간초과가 뜰겁니다. 이분탐색으로 풀어야합니다. 이분탐색에서 left 는 0 (최소 예산) right 는 지방예산중 가장 큰 금액 (최대 예산) 으로 하여 탐색을 시작합니..