문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 어떻게 풀 것인가? LIS와 LDS의 혼합 문제였다. 처음에 LIS를 시행이후에 LDS를 시행하면 문제가 원하는 최장 바이토닉 수열의 길이가 나온다. 간단했다. 아래는 LIS 와 LDS의 정리글이다. https://superohinsung.tistory.com/199 [Algorithm] LIS, LDS (최장 증가 부분 수열, 최장 감소 부분 수열) 최장 증가 부분 수열(LIS, Longest Increasi..
문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어떻게 풀 것인가? 문제의 제목부터가 "최소비용 구하기" 이다. 그래서 다익스트라 최단경로 구하는 알고리즘을 사용하였다. 사실 그래서 처음 접근 자체는 크게 어렵지 않았다. 어떠한 문제를 풀 때 문제의 알고리즘 유형 파악이 빠르다면 코드는 그다지 어렵지 않다. 풀면서 놓쳤던점 X 이 문제를 통해 얻어갈 것 다익스트라 알고리즘 내 코드 import java.i..
문제 https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 어떻게 풀 것인가? 모든 경우를 찾는 브루트포스 문제였다. 다만 조건을 걸지 않으면 O(N^3)이 발생해서, 시간초과가 발생한다. 그렇다면 어떠한 조건으로 거를 수 있을까? 첫번째, 심리적 거리가 최악인 경우는 0이다. 즉, 0이 발생하면 반복문을 중단하면된다. 두번째, 서로 다른 MBTI는 16명이다. 2명씩 총 32명 있을 경우 심리적 거리는 0이 될 수 있다. 33명부터 동일한 MBTI를 가진 인원이 3명이 되기 때문에 비로소 심리적 거리가 0임을 보장할 수 있다. 풀면서 놓쳤던점..
문제 https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 어떻게 풀 것인가? https://superohinsung.tistory.com/187 [BaekJoon] 1300번 k번째 수 (Java) 문제 풀이 [Gold 2] 문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열..
문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 어떻게 풀 것인가? 문제 처음에 주어지는 수를 보면 시간복잡도의 의해서 브루트포스 알고리즘으로는 접근이 불가하다. 즉 log(N)의 시간복잡도를 가진 이분탐색을 이용한 문제이다. 이차원 배열을 일차원 배열로의 변환과 큰 수 처리가 관건인 문제였다. 예를 들어 4 X 4 2차원 배열에서 1차원 배열로 바꾸게 된다면 B[11] = 8이 된다. 문제에서는 1차원 배열..
문제 https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 어떻게 풀 것인가? 문제의 접근은 DFS가 맞다. 다만, 특정위치가 주어지지 않고 주어진 행렬에서 DFS 검사를 모두 행해야하며, 그에 따라 visit 배열도 그 때마다 생성을 해준다. 문제의 예제를 통해서 살펴보자. ===> 첫 번째 길 찾기 E E W W E W 1 1 1 ===> 두 번째 길 찾기 E E W W E W 1 1 1 2 2번 길은 1번 길과 연결되어 결국 1번으..
문제 https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 어떻게 풀 것인가? 문제를 읽자마자, DFS를 떠올렸다. 다만 문제가 현재 밟고 있는 칸의 수만큼 이동이 가능하다는 점만 유의해서 푼다면 쉽게 풀리는 문제였다. 풀면서 놓쳤던점 없음. 이 문제를 통해 얻어갈 것 인접행렬의 DFS 활용문제 내 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStrea..
문제 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 어떻게 풀 것인가? 다소 깊게 생각하면 어렵지만, 수학적으로 접근하면 너무너무 쉬운 문제였다. 가장 적은 종류의 비행기를 타고 모든 국가들을 여행
