Algorithm
-
[프로그래머스] 메뉴 리뉴얼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 좌표를 갱신하면서 해당 구역의..
-
백준 21608 상어 초등학교Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 25. 13:59
https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net - 빡구현 문제이다. 시간복잡도는 N^2명의 학생이 N^2개의 칸을 순회하면서 자신이 앉을 위치를 찾아나가므로 총 O(N^4)이다. - 일단 student_order배열에 앉을 순서대로 학생들의 번호를 넣고, 학생들을 배치하기 시작한다. 이 과정에서 모든 칸을 순회하면서, 어느 칸에서 좋아하는 학생이 인접 칸에 가장 많이 있는지를 탐색한다. 이 과정에서 벡터에 후보 칸을 모두 담는데, ..
-
백준 20057 마법사 상어와 토네이도Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 24. 11:48
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net - 빡구현 문제이다. 시간복잡도는 모든 칸을 순회하면서 각 칸에서 모래를 이동시키므로(상수연산) O(N^2)이다. - 필자는 먼저, 각 칸의 다음 이동 방향을 dir배열에 구현했다. 그 후, 이 방향을 기반으로 하여 토네이도가 이동한 후 흩날리는 모래들을 구해서 각 칸에 넣어주는 식으로 구현을 했다. - 방향을 구하는 과정은 1. 먼저, 해당 칸의 방향 최신화 2...
-
백준 20056 마법사 상어와 파이어볼Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 22. 13:29
https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net - 시뮬레이션 + 구현 문제이다. 시간복잡도는 k번 이동 * 각 이동마다 m개의 파이어볼이 이동하므로 O(km)이다. - 필자는 모든 정보를 vector 하나로 해결했다. vector에 들어가는 요소들은 순서대로 질량, 속력, 방향, 이동 여부이다. - 가장 먼저, 파이어볼의 정보를 받아 push_back한다. 이 후, 총 k번의 이동을 진행한다. 1. 파이..
-
백준 20055 컨베이어 벨트 위의 로봇Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 17. 15:44
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net - 시간복잡도는, 칸과 로봇을 옮기는 작업 O(N) + 내구도가 로봇이 올려질때마다 반드시 깎이므로 O(2NA)해서 O(2NA)이다. - 칸의 개수와 로봇의 개수를 배열에 담고, while문 조건으로 매 단계마다 내구도가 0인 칸의 개수가 k 이상인지를 확인한다. 가장 먼저 로봇과 벨트를 한 칸씩 이동시키고, 로봇이 내리는 칸에 도달했으면 로봇을 내려준다. 이동 과정에서 첫 ..