Algorithm
-
백준 19237 어른 상어Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 16. 18:42
https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net - 맵의 크기는 최대 N^2이고, 총 t초동안 이동가능하므로 O(t * N^2)이므로 시간초과는 나지 않는다. - 가장 먼저, 상어들이 이동하기 위한 좌표를 한 번에 구한다. 한 번에 이동까지 하도록 구현을 하면, 로직이 굉장히 복잡해 질 것이다.(상어들이 한 번에 이동을 하는 것을 가정하기 때문에, 한 마리씩 이동시키는 것은 거의 불가능할 것이다.) ..
-
백준 10026 적록색약Algorithm/그래프 2021. 12. 10. 15:02
https://www.acmicpc.net/status?user_id=totw2018&problem_id=10026&from_mine=1 채점 현황 www.acmicpc.net - 그래프 탐색 알고리즘 문제이다. 시간복잡도는 그래프 탐색 + 문자 치환 탐색 + 그래프 탐색 해서 총 O(n^2)이다. - 특이하게, 입력을 문자열들로 준다. 따라서 필자는 string 자료형으로 총 n번을 입력받고, 입력 받을 때 마다 문자 하나하나를 char 배열 map에 저장을 했다. 또한, 처음 주어진 map에서 BFS 한 번, 이 후 맵의 G를 모두 R 문자로 바꿔준 다음 또 한 번 BFS를 진행하였다. 이러한 점 외에는 다른 그래프 탐색 문제와 크게 다를 것이 없다. - 여담으로, 15분만에 문제를 풀어내서 뿌듯하다..
-
[프로그래머스] 조이스틱Algorithm/Greedy 2021. 12. 10. 09:59
https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr - Level2 Greedy문제이다. 시간복잡도는 conversion 호출에 O(N), 모든 문자열에 대해 탐색을 진행하므로 O(N) 해서 O(N^2)이다. - 무난한 문제지만, 많은 사람들이 테케 11번을 통과 못하는 듯했다. 이유는 단방향으로 진행하는 코드를 작성해서인데, 이렇게 작성하면 안 되고 현재 알파벳을 원하는 알파벳으로 변경한 뒤..
-
백준 7569 토마토Algorithm/그래프 2021. 12. 4. 17:38
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net - 그래프 탐색 문제인데, 특이하게도 3차원으로 값이 주어져서 난이도가 조금 올라가는 문제이다. 따라서, 필자는 3차원 배열을 활용하였고 M,N,H를 각각 X,Y,Z로 두어서 계산을 하였다.(각각 행, 열, 높이) - 시간복잡도는 O(MNH)이 나온다. 2차원 그래프탐색을 H번 진행해야 하므로! - 처음에 토마토가 담긴 칸을 queue에 담는다. 또, visited를 0으로..
-
백준 17822 원판 돌리기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 1. 16:28
https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net - 브루트포스 + 빡구현 문제이다. - 시간복잡도는 N개의 행에 대해서 rotation을 돌리는 데에 M^2 = O(NM^2) + 모든 칸에 대해서 인접 칸을 살펴야 하므로 O(NM) = O(NM^2)이다. 따라서, 주어진 시간 내에 통과가 가능하다. - 처음 문제를 읽었을 때 어떻게 틀을 잡아야 하는지 망설여질 수 있는데, 삼성 기출이 늘 2차원 배열에서 시작하는 것을 기반으로 ..
-
백준 17779 게리맨더링2Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 30. 19:51
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net - 브루트포스 + 빡구현 문제이다. - 시간복잡도는, 최악의 경우 거의 O(N^6)까지도 도달할 수 있다. 하지만 N의 최대값이 20이므로 1억 이하이기 때문에 해당 알고리즘으로 통과가 가능하다. - 시작점 x,y와 모든 d1, d2에 대한 경우의 수들을 선택해서 계산을 해야 한다. 4중 for문으로 4가지 변수값을 선택했다면, area 배열에 구역을 입력 해 주면 된다. 일단 1. 5번 경계점들을 넣..
-
[프로그래머스] 신규 아이디 추천Algorithm/문자열 2021. 11. 29. 16:23
- 카카오 2021 코딩테스트 기출문제 1번, 정답률이 57퍼정도였던 문제이다. 꼭 맞춰주어야 하는 문제이다 - 먼저, 대문자를 소문자로 변환한다. 이 과정에서는 isupper, tolower 함수를 사용한다. - 다음으로, islower, isdigit을 통해 소문자, 숫자, 빼기, 밑줄, 마침표만을 추가한다. - 세 번째로, 마침표가 2번 이상 연속된 부분을 제거하는데, 이는 new_id에 하나씩 push를 하면서 new_id의 맨 마지막 글자가 '.'이고, 삽입할 글자도 '.'이라면 skip하는 식으로 구현을 한다. - 다음으로, 끝 마침표를 제거한다. 처음 마침표는 이미 전 단계에서 제거되었으므로 따로 구현할 필요가 없다. - 5단계도 쉽게 진행하면 되고, 6단계는 substr(인덱스, 추출할 문..
-
백준 17142 연구소3Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 26. 12:40
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net - 브루트포스 백트래킹 + BFS 문제이다. - 시간 복잡도는 BFS에 O(N^2) + 백트래킹은 10Cn의 최대값이므로, 값이 10! 이하이기에 시간초과는 나지 않는다. - 먼저, map에 정보를 입력받는다. 이 때, virus의 좌표 정보는 virus 벡터에 따로 저장한다. 그 후, m개의 바이러스를 선택한다. 선택을 하는 과정은 백트래킹을 통해 진행하며, 전역변수 selected_virus에 해당 좌..