허비의 기술블로그

문제 설명 N개의 도시가 일직선으로 연결돼있고, 각 도시에는 주유소가 있다. 연결된 도시의 거리 배열, 각 도시의 기름값 정보 배열이 들어올 때 최소의 비용으로 첫 번째 도시에서 마지막 도시까지 가는 비용을 구하는 문제다. (단, 기름을 실을 수 있는 양은 무한대이며, 기름값과 거리는 10억 이하의 자연수이다. 또한 도시의 개수는 최대 10만 개다.) 시간 복잡도 : O(N) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 방법 도시를 차례로 지나가며 소모한 기름 값을 계산할 때, 각각 현재..

N개의 회의 사용시간(시작시간, 끝나는 시간)이 들어올 때 회의를 할 수 있는 가장 많은 경우의 수를 찾아서 그 값을 반환하는 문제다. N은 최대 10만이며, (시작시간, 끝나는 시간)은 INT최댓값으로 들어온다. 이때 시작시간, 끝나는 시간이 같을 수 있으며, 회의가 끝나는 시간에 다른 회의가 시작될 수 있다. (일반적 논리와는 맞지 않음에 주의한다.) 시간복잡도: O(NlogN) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 방법 가능한 많은 회의를 만들어야 하므로, 우선 입력값을 차례대로 비교해보기 위해 들어온 (회의 시작시간, 회의 끝나는 시간)을 오름차순으로 정렬한 배열을 생성한다. 이렇게 하면 시작시간이 빠..

N * N 크기의 체스판이 있을 때, N개의 퀸을 놓을 수 있는 경우의 수를 구하는 문제다. N개의 퀸은 서로 공격할 수 없어야 한다. 시간 복잡도: O(N!) (??) (각 행마다 1개의 Queen을 놓을 수 있으며 첫 행에 놓을 수 있는 자리는 N개이고 행이 커질수록 위의 행에서 1~3개만큼 가능한 자리가 줄어든다. 이를 수식으로 어떻게 나타내야 할지 모르겠어서 최소 1개는 줄어들기 때문에 N!이라고 썼다.) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이과정 체스판에서 Queen은 위, 아래, 대각선 이동이 가능하..

강이 위에서 아래로 흐르고 서쪽, 동쪽 땅으로 구분돼있다. 서쪽과 동쪽에는 각각 다리를 놓을 수 있는 포인트들이 N, M개 있다. (M >= N) 이때 서쪽에서 동쪽으로 다리를 놓으려고 할 때 다리를 놓을 수 있는 최대 경우의 수를 찾는 문제다. 시간 복잡도: O(MN) 풀이과정 강의 서쪽 땅 N개의 포인트에서 동쪽 땅 M개의 포인트를 연결하고자 하며, N은 M보다 작거나 같다. 이때 강의 동쪽에 연결할 M개의 포인트 중에 N개를 선택하면 서쪽에서 이어질 다리가 교차하면 안 되므로 다리를 짓는 경우가 1개 나온다. 즉 M개의 포인트에서 N개를 선택하는 경우의 수가 이 문제의 정답이다. 주의할점 조합은 수가 커질수록 결괏값이 커지므로 수의 범위를 조심해야 한다. 문제에서는 M, N의 최댓값이 30이기 때문..

두 터렛의 좌표와 목표물과 각 터렛 사이의 거리가 주어질 때, 존재 가능한 목표물의 위치 개수를 반환하는 문제이다. 즉 두 원 사이의 교차점을 의미하므로 나올 수 있는 값은 0, 1, 2, 무한대이다. 시간 복잡도: O(1) 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 풀이과정 두 원 중심 사이의 거리와, 두 원의 크기(반지름)를 비교하며 경우를 나눈다. distance => 두 중심 사이의 거리 r1 => 한 원의 크기 r2 => 다른 원의 크기 1. 두 원이 같은 경우 존재 가능한 목표물의 개수가 무한대이다. 2. 두 원이 외접하는 경우 교점이 1개이다...

