실전 압축 코딩

1043번: 거짓말 (acmicpc.net) 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net long 자료형 비트 연산 때문에 고생한 문제.... 기본적인 CS 지식이 부족하다고 느꼈다. 풀이 알고리즘 파악 비트 마스킹, 유니온 파인드 문제를 정리하면, 결국 지민이는 둘 중 하나를 선택해야 한다. 과장하기 vs 진실을 말하기 그런데 여기서 조건이 있다. 과장을 한 대상에게 진실을 말하면 안 되고, 진실을 말한 대상에게 과장을 하면 안 된다는 것이다. 즉, 바이러스에 감염되듯이 진실을 들을 대상과 같이 파티에 참석한 인원..

11049번: 행렬 곱셈 순서 (acmicpc.net) 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 알고리즘 파악 DP 처음부터 DP 냄새가 나서 알고리즘은 쉽게 파악했지만... 디테일 한 풀이에서 시간이 많이 걸린 문제 구현 1. 행렬의 곱셈 방식 파악하기 n*m 의 행렬과 m*k의 행렬의 곱셈식은 n*m*k이다. 즉, (ABC)(DEF) -> (A의 N) * (D의 N) * (F의 M)인 것이다. 2. DP ABCDEF의 모든 경우의 수는 -> (A)(BCDEF) , (AB)(CDEF)..

1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 생각보다 오래 걸린 문제... 처음에 잘못 접근을 해 애 먹었다. 풀이 알고리즘 파악 위상정렬+ DP 처음에 무턱대고 BFS로 접근하였다... 단순히 이전 건설 시간의 최댓값만 총 건설시간에 더하였는데 모든 정점이 서로 연결된 케이스를 풀 수가 없었다... 구현 문제의 핵심은 결국 내 건물의 까지의 총 건설시간 = (이전 테크 건물들의 총 건설시간 중 최댓값) + (내 건설시간) 이라고 생각했다. 그래..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 처음으로 한 시간 만에 푼 문제... 그간의 성장세가 눈에 보여 좋았다! 풀이 알고리즘 파악 최단거리 bfs 문제 + 구현 구현 1. queue에는 빨간구슬과 파란 구슬의 위치를 저장한다. 이를 배열로 표현하였다. marble 배열의 0 = 빨간 구슬의 x , 1= 빨간 구슬의 y , 3= 파란 구슬의 x ,4= 파란 구슬의 y 2. bfs를 통해 구슬을 움직인..