백준 알고리즘44 [BOJ]15683번: 감시 문제: https://www.acmicpc.net/problem/15683 시뮬레이션 문제입니다. 하나의 CCTV가 감시하는 방향은 4방향이고, 최대 8개의 CCTV가 있으므로 CCTV를 셋팅하는 경우의 수는 4^8입니다. 1. CCTV를 셋팅하는 경우의 수 만들기 2. (여러 경우의 수 중 하나의 케이스에 대해) CCTV를 쏴서 없어지는 빈 칸 갯수 COUNTING 구현을 단순하게 하기 위해서 CCTV를 쏘는 로직(func 메서드)은 오직 한 방향으로 쏘는 것만 구현했습니다. 그 후에 func 메서드를 여러 번 호출함으로써 두 방향, 세 방향, 네 방향을 탐색하는 경우를 처리했습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ15683.cc 2020. 7. 17. [BOJ]17090번: 미로 탈출하기 문제: https://www.acmicpc.net/problem/17090 TOP-DOWN 방식 DP로 풀고 시간초과가 나서 다르게 접근한 문제입니다. 문제가 되는 상황은 싸이클이 발생하는 상황을 어떻게 처리하느냐입니다. 해결 방법은 1. 기저사례 칸 좌표를 모두 큐에 넣습니다. 기저사례 칸이라 함은 현재 칸에서 주어진 방향으로 점프하면 밖으로 나가는 좌표를 의미합니다. 2. 큐에 들어가 있는 좌표에서 인접한 UDLR 방향 네 개의 좌표를 탐색합니다. 인접한 좌표 중에, 인접한 좌표 -> 기저 사례 칸으로 점프하는 인접한 좌표를 새로 큐에 넣습니다. (이 인접한 좌표가 다시 기저 사례 칸이 되는 방식입니다.) 3. BFS방식으로 방문 표시를 하면서 2번을 반복하며 기저 사례칸과 연결되는 모든 칸을 세주면.. 2020. 7. 16. [BOJ]14501번: 퇴사 문제: https://www.acmicpc.net/problem/14501 모든 경우를 다 구해봐야 하므로 DP 문제입니다. 제가 세운 점화식은 다음과 같습니다. dp[day][revenue]: 특정 DAY까지 revenue를 벌었을 때의 상태를 저장했습니다. dp[day][revenue] = max(특정 day 일을 하거나, 특정 day 일을 안하거나) 이렇게 나눌 수 있습니다. 특정 day 상담 일을 한다면 다음 날짜는 day 상담기간만큼 JUMP 할 것이고 특정 day 상담 일을 안한다면 day + 1 상담을 할 지 말지 결정하는 로직으로 넘어가면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ14501.cc 2020. 7. 2. [BOJ]1411번: 비슷한 단어 문제: https://www.acmicpc.net/problem/1411 문제 이해 못해서 멍때렸던 문제입니다. 최대 100개에 대해 2개씩만 비교하면 되니 100 combination 2의 경우의 수로 완전탐색이 가능합니다. 두 개씩 뽑아서 아래 사항들을 비교해주면 됩니다. 1. 길이가 같은지 2. 이미 매칭된 알파벳이 다른 알파벳과 매칭되었는지 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1411.cc 2020. 7. 1. 이전 1 ··· 6 7 8 9 10 11 다음
