Patrick's Devlog

Item 13 : 자원 관리에는 객체가 그만 투자를 모델링하는 클래스 라이브러리를 가지고 어떤 작업을 한다고 가정하자. 이 라이브러리는 Investment라는 최상위 클래스가 있으며, 이를 기본으로 해 구체적인 형태의 투자 클래스가 파생되어 있다. 또 여기서 이 라이브러리는 Invetment에서 파생된 클래스의 객체를 사용자가 얻어내는 용도로 팩토리 함수만을 쓰도록 만들어져 있음을 가정한다. class Investment { .. } // 여러 형태 투자를 모델링한 최상위 클래스 Investment * createinvestment(); // Investment 클래스 계통에 속한 클래스의 객체 동적할당 및 포인터 반환 // 이 객체 해제는 호출자 쪽에서 직접 해야함 (매개변수 생략) creativeIn..

1. Greedy Algorithm(탐욕 알고리즘) 탐욕 알고리즘은 탐욕적인 방법으로 문제를 풀 수 있으나, 그 문제가 정말 맞는 방법인지 알기 어렵다. 만약 탐욕 알고리즘을 통해 최적의 알고리즘을 찾았지만, local minimum일 수 있으므로 global minimum만 존재하는 알고리즘인지 아는 것이 중요하다. example> 동전 바꾸기 문제 1. [10, 100, 500] 동전들이 존재할 때 최소한의 동전으로 710원을 만들어라. solution 1 > 가장 큰 동전으로 먼저 이용하고 이용한 동전을 빼주며 맞춰가면 된다. 500 x 1, 100 x 2, 10 x 1 2. [10, 30, 40, 50] 동전들이 존재할 때 최소한의 동전으로 70원을 만들어라. 여기서는 위의 방법으로 풀어버리면 풀..

1. 개요 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 1-1. 설명 국가는 정해진 예산 내에 최대한의 예산을 지방에 배정해주려고 한다. 각 조건에 맞게 지방에 돈을 분배했을때, 배정된 예산중 최댓값 정수를 출력하는 프로그램을 작성한다. 자세한 조건들과 설명은 위의 링크를 참조한다. 1-2. 제한 사항 - 첫 줄에는 지방 수를 의미하는 N이 주어지며, N은 3 이상 10,000 이하 - 다음 줄에는 각 지방의 예산 요청을 표현하는 N개..

1. DP vs Backtracking DP는 problem과 sub-problem을 나누어 진행하고, 이 sub-problem은 더 작은 sub-problem으로 나누어 질 수 있다. 겹치는 sub-problem은 memorization을 통해 저장하면서 중복된 계산을 줄여갔다. 그러나, Backtracking은 우리가 가져갈 수 있는 모든 경우의 수를 하나씩 살펴보고, Decision space를 만들어 나간다. 여기서 어떠한 경우의 수가 의미가 없게되면 가지치기를 하게 되고 backtracking을 하면 된다. 2. Backtracking ex> Phone keypad 문제(leetcode 17) 우리가 아는 휴대폰의 키패드는 아래의 사진과 같다. "25"가 입력이 되었을 때, AJ / AK / A..

1. 개요 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1-1. 설명 오늘은 스사트링크에 다니는 사람들이 모여 축구를 한다. 축구를 위해 모인사람은 N명이며, 이는 짝수이다. 이제 N/2명으로 이루어진 스타트팀과 링크팀으로 사람을 나눠야한다. 우리는 능력치를 조사하여 각 팀에 더해지는 능력치가 최소일때를 찾는 프로그램을 구현한다. 문제의 자세한 설명은 위의 링크를 참고한다. 1-2. 제한 사항 - 첫 줄에 N이 주어지며, N은 4 이상 20 이하 짝수 - 둘째 ..

1. 개요 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 1-1. 설명 가로수가 임의의 간격으로 심어져 있다. 우리는 가로수들이 모든 간격이 동일하게 되도록 가로수를 추가로 심게끔 추진한다. 최대한 적은 가로수의 수로 같은 간격이 되도록 할때, 심어야 할 최소의 가로수 수를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에는 이미 심어져있는 가로수의 수를 나타내는 정수 N이며, 3이상 100,000 이하 정수 - 둘째 줄부터..

1. 개요 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1-1. 설명 N-Queen 문제는 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을때 퀸을 놓는 방법의 수를 구하는 프로그램을 구현한다. 1-2. 제한 사항 - 첫줄에 N이 주어지며, N은 1 이상 15미만 2. 구현 2-1. 풀이 백트래킹 방법으로 구현해본다. 백트래킹은 간단하게 설명하자면 DFS로 탐색하는 중, 방문 중인 노드가 유망한지 체크한다. 체크..

1. 개요 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1-1. 설명 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇개의 수를 선택해 구할 수 있는 합 중 가장 큰 합을 구하려 한다. 단, 수는 한 개이상 선택해야 한다. 1-2. 제한 사항 - 첫 줄에 정수 n이 주어지며, n은 1 이상 100,000 이하 - 둘째 줄에는 n개의 정수로 이루어진 수열이 주어지며, 수는 -1,000 이상 1,000 이하 2. 구현 2-1. 풀이..