Algorithm/구현(Brute force, Back tracking, etc.)
-
백준 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. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간..
-
백준 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이면 체크해야 하는 ..
-
백준 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개의 방향으로 이동 시 값이 어떻게 바뀌는지를 캐치해야한다. 초기 상태에서 동쪽을 예로 들면, ..
-
백준 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 변수는 주어진 ..
-
[프로그래머스] 메뉴 리뉴얼Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 29. 07:21
https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr - 구현, 백트래킹, hash 문제이다. 백트래킹을 사용할 때, 주어진 문제의 조건을 반드시 확인해야 한다. 문자열의 길이가 최대 10이므로, 조합에 대한 경우의 수는 10Cr * 20( 2 max_num){ // max값 갱신 max_num = um[all_string[j]]; temp_answers.clear(); temp_answers.push_back(al..
-
백준 21610 마법사 상어와 비바라기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 28. 22:49
https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net - 상대적으로 쉬운 난이도의 구현 문제이다. 시간복잡도는 O(mN^2)이다. - cloud_xy에 주어진 4 칸의 좌표를 담고, 총 m번의 이동을 시작한다. 1. 구름 이동의 경우, 1번 행(열)과 n번 행(열)이 연결되어 있는 점을 잘 고려해서 구현한다. 필자는 주어진 방향대로 한 칸씩 이동하도록 하되, 처음 s를 입력받을 때 s=s%n을 해 줌으로써 이동 횟수를 최소화해주었다. 이동할 ..
-
백준 21609 상어 중학교Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 27. 14:47
https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net - 빡구현 + BFS이다. 시간 복잡도는 BFS N^2 + 중력 작용 N^2 + rotate N^2 + 중력 작용 N^2 = O(N^2)이다. 1. 가장 큰 블록 그룹 찾기 => BFS를 통해 블록 그룹을 찾아준다. 이 때, (1) 범위를 벗어나거나 (2) 해당 칸이 -1이거나 (3) 현재 블록 그룹 번호와 다른 경우는 탐색을 중단한다. 이 과정에서 num_group을 인덱스로 활용하여 블록 ..
-
백준 20058 마법사 상어와 파이어스톰Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 25. 14:34
https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net - 구현 + 약간의 BFS가 섞인 문제이다. 시간복잡도는 모든 칸에 대해 회전을 진행하므로 N^2 * Q = O(QN^2)이다. - 먼저, 회전을 진행 할 구역의 길이 area_length(2^l)를 구한다. cmath 헤더의 pow 메서드를 사용하면 제곱수를 간단하게 구할 수 있다. 이 후, 이 값을 활용 해 주면서 start_x, start_y 좌표를 갱신하면서 해당 구역의..