본문 바로가기

개발일지/Problem Solving

백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS) * 문제 링크 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 문제 내용 요약 수열(크기 1 ≤ N ≤ 1000)이 주어졌을 때, "가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)"의 길이를 구해라 예) {1,2,1,3,2,5} 면 {1,2,3,5} 가 LIS 다. 접근법 (힌트에서부터 차근차근) 피보나치를 제외하면 가장 유명한 .. 더보기
백준 11376번 - 열혈강호 2 * 문제 링크 https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 문제 내용 요약 강호네 회사에서는 또 직원 N명과 할 일 M개가 있다. (1 ≤ N,M ≤ 1000) 직원 한 명은 2 개의 일만 가능하고, 한 일에는 한 명만 배정되어야 한다. 최대 몇 개의 일을 할 수 있을까? 접근법 11375번 열혈강호 문제를 먼저 풀어오기를 추천한다. https://syerco0.tistory.com/19 백준 11375번 - 열혈강호 * 문제 링.. 더보기
백준 11375번 - 열혈강호 * 문제 링크 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 문제 내용 요약 강호네 회사에서는 직원 N명과 할 일 M개가 있다. (1 ≤ N,M ≤ 1000) 직원 한 명은 한 개의 일만 가능하고, 한 일에는 한 명만 배정되어야 한다. 최대 몇 개의 일을 할 수 있을까? 접근법 하나의 직원에 하나의 일을 매칭하는, 즉 2개의 집합의 원소를 일대일로 매칭시키는 문제다. 가장 기본적인 "이분 매칭(Bipartite Matching)" 문제.. 더보기
백준 3878번 - 점 분리 * 문제 링크 https://www.acmicpc.net/problem/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 문제 내용 요약 2차원 좌표 1사분면에 검정 점과 흰 점이 많이 있는데 (1 ≤ N,M ≤ 100) 얘네들을 직선 하나로 색깔별로 분리하려고 한다. 직선은 어떤 점도 만나면 안된다. 분리가 되는지 안 되는지 판단하자 (그림은 문제 링크 참고) 필요 배경 지식 두 가지 배경 지식이 필요하다. 컨벡스 헐과 선분 교차 판정 두 가지다. 이에 대한 기본적인 내용은 아래의 두 글을 참고하길 바.. 더보기
백준 17387번 - 선분 교차 2 * 문제 링크 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 문제 내용 요약 두 선분의 각 끝 점들이 주어지면 (그래서 점 2개씩 2개, 총 4개) 그 선분들이 교차하면 1, 아니면 0 을 출력해라 접근법 선분 교차 판정 문제는 CCW를 이용해서 푼다. CCW에 대한 설명은 아래 글의 CCW 부분을 참고하길 바란다. https://syerco0.tistory.com/10 백준 1708번 - 볼록 껍질 * 문제 링크 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질.. 더보기
백준 3679번 - 단순 다각형 * 문제 링크 https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌 www.acmicpc.net 문제 내용 요약 주어진 점 N ( 3 ≤ N ≤ 2000 ) 개로 아무렇게나 다각형을 만들자 다각형의 선분은 무조건 점에서만 교차해야하고, 모든 점이 한 직선에 있는 경우는 없다. 접근법 계속해서 컨벡스 헐 문제를 풀어왔다면, 접근하기에 어렵지는 않을 것이다. 사실 컨벡스 헐까지 가지 않고, 각도에 따라 정렬할 줄만 알면 된다. 아래는 관련 배경 지식 링크.. 더보기
백준 7420번 - 맹독 방벽 * 문제 링크 https://www.acmicpc.net/problem/7420 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net 문제 내용 요약 화학 제국의 왕 성준이가 타국의 공격을 막으려고 건물들 ( 3 ≤ L ≤ 1000 ) 을 감싸는 맹독 방벽을 세우려 한다. 근데 만들기 힘들어서 최대한 적게, 그리고 자국민들 피해 안 가게 하려고 건물들에서 최소 L ( 1 ≤ L ≤ 1000 ) 만큼 떨어지게, 모든 건물을 한 번에 두르게 지으면 길이가 얼마나.. 더보기
백준 1708번 - 볼록 껍질 * 문제 링크 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 문제 내용 요약 다각형의 아무 두 점을 잡아 선분을 그었을 때, 항상 다각형 내부에 존재하면 그 다각형을 볼록 다각형이라 한다. 2차원 평면에 N ( 3 ≤ N ≤ 100,000 ) 개의 점 중에 선택해서 모든 점들이 내부에 있도록 볼록 다각형을 만들었을 때 (Convex Hull) 의 선택한 점의 개수를 구해라. CCW (Counter Clockwise) 세 점.. 더보기
728x90
반응형

티스토리툴바