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

www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 백준 그리디 단계별풀기에서 마지막 문제를 안풀어서 이번에 풀어봤습니다. 문제에 대해 간략히 설명하면, 기름값이 다른 도시들이 있고 각 도시는 일렬로 다른거리로 연결되어 있습니다. 도시에 도착했을때 기름*km수 만큼 기름을 채울 수 있다. 마지막도시까지 가는데 필요한 최소 기름값을 출력하면 됩니다. 풀이 방법은 기름값이 이전 도시보다 더 낮은 경우 더 낮은 기름값으로 다음 도시까지의 거리만큼 기름을..

www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 백준 그리디유형의 문제인 뒤집기를 풀어봤습니다. ㅎㅎ 연속된 숫자를 한번에 뒤집을 수 있는데요 (0 or 1) 최소한으로 뒤집어서 모두 같은 숫자를 만들어야합니다. 풀이방법은 0과 1의 연속된 숫자의 묶음이 더 적은 쪽의 묶음의 개수를 답으로 출력해주면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; class Main { private static String S;..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 백준 투포인터 유형에 있는 두 용액이라는 문제를 풀어봤습니다. ㅎㅎ 두 개의 용액을 골라 합이 0하고 가장 가까운 두 용액을 출력해주면 되는 문제입니다. 풀이방법을 간단히 설명하면 1. 용액 배열 정렬 2. 양쪽 끝으로 투 포인터 탐색을 해주면 됩니다. 가장 0하고 가까운 값이 나오면 정답을 갱신해주고 둘의 차이가 양수면 오른쪽 포인터를 더 작은 값을 가진 왼쪽으로 움직음으로써..

www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 백준 2589 보물섬 문제를 풀어봤습니다. ㅎㅎ 백준 브루트포스 유형에서 한 문제를 골라풀었는데 BFS 기본 문제였습니다. 땅끼리 거리가 가장 큰 곳이 보물이 숨어있는 땅이므로 땅인 곳을 모두 BFS 탐색돌려서 가장 먼 경로를 출력하면됩니다. 코틀린의 coerceAtLeast() 라는 함수를 알 수 있던 문제였습니다. 자바에서는 최대값 = Math.Max( 최댓값, 숫자2 ) 이렇게 최댓값을 갱신하지만 코틀린에서는..

www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트랙킹 시리즈문제 중 하나인 백준 15663 N과 M (9)를 풀었습니다. 오름차순으로 숫자들을 나열하되 중복된 숫자는 두 번 출력하면 안되었습니다. 그래서 오름차순으로 정렬하고 set을 이용해 중복된 숫자는 안나오게 백트랙킹을 구현했습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.HashSet; import java.util.Scan..

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 이전 플로이드 문제에 이어 백준 플로이드 워셜 알고리즘 유형에서 한 문제를 풀어봤습니다. 너비우선탐색으로도 풀 수 있지만 플로이드 워셜을 학습하기 위해 플로이드로 풀었습니다. ㅎㅎ 풀이는 다음과 같습니다. [Java] import java.util.Scanner; class Main { private static int n; // 유저의 수 private stat..

www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 알고리즘 플로이드 워셜 유형을 풀어봤습니다. chanhuiseok.github.io/posts/algo-50/ 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io blog.naver.com/ndb796/221234427842 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) ..

programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 프로그래머스 LV2 배달 문제를 풀어봤습니다. ㅎㅎ 1번 마을에서 K 이하의 시간으로 배달을 갈 수 있는 마을의 개수를 구하는 문제입니다. 그래서 1번 마을에서 각 마을간의 최단경로(최단시간)를 구해서 K시간 이하가 몇개 있는지 답을 구하면 됩니다. 다익스트라가 사용되며 도시의 개수는 N개 그리고 한 도시의 주변 개수는 road.length 이므로 각..

www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 최소신장트리 복습 겸 백준 분류별 풀기에서 기본 유형을 하나 풀어봤습니다. 이전에 많이 풀었던 유형이라 설명은 생략하도록 하겠습니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; class Main { private static int[] parent; ..

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 프로그래머스 LV3 그리디 유형의 선 연결하기 문제입니다. 섬이 여러개 있는데 최소 비용으로 모든 섬을 연결해야합니다. 전형적인 최소신장트리 문제로 크루스칼 알고리즘을 사용하게 됩니다. 오랜만에 푸는 유형이었습니다. youngest-programming.tistory.com/category/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/%EC%9C%A0%EB%8B%88%EC%98%A8%ED%8C%8C%EC%9D%B8%EB%93%9C%2C%20%EC%B5%..

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

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 백준 그래프 유형분류에서 푼 안전영역이라는 문제입니다. ㅎㅎ 지역마다 높이가 다른데 해당 높이보다 같거나 큰 비가 오면 지역이 물에 잠기게 됩니다. 모든 비오는 경우의 수에서 물에 안잠긴 지역들의 구역이 최대일때 몇 구역인지 구하는 기본적인 BFS 유형의 문제였습니다. 비에와서 잠긴 부분을 벽(isUnderWatered)라고 생각하고 풀면 됩니다. 풀이는 주석으로 충분하며 다음과 같습니다. [Java] import j..

programmers.co.kr/learn/courses/30/lessons/43238?language=java 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 프로그래머스 LV3 이분탐색 유형인 입국심사라는 문제를 풀어봤습니다. 각자 심사하는데 걸리는 시간이 다른 심사관들이 있는데 N명을 심사하는데 걸리는 최소시간을 구하는 문제입니다. 주석에 풀이를 자세히 적어놨고 간략히 설명하면 다음과 같습니다. 1. 걸리는 시간의 최소와 최대를 이분탐색의 left, right로 설정합니다. 2. 이분탐색 시간(mid)을 ..

www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 백준 분류별 풀기에서 이분탐색문제인 숫자 카드를 풀어봤습니다. 먼저 기본적인 이분탐색문제 중 하나였습니다. 경우의 수를 보면 알다시피 보통 시간초과를 일으키는 문제라는 경고의 수인 50만개까지 데이터가 있을 수 있습니다. 완전탐색으로 문제를 해결하면 당연히 시간초과가 나게됩니다. 그러므로 이분탐색을 사용하여 O(N)을 O(logN) 시간복잡도를 줄여주도록 합시다. 추가로 출력시 S..