https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. Logic - 먼저 시간 복잡도를 계산해봤을때 넉넉잡아 계산해도 50 * 50 * 13 * 13을 해도 42만정도가 나오기 때문에 충분히 돌 수 있다. 그러므로 완전탐색 문제인 것을 알 수 있다. 폐업시키지 않을 치킨집의 최대 갯수를 준다고 했는데 치킨집은 많으면 많을 수록 좋기 때문에 다 골라준다고 생각하면 된다. 여기서 폐업시킨다는 뜻은 고르지 않는다로 생각하고 치킨..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. Logic - 첫번째 문자부터 확인하면서 각 문자열의 끝까지 확인하고 만약 각 인덱스의 서로의 문자가 같으면 값 +1 Topdown형식으로 풀었다. 2. Code #include using namespace std; int dp[1001][1001]; string str1, str2; int solve(int s1Idx, int s2Idx) { /..
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. Logic - 집중국의 수신 가능 영역을 최소화 시키기 위해서는 집중국을 세울수 있는 갯수로 지어진 k만큼 다 세워 줘야 한다. 센서를 세우는데 가장 적합한 위치는 오름차순 정렬을 했을 때 인접한 두 센서의 가운데에 세워야 한다. 케이스에서 나온 1 6 9 3 6 7 > 오름차순 정렬 1 3 6 6 7 9 > 인접한 두 노드의 거리를 빼주기 dist : 2 3 0 1..
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 처음 이 문제를 봤을 때는 작은 숫자 순서대로 다 빼주면 되는 줄 알았다. Case 3을 보면 작은 수 부터 다 빼주면 477584이기 때문에 정답이 아니다. 결국 이 문제를 일반화 시켜보게 되면 알고리즘은 "현재 보고 있는 수보다 작은 수가 앞에 있으면 앞에 있는 수를 지워야 한다." 이다. 문제에 나온 TestCase 3을 예시로 들어 설명하자면 10 4 4177252841 지울 수를 걸러내는 로직은 스택에 값이 있고(비어있지 않고) 숫자를 지울 수 있으..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 1. Logic multiset 해설 1. 우선순위큐에 보석의 가치와 무게 순으로 넣는다. 2. 가방의 무게를 입력받아 multiset으로 넣는다. 3. multiset은 오름차순으로 정리되기 때문에 lower bound(O(logN))을 활용하여 보석의 무게와 같거나 더 큰 가방을 찾는다 vector 해설 1. 보석과 가방을 벡터에 입..
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 1. Logic 처음 생각은 긴 문자열부터 첫번째 짜리부터 순서대로 9, 8, 7 이렇게 큰 숫자부터 넣어주면 된다고 생각했지만 문자가 중복되게 나오는 경우의 수도 있기 때문에 고려를 해주어야 한다. 예를 들어 ABC BCA 같은 경우가 대표적인데, 이때는 A와 B중 어느 알파벳에 9를 할당해 줄 지 구해야 한다. 각 자릿수에 가능한 숫자를 구해보면 A=100 B=10 C=1 > 100A 1..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. Logic 항상 작은 값 2개를 선택해서 정렬해야 최소한으로 비교할 수 있게 된다. 우선순위 큐는 우선순위가 높은 값을 기준으로 즉 값이 큰 거부터 내림차순으로 정렬해 주는 자료구조이다. 우선순위 큐를 선언과 동시에 greater인자를 붙혀주게 되면 오름차순으로 정렬되기 때문에 문제를 풀기 적절한 자료구조이다. 2. Code #include using namespace std;..
https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 1. Logic - 처음 시작 1은 무조건 양수로 시작한다고 이해하고 풀었다. 왜냐면 -1 -2 +3도 있지만 테케에 포함되지 않기 때문에 n = 9일 때를 생각해 보면 처음에 12가 들어오는 경우도 생기기 때문에 1을 먼저 박고 시작하지 않고 0일때를 분할하여 계산해주었다. 부분 문제 1. cnt == 0일때(처음 시작일 때) - 1을 더할지 - 12를 더할지 2. cnt == 0이 아닐때(처음 시작이 아닐때) - 한자리만 더할지 - 한자리만 뺄지..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. Logic - 문자 하나를 지날 때 마다 체크를 해서 다음 경로에서 이전에 어떤 문자를 지나왔는지를 확인해야하기 때문에 처음에는 자료구조 중 map을 사용해서 체크했다. 경로를 체크한 후 방문 처리한 계속 남아있게 되면 다른 경로를 진입할 때 continue 처리가 되기 때문에 DFS를 빠져나오면서 map에서 키값을 false로 돌려놔준다. 방문처리 하는 법 1. 자료구조 Map을 활..
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. Logic 해당 문제는 메모리 제한이 4MB로 굉장히 작으므로 배열의 수를 최대한 줄이는 데 초점을 두고 풀이해야한다. 간단한 설명은 입력받은 수를 변수에 저장한 후 입력받은 수를 기준으로 위의 수를 서로 비교하여 크고 작은 수를 가져와서 현재의 배열에 저장하는 식으로 풀이한다. 코드를 보면 더 잘 이해가 갈 것이다. 2. Code #include using namespace std; int n; int ..
