Algorithm
-
백준 2096 내려가기Algorithm/DP 2022. 9. 16. 16:20
골드 5 난이도의 dp문제이다. 문제를 처음 읽으면 굉장히 간단한 dp문제로 보인다. max_dp[i][j] => i행 j열까지 내려왔을 때, 점수들의 합이 가장 큰 값 min_dp[i][j] => i행 j열까지 내려왔을 때, 점수들의 합이 가장 작은 값 1. 하지만 메모리 제한이 4MB이기 때문에, max_dp와 min_dp를 넉넉하게 최대값인 100001 * 4로 잡는 순간 메모리 초과가 뜨게 된다. 그래서 조금 더 생각을 해 보면, 딱 2개의 row만 필요함을 알 수 있다. 첫 row는 현재 행 까지의 최대(최소)값 들을, 다음 row는 해당 행 까지의 최대(최소)값을 넣어주고 다음 행을 조사하기 직전에, 마지막 row의 모든 값들을 첫 row로 이동 해 주면 되는 것이다. 따라서, 2 * 3 배열..
-
백준 23290 마법사 상어와 복제Algorithm/구현(Brute force, Back tracking, etc.) 2022. 1. 7. 15:57
https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net - 구현 + DFS문제이다. 디버깅하느라 정말 힘들었다. 시간 복잡도는 구할 수 없다. 단, 모든 격자에 물고기가 100만마리가 넘지 않도록 입력이 주어지므로, C * 100만 * 명령수 S(maximum 100)해서 시간 초과는 나지 않을 것이다. - 문제에서 주어진 단계들을 하나씩 알아보자. 1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간..
-
백준 14940 쉬운 최단거리Algorithm/그래프 2022. 1. 5. 21:26
https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net - 간단한 그래프 탐색 문제이다. 시간복잡도는 한 번의 bfs가 실행되므로 O(MN) - M과 N이 최대 1000이므로, 모든 칸에 대해서 bfs를 실행한다면 시간초과가 나게 된다. 따라서, 좌표가 2인 칸에서만 bfs를 실행 해 주면 된다. map과 똑같은 크기의 answer배열에 정답을 넣어줄 것이다. - 탐색을 진행할 때 방문하는 노드의 기준은 1..
-
백준 23289 온풍기 안녕!Algorithm/구현(Brute force, Back tracking, etc.) 2022. 1. 4. 13:36
https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net - 빡구현 문제이다. 시간 복잡도는 R * C 크기의 map * 만약 모든 칸에 온풍기가 존재한다면, 온도를 확산시키는 과정이 총 R*C 일어나므로, O((RC)^2)이다. 하지만 시간복잡도 조절을 위해 이 과정이 최대 101번정도 이루어지므로, 시간초과 걱정은 X - 가장 먼저, map의 정보를 입력받는다. 여기서 문제에 주어진 조건대로, map의 값이 1~4이면 온풍기, 5이면 체크해야 하는 ..
-
[프로그래머스] 정수 삼각형Algorithm/DP 2022. 1. 2. 19:10
https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr - 시간복잡도는 n = 삼각형의 높이라 할 때, n * (n-1) * (n-2) .. * 1 이므로 O(N^2)이다. - 간단한 DP문제이다. DP문제는 반드시 점화식을 세워야 한다. i를 꼭짓점부터의 해당 층의 상대적인 위치, j를 그 층에서의 요소의 인덱스라 할 때, 점화식은 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] (i, j = 0,1,...n) 단, 예외로 해당 층의 ..
-
백준 23288 주사위 굴리기2Algorithm/구현(Brute force, Back tracking, etc.) 2022. 1. 1. 05:51
https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net - 단순구현 + DFS/BFS 문제이다. 시간복잡도는 K번의 이동 * 이동 시 BFS하여 O(KMN) - 이 문제 를 풀어보았다면 무난하게 풀 수 있는 문제이다. - 가장 먼저, 주사위의 규칙성부터 찾아본다. square 배열을 두고, 초기 값을 {1,2,3,4,5,6}으로 주고 각 4개의 방향으로 이동 시 값이 어떻게 바뀌는지를 캐치해야한다. 초기 상태에서 동쪽을 예로 들면, ..
-
[프로그래머스] 여행 경로Algorithm/그래프 2021. 12. 31. 14:28
https://programmers.co.kr/learn/courses/30/lessons/43164?language=cpp 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr - DFS/BFS 문제이다. - 가장 먼저, dfs를 어떻게 구현 할 지를 생각해야 한다. dfs함수의 매개변수에는 tickets배열, 현재 머무는 공항의 이름, 현재까지의 모든 경로를 문자열로 기록 해 놓은 path, 티켓을 얼마나 사용했는 지를 나타내는 count변수를 사용한다. dfs를 구현하는 경우..
-
백준 21611 마법사 상어와 블리자드Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 30. 13:34
https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net - (빡!)구현 문제이다. 시간복잡도는 블리자드 연산에 N^2 + 총 M번 명령이 수행되므로 O(MN^2)이다. - 이 문제는 초기 접근법이 중요하다. 초기 접근법에 따라 코드 설계 난이도가 달라진다. 먼저, 풀이 과정으로는 1. 상어 칸부터 시작해서 맨 마지막 칸 까지의 좌표를 순서대로 map_xy에 담는다. 해당 로직은 all_xy 함수에서 실행된다. move 변수는 주어진 ..