전체 글 (54) 썸네일형 리스트형 [BOJ 3392] 화성 지도 백준 3392번 화성 지도 https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net 문제 변이 각각 x축, y축으로 평행한 직사각형이 N개가 주어짐 (N 냅색 (Knapsack) 안녕하세요. 오늘은 냅색 (knapsack) 에 대해 알아보겠습니다. 개념 냅색은 일명 배낭 채우기 문제라고도 불립니다. N개의 물건은 각각 무게 w와 가치 v를 가짐 배낭이 버틸 수 있는 최대 무게는 weight_limit weight+limit를 넘지 않도록 배낭에 물건을 넣어서 가치가 최대가 되게 하는 문제 Brute Force 모든 경우의 수를 찾는 브루트 포스 알고리즘을 생각해봅시다. 해당 물건을 가방에 넣을지 말지 2가지 경우의 수가 있습니다. 물건이 N개가 있으니 최종 시간 복잡도는 O(2 ^ N) 입니다. N이 30만 되어도 10억을 넘는 숫자가 되니 더 빠른 알고리즘을 생각할 필요가 있습니다. Dynamic Programming 동적 계획법으로 문제를 풀려면, 최적의 원리를 만족해야 합니.. [BOJ 13711] LCS 4 백준 13711번 LCS 4 https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net 문제 수열의 크기 N 1; if (lis[m] > key) r = m - 1; else l = m + 1; } return r + 1; } int solve(int N) { for (register int i = 0; i < N; ++i) { int t = lower(arr[i]); lis.pu.. LIS (Longest Increasing Sequence) 안녕하세요. LIS (Longest Increasing Sequence)에 대해 알아보겠습니다. 개념 LIS는 최장 증가 부분 수열이라고 합니다. 수열에서 가장 긴 증가하는 부분 수열입니다. arr에서 가장 긴 부분 수열은 {2, 4, 8, 9} 입니다. 이를 LIS라고 말하고 LIS의 길이는 4 입니다. (부분 수열은 연속하지 않아도 됨) 풀이 LIS를 구하는 여러 방법 중에서 아래 2가지 방법을 알아보겠습니다. DP 사용 이분 탐색 사용 DP 사용 과정 dp[i]를 arr[i]를 마지막 원소로 갖는 LIS의 길이 라고 둔다면, 0 [BOJ 20942] 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회 백준 20942번 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회 https://www.acmicpc.net/problem/20942 20942번: 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회 첫 번째 자리에는 $15$세의 참가자가 이미 배치되어 있다. 두 번째, 세 번째, 네 번째 자리에 각각 $17$세, $12$세, $19$세의 참가자를 배치하면, $15 \operatorname{\&} 17 = 1$, $15 \operatorname{\&} 12 = 12$, $12 www.acmicpc.net 문제 N개의 자리가 있다. 각각의 자리에는 8세 ~ 19세의 참가자를 배치해야 한다. M개의 연산에 대해, 두 자리에 대한 비트 연산(bitwise and, bitwise or)을 해서 특정 .. [BOJ 3648] 아이돌 백준 3648번 아이돌 https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 문제 한 심사위원이 두 표를 행사합니다. 행사한 두 표 중에 적어도 하나는 결과가 만족해야합니다. 추가로 상근이는 반드시 합격 목록에 들어가 있어야 합니다. 풀이 4 3 1 2 -2 -3 2 4 예제 입력이 위와 같이 주어집니다. 총 3명의 심사위원이 두명한테 투표를 행사했습니다. 양수는 해당 number가 합격해야 한다는 의미이고, 음수는 해당 number가 불합격해야 한다는 의미입니다. 1) 1 2 1번이 불합격하면.. 2-SAT 안녕하세요. 오늘은 2-Satisfiability 에 대해 알아보겠습니다. 개념 전체 식이 True가 되도록 변수에 True 또는 False 값을 배정하는 문제입니다. True 또는 False 2지 선다이기 때문에 2-SAT 이라 불립니다. X, Y, Z 변수에 True 또는 False 값을 할당해 전체 라인이 True가 되도록 만들어봅시다. Line 1 X : True, Y : False, Z : False 가능 Line 2 X에 True 또는 False 를 넣어도 만족하지 않음 불가능 풀이 그래프 모델링을 통해 2-SAT을 풀 수 있습니다. (X or Y) X 또는 Y가 true가 되어야 합니다. 만약 X가 false 라면, Y는 반드시 true가 되어야 합니다. (not X -> Y) 만약 Y가 f.. [BOJ 4305] 성격 진단 테스트 백준 4305번 성격 진단 테스트 https://www.acmicpc.net/problem/4305 4305번: 성격 진단 테스트 각 테스트 케이스마다 정답을 출력한다. 한 줄에 하나의 그룹(partition)을 알파벳순으로 출력하며, 각 그룹의 알파벳순으로 가장 앞에 오는 원소 기준으로 그룹들도 알파벳순으로 출력되어야 한 www.acmicpc.net 문제 5지 선다 중에 1개를 선택하는 성격 진단 테스트 입니다. A B C D E 중에 A를 선택하면, A가 B, C, D, E 보다 더 선호하는 보기라는 것입니다. 이렇게 여러 문항을 테스트 하다가 모순이 생길 수 있습니다. 모순이 있는 집단을 찾는 문제입니다. 풀이 모순이 생긴다는 의미는 A 보다 B를 선호한다고 골랐는데, 다른 문항에서 B 보다 A를 .. 이전 1 ··· 3 4 5 6 7 다음
