생각 생각

https://acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 항상 난해한 백트래킹 문제다. 출력 조건은 길이가 m이 되었을 때다. N과 M(1)과 달리 1 2와 2 처럼 중복되었을 때를 배재한다. 즉, 앞 숫자는 무조건 뒷 숫자보다 작다. 이를 위해 i의 range가 1이 아니라 start이다. 길이가 m이면 종료하고, 아닐 땐 i를 넣고 다음 것을 넣을 지 말 지 dfs(i+1)을 해본다.

https://acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 특별할 것 없는 문제였다. bfs 한번 돌려주면 부모를 찾을 수 있다.

https://acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 사실상 브루트포스 문제이나 어떻게 효율적으로 다 찾는지를 고민해야 했던 문제. 제곱수인지 체크하는 함수와 공차를 -8부터 8까지 바꿔가며 수를 만들어보는 함수를 짰다. 핵심은 최대한 숫자를 붙이지 않아도 제곱수가 될 수 있다는 것. 즉 매번 숫자를 만든 후에 제곱수인지 체크해봐야 한다는 것이다. 그 후 모든 숫자에 대해서 해당 함수를 적용해주면 끝. ​ * 자주 까먹는 내장함수 정리 1. isi..

https://acmicpc.net/problem/17609 회문 문제를 여러 문제 풀었는데, 여전히 처음 풀 때는 헛짓거리를 하게 된다. 회문이 참 싫다. 문제를 푼 알고리즘 자체는 평범한 투포인터였다. 왜인지 안에서부터 출발하는 뻘짓을 했는데, 밖에서부터 확인하면서 들어오는게 합리적이다. 문제는 밖에서부터 안으로 오는 과정에서 한 번의 오류가 생겼을 때, 한개까지는 틀린 글자를 제거한다는 점이다. 그럼 왼쪽의 틀린 글자를 제거할 지, 오른쪽의 틀린 글자를 제거할 지를 결정해야 한다. 두 개는 배타적이지 않으므로, 두 가지 케이스를 모두 진행한다. 한 번 더 다른 글자가 나오면 회문이 아니다. 두 케이스 다 회문이 아니면 결과적으로 회문 아님 판정을 내린다. ​ 기억하자, 회문은 밖에서부터 투 포인터 ..

https://acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 마찬가지로 푸는 방법이 잘 생각나지 않아 고민한 문제였는데, 결과적으로는 생각보다 허무하게도 이분탐색이었다. 최소 거리는 1, 최대 거리는 처음 집에서 마지막 집으로 두면 그 사이 어딘가에 답이 있을 것이다. 그 답을 이분탐색으로 찾아나가는 것이다. 즉, 답을 k 라 할 때 우리가 k의 거리로 공유기를 c개만큼 설치할 수 있다면 그것이 답일 것이다. 그..

https://acmicpc.net/problem/14578 14578번: 영훈이의 색칠공부 영훈이가 색칠 할 수 있는 모든 경우의 수를 1,000,000,007로 나눈 나머지를 출력하시오. www.acmicpc.net 너무 안 풀려서 2주동안 고민한 문제. 1주 반쯤 되었을 때 아무리 생각해봐도 풀 수 없어 비슷한 개념을 찾아보다가 교란순열을 알게 되었다. ​ 사람 n 명이 있고 모두 서로 다른 모자를 쓰고 있다. 모든 사람이 동시에 모자를 벗고 섞은 뒤 다시 쓸 때 어느 누구도 자신의 모자를 쓰지 않는 경우의 순열이다. 그게 이 문제와 상관이 있는 이유는, 파란색과 빨간색을 취하되 파란색은 파란색끼리, 빨간색은 빨간색끼리 같은 칸에 칠해지지 않으며 나아가 파란색과 빨간색은 같은 행에 칠해지지 않기 때..

https://acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 재미있는 문제였다. 클래스 4 진입 문제이자 10000등대를 돌파하게 된 문제이기도 했다. 단순 bfs를 넘어 점점 생각해야 하는 문제가 나온다. ​ 선언부는 동일하다. 다만 1011과 같은 식으로 모든 숫자들이 붙어 나오는 경우, 이제 list comprehension 으로만 선언해야겠다. 아무래도 빠르고 직관적이다. 이 문제를 처음에 풀 때 반례를 통과할 수 없었다. 그 이유..

https://acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 처음엔 dp로 코드를 짰는데, 메모리 초과가 떠서 바로 bfs로 돌린 문제. 간단해서 함수는 안 만들었다.