포켓몬의 수와 위치를 찾을 개수가 입력으로 들어온다. 이후 포켓몬 이름을 차례대로 입력받은 뒤에, 위치를 찾을 포켓몬 이름 혹은 이름을 찾을 위치(숫자)를 입력받는다.. 포켓몬 이름은 알파벳으로 구성돼있다. 출력할 포켓몬 이름이 들어올 때 숫자가 입력된다면, 해당 숫자 번째로 들어온 포켓몬의 이름을 출력해야 한다. 이름이 입력으로 주어지면 해당 포켓몬의 위치를 출력한다. 시간 복잡도 : O(1) 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이과정 자료 갯수가 최대 10만 개이..

(x, y) 좌표의 1차원 배열이 입력으로 들어오면, 이를 오름차순으로 정렬해 출력하는 문제다. 두 좌표의 x값을 비교해 더 작은 좌표가 앞에 오고, 두 좌표의 x값이 같다면 y값을 비교해서 작은 좌표가 앞에 오게 된다. 시간 복잡도: O(NlogN) (정렬은 O(N^2)으로 할 수 있지만 N의 최댓값이 100,000이므로 해당 정렬(ex. 버블 / 삽입 / 선택 정렬)을 사용하면 시간 초과가 나게 된다.) 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀..

상자가 쌓인 층들이 나열된 1차원 배열과 상자를 옮길 수 있는 횟수를 입력받아, 평탄화를 진행했을 때 최고 높이와 최저 높이의 차이를 반환하는 문제이다. 시간복잡도: O(상자 배열 길이 * 상자 옮기는 횟수) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이과정 매번 상자를 옮기는 과정에 있어서, 가장 높이 쌓여있는 값과 가장 낮게 쌓여있는 값을 찾은 다음에 최댓값에서 1을 빼고 최솟값에 1을 더해서 평탄화를 진행한다. 최댓값, 최솟값을 가진 위치를 찾는 과정에서 값을 변경함에 따라 최소, 최댓값이 바뀔 수 있으므로, index를 먼저 구해놓는다. 주어진 변경 가능 횟수 내에 작업이 종료될 수 있지만, 끝까..

일렬로 나열된 빌딩들의 층 수가 주어지면 모든 빌딩의 각 층에서, 좌우 각각 2개의 빌딩에 대해 조망이 확보되는 층의 개수를 구하는 문제이다. 시간복잡도: O(N) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방법 빌딩 배열에서 좌, 우 끝의 2개 빌딩은 높이가 0이라고 주어졌으므로, 3~M-2번째 빌딩의 층들만 조망 가능 여부를 검사하면 된다.(M:빌딩의 개수) 검사 방법은 우선 좌, 우 각각 2개의 빌딩에서 가장 높은 빌딩의 층 수를 구한 다음, 현재 빌딩의 층수와 비교한다. 현재 빌딩의 층 수가 더 높다면, 현재 빌딩에서 조망 가능한 층은 없으며, 현재 빌딩이 더 높다면, 높은 층들은 조망이 가능..

스도쿠의 좌표(9*9 2차원 배열)가 주어지면, 스도쿠가 유효한지(1~9까지의 숫자가 유일하게 등장하는지) 검사하는 문제다. 시간복잡도: O(N) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방법 스도쿠의 9 * 9 좌표에서 세로줄, 가로줄, 3 * 3 사각형에 대해서 숫자를 검사해야 한다. 이를 위해 우선 2차원 배열을 입력받은 다음에 세로줄, 가로줄, 3 * 3 사각형을 각각 차례로 담은 2차원 배열 3개를 만든다. ex) 입력: 7 3 6 4 2 9 5 8 1 5 8 9 1 6 7 3 2 4 2 1 4 5 8 3 6 9 7 8 4 7 9 3 6 1 5 2 1 5 3 8 4 2 9 7 6 9 6 2..