PS
BOJ 10775 - 공항
www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 처음 이문제를 봤을때, 해시테이블을 써야되나 라고 생각했다. 그래서 c++ 의 unordered_map 을 사용해서 입력을 받을때마다 해당 인덱스를 value값으로 입력으로 주어지는 gi 값을 key 값으로 하는 그런 해시테이블을 만들어서 처리하는 문제인줄 알았다. 그러나 통과하지 못했고, 배열로 작성해서 이중포문 돌리는 것 역시 최댓값이 10^5 이므로 O(N^2) 이 되면,..
BOJ 6236 - 용돈 관리
www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 처음 문제를 읽었을때, 지문 내용이 잘 이해가 안됬는데, i번째 날에 사용할 금액과 K원 둘의 명확한 차이점과 사용방식이 헷갈렸다. 문제에서 배열로 주어지는 값들(N개의 수, arr[i])은 i번째 날에 쓸 돈이고, K원은 통장에서 인출한 돈이다. 그리고 K원을 인출할 수 있는 횟수는 M번으로 제한되어 있다. if (arr[i] k) 이면, i번째 날이 k원만 가지고는 생활이 안되므로, 인출을 해야된다. 즉 인출을 ..
BOJ 1761 - 정점들의 거리
www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 이 문제를 풀기 위해서는 먼저 LCA (Lowest Common Ancestor) Algorithm 에 대해 알고 있어야 한다. 그리고 LCA 를 알기 위해선, 희소 테이블(Sparse Table) 에 대한 사전지식이 있어야한다. 참고 - 희소 테이블 : blog.naver.com/kks227/220793361738 희소 테이블(Sparse Table) (수정: 2019-11-16) 안녕하세요. 이번 ..
BOJ 2170 - 선긋기
www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 입력으로 들어온 시작점, 끝점을 전부 하나의 자료형에 담아둔 뒤, 시작점 기준으로 오름차순 정렬한다. 그 후 정렬된 배열에서 첫번째 원소는 가장 앞에 있는 시작점 이므로, 이 좌표를 기준으로 삼고 다음 좌표와 비교할때, 이전 좌표의 시작점 끝점 사이에 존재하는 선인가? (겹치는 선인가) 판별한다 그리고 겹치는 선이면서 동시에 다음 좌표의 끝점이 더 긴 경우 끝점을 그 값으로 갱신한다..
BOJ 11053 - 가장 긴 증가하는 부분 수열
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net BOJ 11722 - 가장 긴 감소하는 부분 수열 (sdy-study.tistory.com/160) 과 똑같은 문제다 감소하는것 대신 증가하는것 찾으면 되니 부등호만 바꾸면 된다. - c++ #include #define MAX 1001 using namespace std; int N, answer; int arr[MAX], dp[M..
BOJ 11722 - 가장 긴 감소하는 부분 수열
www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net DP 로 풀어야하는 문제이다. int arr[MAX] 는 입력 받은 값 int dp[MAX] 는 dp[a] = b; a 번째 index 까지의 최대길이가 b 이다. 를 의미한다. dp 배열을 채워넣기 위해서 아래의 두가지 사항을 고려한다 첫번째, 현재 인덱스(i) 보다 작은 인덱스(j) 가 가르키는 값(arr[j]) 가 현재 인덱스가 가..
BOJ 17144 - 미세먼지 안녕
www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 두가지를 구현해야한다. 1. 미세먼지를 퍼트리는 함수 2. 공기청정기를 가동하는 함수 미세먼지를 퍼트리는 함수는 공기청정기가 있는지역 또는 2차원배열 범위를 벗어나는 지역을 제외하고 전부 퍼질수 있다. 주의할점은 이미 미세먼지가 존재하는 지역에 미세먼지가 퍼질때이다. 위 그림에서 왼쪽이 미세먼지가 퍼지기 전이고 오른쪽이 퍼진 이후다. 먼저 (0, 1) 부분 (값 30) 이 퍼질때는 30 / 5 = 6 이 퍼져..
BOJ 16235 - 나무 재테크
www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 이 문제에서 가장 주의해야할 점은 1 * 1 한 칸에 여러개의 나무가 들어갈 수 있다는 것이다. 그래서 나무의 나이를 나타내는 배열을 단순히 int tree[11][11] 이런식으로 선언하면 문제의 조건에 부합하게 풀 수 없게 된다. 여러개가 들어가야 하고, 크기가 고정된 배열 보다는 동적 배열인 벡터를 이용해서 선언하면된다. vector tree[11][11] 이런식으로.. 이 부분만 주의하면..