분류 전체보기

[백준 10090] Counting Inversion C++

10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 분할 정복 1. 문제해결 아이디어 임의의 수열에서 자신보다 뒤에 있는데 자신보다 작은 수의 개수의 총 합을 구하는 문제이다 N^2로 풀면 너무 쉽겠지만 N

[백준 1111] IQ Test C++

www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 처음에 x가 0이 되는 경우를 깜박해서 ZeroDivisionError 가 발생했었다 같은 수가 연속으로 나올경우 x값이 0이 된다! 모든 점이 한 직선위에 있음을 알아차리고, 직선의 기울기와 y절편을 구한다 구한 기울기와 y절편이 모든 좌표 쌍에 적용된다면 a, b는 구해진 것임 그리고 N==1, N==2일때의 기저조건 예외처리를 해주고 마무리를 했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

[백준 14501] 퇴사 C++

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp와 브루트포스 방식을 모두 적용할 수 있는 좋은 문제이다! solve1은 브루트 포스와 dp를 적용해서 O(n^2)에 풀 수 있는 방법이다 solve2는 solve1과 논리는 같지만 top-down방식으로 재귀함수를 이용한 방법이다 solve3는 동적계획법을 최대한 활용해서 Pi, Ti를 뒤에서부터 탐색하는 방법을 사용해 O(N)만에 해결하는 방법이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5..

[백준 2798] 블랙잭 C++

N이 최대 100 이므로 3장을 뽑는 모든 경우의 수를 탐색하는 O(N^3) 알고리즘을 수행할 수 있다 for 문을 돌면서 sum에 현재 선택한 카드 3장의 합을 저장하고, sum이 M을 넘지않지만 현재 결과보다 크다면 현재 결과를 갱신한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std; int main(){ int N, M, num[101], sum = 0, result = 0; cin >> N >> M; for(int i = 0; i > num[i]; } for(int i = 0; i

[백준 1074] Z C++

분할정복은 어려워! 코드만 보면 되게 간단해 보이는데 간단하게 만들기 위해 머리를 짜내는게 힘들다.. 내 머리는 재귀적인 생각을 잘 못하는듯 하다 처음에 입력받은 N값을 2로 나눈 값을 solve()로 넘겨준다 -> 이 때 n == 2라고 가정하자(N == 3인 경우) (r, c)가 몇 사분면에 있는지 4개의 if문을 통해서 판별한다 판별기준 : row + n 과 col + n row+n을 기준으로 r이 이 값보다 작으면 1, 2 사분면 중 하나, 같거나 크면 3, 4 사분면 중 하나이다. col+n을 기준으로는 c가 이 값보다 작으면 1, 3 사분면 중 하나, 같거나 크면 2, 4 사분면 중 하나이다. 총 4가지 기준으로 분할 정복을 실행하고 r, c의 위치를 찾으면 (n == 0) 리턴하여 지금까지 ..

[백준 10830] 행렬 제곱 C++

분할 정복은 어렵다! 거듭제곱에 대해서는 위와 같이 분할이 일어난다. -> m이 짝수일 때, 홀수일 때 분할이 달라지는건 코드에 표현되어있다. 개인적으로 class를 만들어서 객체간의 연산을 해주는 방식으로 만들어서 마음에 든다! #include #include using namespace std; int N; long long B; // 정방 행렬을 저장하는 class class Matrix{ public: int Map[6][6]; Matrix(){} Matrix(int n){ int in; for(int i = 0; i > in; Map[i][j] = in % 1000; } } } // 연산자 오버로딩을 통해서 행렬의 곱..

[백준14500] 테트로미노 C++

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나..

[백준 9252] LCS2 C++

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의..

[백준 1535] 안녕 C++

세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다. 세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다. 세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N(> N; for(int i = 1; ..

[백준 12865] 평범한 배낭 C++

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군..