정리와기록 블로그

문제: www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 접근: 회의실을 끝나는 순서대로 정렬합니다. (이때 같은 시간에 끝난다면 시작 시간이 빠른 순서대로 정렬합니다) 정렬한 배열을 순회하면서 '이전 회의 시간이 끝나는 시간' > N; for (int i = 0; i > temp.first >> temp.second; rooms.push_back(temp); } sort(rooms.begin(), rooms.end(), comp); int cnt = 0; long last = -1; for (int i = 0; i < N; i..

문제: www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 접근: DP의 접근법은 1) 완전 탐색으로 풀 수 있을지 본다. 2) 중복되는 부분을 cache로 메모이제이션을 해준다. 입니다. 해당 논리로 접근했습니다. 1) 완전 탐색은 물건을 빼거나 / 넣거나 하면 2^100 만큼의 경우를 만들어낼 수 있고, 이 때 겹치는 부분에 대해서만 cache 처리해주면 된다고 생각했습니다. 재귀로 도전했는데..

문제: https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 접근: 카운터 배열을 마련하여, 방 번호가 몇 번까지 나왔는지 체크합니다. 새로운 셋이 마련되어야 하는 순간은 방 번호가 현재 갖고 있는 셋보다 더 많이 주어졌을 때(numOfCounter < counter[num]) 인 경우입니다. 이런 경우에는, 셋을 하나 더 받아야 해당 번호를 수용할 수 있다는 뜻이기 때문입니다. 6이나 9일 경우에는 9나 6의 번호를 보고 판별합니다. 코드: namespace forAlgo2 { class Program { static string str..

문제: https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마�� www.acmicpc.net 접근: 스택을 이용해서 풀면 됩니다. 비어있을 때 닫는 괄호가 나오면 바로 종료하는 등 예외 처리를 해줍니다. 코드: #include #include #include #include using namespace std; string Line; string CheckBalance(stack, string); int main() { while (1) { stack Stack;..

문제: https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오�� www.acmicpc.net 접근: 점수를 위해서는 모두 버리는 것보다 오른쪽 카드 더미를 버리는 행위를 선택해야 합니다. 오른쪽 카드가 더 크다면, 왼쪽 카드만 버리거나 모두 버리는 것 중 큰 결과를 갖는 행위를 선택합니다. 카드 인덱스로 위 행위를 재귀 함수화하면, 중복되는 경우들이 있기 때문에 동적할당법을 사용합니다. (2000*2000) 코드: #include #include #i..

문제: https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 접근: c / d / l / j / n / s 여섯가지 알파벳의 경우에만 크로아티아 특유의 알파벳인지 확인하면 됩니다. 만약 해당 알파벳이면서, =, - 등의 기호가 따라오는 경우 크로아티아 특유의 알파벳으로 확인하고 순회하는 인덱스도 +1 또는 +2만큼 넘어갑니다. (코드 참고) 코드: #include #include using namespace st..

문제: https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 접근: 4방향 DFS를 사용했습니다. 이미 방문했거나, 이미 방문한 알파벳인 경우가 아닌 보드판만 다음 보드판으로 진행하게 했습니다...

문제: https://www.acmicpc.net/problem/2804 > A >> B; int row = -1, col = -1; for (int i = 0; i < A.length(); i++) { for (int j = 0; j < B.length(); j++) { if (A[i] == B[j]) { col = i, row = j; break; } } if (row != -1) break; } for (int i = 0; i < A.size(); i++) mat[row][i] = A[i]; for (int j = 0; j < B.size(); j++) mat[j][col] = B[j]; for (int i = 0; i < B.size(); i++) { for (int j = 0; j < A.siz..