생각 생각

https://acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net bfs로 풀다가 막혀서 dp로 풀게 된 문제. bfs로도 분명 가능은 한데, 메모리 초과가 뜬다. visited 처리를 잘 못해주어서이다. 처음 풀었던 풀이는 이랬다. 즉 heap을 만들어 최대한 비용이 적은 움직임을 먼저 하여 가장 먼저 끝난 것을 출력하는 것이었다. 다만 이렇게 할 경우 중복되는 것들을 잡아낼 수 없어 heap에 자꾸 값이 들어가고, 그러니 결국 메모..

https://acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 범위를 보자마자 이분 탐색을 떠올렸고, 시도했으나 여전히 이분 탐색이 익숙하지 않아 고생한 문제. 이분 탐색은 항상 언제 결과값을 mid로 설정할지가 중요하다는 것을 다시금 상기시켜준 문제였다. 결국 문제는 '합의 절대값이 가장 작은 두 수를 어떻게 찾을래?'이다. 별거 아닌 듯 보이지만, 여기서 핵심은 res=mid의 위치이다. 즉, res를 갱신한 시점이 end값을 mid-1로 바꾸기 전이기 때..

https://acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 드디어 책에서 몇 번 본게 다인 CCW 문제를 보게 되었다. 두 벡터의 외적 결과값이 양수라면 반시계방향으로 향하고, 음수라면 시계방향, 0이라면 일직선이다.

https://acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 고등학교때 많이 보던 신발끈 정리를 이용해 풀 수 있는 문제였다. 각 모서리마다 원점과 모서리가 이루는 삼각형의 면적을 구해 더하는 방법이다.

https://acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 문제를 푸는 발상은 바로 할 수 있었으나 시간복잡도 줄이는 방법을 한참을 고민한 문제였다. 문제를 보자마자 떠올린 문제는 단지번호붙이기(https://acmicpc.net/problem/2667)였다. 쉽게 말해 그룹을 나누는 것인데, 이런 알고리즘을 flood-fill algorithm이라고 한다고 하는 것을 나중에 알았다. ​ 문제를 푸는 방법은, 벽이 아닌 칸을 만나면 그 칸과..

https://acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net dp로 풀면 메모리 초과 오류가 난다. bfs로 찾아가면 어렵지 않게 해결할 수 있는 문제였다. n부터 나눌 수 있으면 나누고, 아니면 빼며 탐색해주면 된다.

https://acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 정말 오랫동안 괴롭힘당한 문제였다. 많은 풀이 방법을 시도해봤는데 전부 틀렸다. dictionary로 캐싱을 시도하고 회문을 구하는 방법을 구하는 등 여러 방법을 시도했지만, 결과적으로 메모이제이션을 이용해야 했던 것은 맞으나 이중 리스트를 이용해 메모이제이션을 구현해야 했다. a점부터 b점까지가 팰린드롬이면, 이중 리스트 dp[a][b]=1로 바꿔주는 것이 이 문제풀이의 핵심이다. 우선 확실하게 팰린드롬인 것들을 처리해준다. 한 글자짜리와 ..

https://acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 재귀는 너무 어렵다. 여전히 헷갈리는 부분이 많다. 특히 이런 문양 찍기 문제를 풀 때 공백 처리가 어렵다. 이럴 때는 애초에 default 상태를 공백으로 해두고 좌표를 찍으며 *을 채워가는 것임을 기억하자. ​ N==3일때는 기본 문양이다. 3보다 클 때는 2씩 나눠가며 위치만 바꿔 재귀함수를 시행해주면 된다.