공부일기장

https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 비트마스킹에 빠져있을 때 푼 문제. 싸지방에서 풀이 올리던 블로그에서 가져온 글 - 2 접근 방법 4991번 문제 풀이 에서 언급했던 것 처럼 배열에서 최소길이와 특정 지점을 모두 방문해야하고, 중복 방문이 허용되므로 5개의 지점의 방문 상태를 비트마스킹으로 나타내서 푼다. 아주 전형적인 bfs + bitmasking 문제. 풀이 tag : dfs, bitmasking //BOJ 17244..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 그래프만 다루다보니 트리가 잊혀져가서 트리문제중 기억에 남던 문제를 다시 풀어보았다. 접근 방법 1967번과 같은 문제인데, 노드의 갯수가 늘어났다. V가 최대 10만이므로, O(n^2)의 방법으로는 풀리지 않음을 주의해야한다 아무 노드를 루트로 지정하여, 아래로 내려갈 때 가장 긴 길이와 두번째로 긴 길이를 구하여 더하는 방식으로 접근했다. 그러나 위의 그림1 처럼, 루트가 아님..

https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net Good Bye BOJ, 2021! B번 풀다가 폴라드 로 알고리즘으로 푸는줄 알고 헛수고하다가 복습 겸 찾아 본 소인수 분해 문제. 사실 소인수 분해 알고리즘을 잘 몰랐는데, 이 문제 때문에 소인수 분해 알고리즘을 좀 찾아봤다. 싸지방에서 풀이 올리던 블로그에서 가져온 글 - 1 접근 방법 소인수 분해는 여러가지 방법으로 수행 가능하다. 그중에서 '에라스토테네스의 체' 분류에서 문제를 찾았다. 일반적..

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 웹 공부를 하기 싫을때 나는 백준을 푼다. dp를 풀면 마음이 평온해지기 때문이다. 접근 방법 개근상을 받지 못하는 조건이 명확히 나온다. 두번 이상의 지각 또는 연속된 세번의 결석. N+1일에서 출석, 지각, 결석 세 가지의 경우가 가능하고, 이는 N일의 상태에서 가져오는 전형적인 바텀-업 dp문제. dp[N][late][consAbs]; N일까지 총 지각한 횟수와, N일까지 연속된 결석의 횟수를 기록해야한..

https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net kks227 블로그 따라가며 알고리즘 다시 익히는 중이다. 비트마스킹을 되게 재밌게 했었는데 기억이 안나서 감잡기 문제. 접근 방법 딱 봐서 bfs문제인데, 방문했던 칸을 다시 방문할 수 있다는 조건이 존재한다. 1194번 문제랑 비슷하게, 현재 방문한 상태를 저장하는 변수 하나를 큐에 같이 넣어서 탐색하면 된다. 'n*m 배열의 최단거리' + '특정 지점 모두 방문' 두 조건이 붙으면 bfs+비트마스킹으..

https://www.acmicpc.net/problem/20957 20957번: 농부 비니 타고난 농사꾼 비니는 최근 숫자 공부에 푹 빠졌다. 열심히 숫자 공부를 하던 비니는 놀라 자빠질 수밖에 없었다. 숫자 7이 비니가 가장 아끼는 낫과 비슷하게 생겼기 때문이다. 옛말에 낫 놓고 7 www.acmicpc.net dp는 꾸준히 안하면 무조건 까먹을거 같다. 그중에서도 내가 젤 좋아하는 digit dp문제이다. digit dp를 좋아하는 이유는 직관적으로 규칙이 보이기 때문. 접근 방법 모든 숫자의 합과 곱을 알아야한다. digit dp는 n-1자리의 결과에서 0~9 숫자를 붙일 때 발생하는 규칙을 이용하여 dp 점화식을 세우면 쉽다. 내기준 n-1 자리 모든 숫자의 합은 , 0~6의 모든 상태를 알아야..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net bfs + 백트래킹 감잡기 문제. 접근 방법 D, S, R, L 변환 방법으로 특정 숫자에 최단으로 도달하고, 도달 방법을 찾는 문제이다. bfs를 이용하면 최단 길이는 어렵지 않게 구할 수 있고, 변환 방법을 기억해야한다. bfs를 돌릴 때 큐에 변환된 과정을 넣으면 메모리가 초과될 것 같으므로, num1 -> num2로 변환될 때 num2에서 num1으로 돌아갈 수 있도록 어떤 숫..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net n-queen 문제와 더불어 백트래킹의 기본이자 교과서같은 문제 라고 나혼자 정했다. js로 쿼리도 게임을 만들면서 bfs 백트래킹을 통해 최적의 위치를 찾아야 하는데, 백트래킹 하는 법을 까먹어서 급하게 다시 도전한 문제. 접근 방법 백트래킹이란게, 결국 완전탐색을 재귀적으로 하는 것이라고 나는 생각한다. 앞에서부터 빈 칸을 1~9로 채워 나가는데, 해당 칸에 가능한 숫자인지 확인해주고, 가능하..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 벽 부수고 이동하기 시리즈 마지막 문제 접근 방법 이 문제는 1.2.3 번 문제의 코드와 연관이 없는 문제다. 특정 벽을 부술 때 연결된 칸 수를 구한다. 가장 먼저 떠오르는 풀이는 모든 벽을 부숴보고 bfs/dfs를 돌리는건데, K개의 벽이 있다고 할 때 시간 복잡도가 O(NMK)가 될 것이 자명하므로 시도하지 않는다. bfs/dfs를 최소한으로 사용하는 경우를 생각 해 보..

https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽 부수고 이동하기 시리즈 3번째 접근 방법 벽 부수고 이동하기 2 문제와 비슷한데, 두 가지 조건이 추가되었다. 1. 밤과 낮이 번갈아가며 바뀌고, 낮에만 벽을 부술 수 있음. 2. 제자리에 머무를 수 있음 생각을 해보면, 최단 거리를 구하는 데 제자리에 머무르는 거는 도움이 되지 않는다. 그렇다면 언제 제자리에 머물러야하느냐? 바로 벽을 부숴야하는데 밤이라서..