분류 전체보기
-
백준 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 이상인지를 확인한다. 가장 먼저 로봇과 벨트를 한 칸씩 이동시키고, 로봇이 내리는 칸에 도달했으면 로봇을 내려준다. 이동 과정에서 첫 ..
-
백준 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)이므로 시간초과는 나지 않는다. - 가장 먼저, 상어들이 이동하기 위한 좌표를 한 번에 구한다. 한 번에 이동까지 하도록 구현을 하면, 로직이 굉장히 복잡해 질 것이다.(상어들이 한 번에 이동을 하는 것을 가정하기 때문에, 한 마리씩 이동시키는 것은 거의 불가능할 것이다.) ..
-
2021 겨울 라인 인턴쉽 코딩테스트 후기Etc/Diary 2021. 12. 11. 12:58
- 총 5문제, 150분이 주어졌다. - 인턴쉽 코딩테스트라 그런지 널널한 모습이었다. 보통 원격시험이면 캠을 키거나 브라우저에 락다운을 걸고 진행하는데, 그런거 없이 그냥 문제만 풀면 되었다. 어떠한 부정행위, 검색행위도 감시 안 함.. - 1번 문제는 for문으로 답을 체크해 나가면서 푸는 브론즈3 정도의 문제였다. - 2번 문제는 MST문제였다. 크루스칼 알고리즘을 사용해서 최소 비용 구하면 되었음. 실버3정도? - 3번 문제는 빡(?)구현 문제였다. 문제에서 주어진 아날로그 숫자 모양을 기반으로 주어진 아날로그 숫자들이 무엇인지를 구하는 문제. 실버 2정도..? - 4번 문제는 완탐 백트래킹 문제였다. 삼성 코테 연습으로 지겹게 풀던 유형이라.. 쉽게 풀었다. 실버1~골드5 정도 - 5번 문제는 ..
-
백준 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으로..