PS하는 깃털

문제 링크 : https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 문제 풀이 이 문제는 원 위에 정D1각형부터 정D2각형까지 그릴 때 중심에서 다른 점들에 의해 '가려지지 않는' 점들의 개수를 묻는 문제이다. 제한시간이 1초이고 D2가 2000이하이므로 넉넉하게 O(n^2)으로 해도 별 문제가 없을 것 같아보인다. 반지름이 D1인 원에서 부터 반지름이 D2인 원까지 각각의 원에 대해서 각각의 좌석들에 대해 모두 탐색을 해보자. 각 원에서 좌석들에 ..

문제 링크 : https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제 풀이 이 문제는 초기 위치에서 시작해, 이전 변위와 현재 변위의 차가 1 이하가 되도록 이동하여, 마지막 위치까지 이동했을 때 이동 횟수의 최솟값을 묻는 문제이다. i번째 이동에서의 이동거리를 D(i)로 정의해보자. 이제 각각의 이동에 대해 D(i)를 최대로 할 수 있게 Greedy방법을 써보자. 현재 위치 current에 대해 D(..

백준 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net  오늘은 DP를 이용해 최장 증가 부분 수열의 길이를 구하는 코드를 구현해볼 것이다.최장 증가 부분 수열 : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.ex)  A = ..

PS를 좋아하는 사람이라면 한 번쯤은 Knapsack Problem에 대해 들어본 적이 있을 것이다. DP를 활용하는 대표적인 문제이기도 하고, 알고리즘을 공부하기에도 좋은 문제이다. Knapsack Problem : 주어진 물건들에 대해 그 가치와 무게가 주어져있을 때, 무게의 합이 담을 수 있는 최대 무게를 넘기지 않고 가치의 합이 최대가 되도록 배낭에 담기 위해서는 어떤 물건을 담아야하는가? 자세한 설명 : https://en.wikipedia.org/wiki/Knapsack_problem Knapsack problem - Wikipedia From Wikipedia, the free encyclopedia Problem in combinatorial optimization Example of a ..

문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 이 문제는 이분 탐색을 사용하는 전형적인 문제이다. 랜선의 길이를 이용해서 이분 탐색을 하면 된다. 먼저, 왼쪽 포인터를 L, 오른쪽 포인터를 R라고 했을 때, 초기 값은 L=1, R은 랜선의 길이 중 최대 길이로 지정한다. 이제 이 둘의 평균인 M을 보면 두 가지 경우가 있다. 1. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N미만..

배열을 다루다보면 일정한 기준으로 그 배열을 정렬해야하는 상황이 생긴다. 이럴 때 C++ STL 에서 제공하는 sort()를 이용하면 편하다. sort()는 기본적으로 헤더파일에 속해있다. 그래서 이 함수를 쓰기 전에 먼저 헤더파일을 가져와야한다. #include 1) 배열(array) 배열을 정렬할 때는 sort()를 아래와 같이 사용한다. sort(시작주소, 끝주소 + 1) 시작주소는 (배열의 이름) + (번지수) 로 표기한다. 예를 들어 arr라는 배열의 1번지부터 시작하고 싶으면 arr+1로 나타낸다. 끝주소는 (배열의 이름) + (번지수)+1 로 표기하고, 예를 들어 n-1번지는 arr+n으로 표현한다. 2) 벡터(vector) 벡터를 정렬할 때에도 배열과 비슷한 방식을 사용한다. sort(v...

문제 링크 : https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 문제 풀이 이 문제에서는 사진틀의 개수와 추천횟수를 주고, 어떤 학생들을 추천했을 때 사진틀에 있는 사진들이 바뀌어 최종적으로 어떻게 되는지 묻고 있다. 나는 이 문제를 풀 때 여러 함수를 정의해서 풀었다. 먼저 사진틀에 사진들이 다 차있는지를 알아보는 full()과, 삭제할 학생을 찾는 remove(), 매 추천마다 사진틀의 시간을 더해주는 addTime()함수를 정의하였..

문제 링크 : https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 문제 풀이 이 문제는 모눈종이의 가로, 세로의 길이와 모눈종이 상의 자르는 선을 주어줬을 때, 나눠진 부분 중 가장 넓이가 큰 부분을 구하는 문제이다. 최대 넓이를 구하려면 단순하게 가장 긴 가로 변과 가장 긴 세로 변의 길이를 구하면 된다. 구하는 방법은 먼저 column, row배열에 자르는 선인지에 대한 정보를 담고 각각의 배열에서 반복문을 1번씩만 돌아 최소길이를 구할 수 있다. ..

문제 링크 : https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제 풀이 이 문제에서는 좌석들의 정보(VIP여부)가 주어졌을 때 가능한 모든 좌석 배치의 경우의 수를 묻는 문제이다. 당연히 VIP 좌석 때문에 나눠진 좌석들끼리는 서로 영향을 주지 못하기 때문에 각각의 경우의 수를 구하고 곱해야겠다는 생각을 했다. 또 이 가능한 경우의 수는 DP를 이용하면 쉽게 구할 수 있었다. n명의 사람이 있고, VIP가 없을 때 가능한 좌석 배치를 D[n]이라고 하면,..

문제 링크 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 문제 풀이 문제에서는 볼들의 배열이 주어졌을 때 같은 색깔의 볼들을 한 쪽으로 모으는 최소 이동 횟수를 요구하고 있다. 처음 봤을 땐 왼쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우, 오른쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우 모두 나눠서 반복문을 4번 돌아 구한 다음, 최소를 출력하려고 했다. 근데 더 생각해보니 왼쪽이랑..