Algorithm
-
백준 17143 낚시왕Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 26. 10:19
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net - 단순 빡구현 문제이다. - 내가 구현한 알고리즘의 경우, 시간복잡도는 O(r^2c^2)이다. - shark가 위치한 좌표는 pair 자료형의 벡터로 관리했다. 왼쪽부터 각각 속력, 방향, 크기, 상어의 이동 여부를 의미한다. t가 c를 넘지 않을 동안 주어진 while문을 실행한다. - 땅과 가장 가까운 상어를 잡고, 이후 상어의 이동을 시작한다. 일단 상어가 이동할 거리를..
-
백준 5430 ACAlgorithm/문자열 2021. 11. 22. 16:01
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net - 문자열 파싱 + 자료구조 deque 사용 문제이다.(vector를 사용해도 되긴 하다) - 1차로 입력이 좀 까다롭고, 2차로 R연산 시 배열을 뒤집지 않고 해결할 방법을 찾아야 한다.(만약 배열을 직접 뒤집을 시 시간초과가 나게 된다.) - 필자는 배열 형태를 입력받아서, erase 메서드로 맨 앞, 맨 뒤 대괄호를 없애고 추가로 쉼표를 기준으로 파싱을 한 뒤 정수로 변환하여 덱에 push를 했다. - reverse 상태 여부를 boolean변수로..
-
백준 17144 미세먼지 안녕!Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 19. 13:44
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net - 단순 구현 문제이다. 이런 문제는 무조건 맞춰야 코딩테스트 합격이 가능하다고 생각. 푸는데 50분정도가 걸렸다. - 삼성 기출문제들은 시간복잡도를 계산하는게 무의미한 것 같다. 굳이 계산하면 모든 좌표에 대해 rxc만큼의 spread 연산을 진행하고, 이 후 약 2r+2c만큼 추가 연산을 진행하고.. 이 과정들을 t번 반복하기 때문에 O(rct)이다. - 가장 먼저 모든 좌표에 대해서 미세먼..
-
백준 16236 아기 상어Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 19. 13:18
https://acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net - 1시간 10분이 걸린 문제.. 문제 조건을 꼼꼼하게 잘 읽고 풀었으면 10분은 단축시킬 수 있었을듯함 - BFS + 구현 문제이다. 시간복잡도는 의미없을 듯. BFS는 O(N^2) - BFS를 진행하는 동안 해야 하는 것들을 살펴보면 1) 물고기를 발견했을 때 (1) 물고기가 상어보다 크다면 탐색 중단 (2) 크기가 같다면 queue에만 push. 지나갈 수는 있기 때문이다. (3) 작다면 먹..
-
백준 16235 나무 재테크Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 18. 17:22
https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net - 단순 구현 문제이다. 특이점으로는 for loop이 여러개가 중첩된다. 따라서, 집중해서 잘 코드를 구현하는게 중요하다. 또한, 하나의 1x1 구역에 여러 개의 나무가 심어질 수 있다는 것에 유의한다. 이걸 C로는 어떻게 구현을 하는지는 모르겠지만, C++에는 vector라는 무기가 있기 때문에 2차원 vector 배열을 선언해서 각 영역에 존재하는 나무의 나이를 push 해 ..
-
백준 16234 인구 이동Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 18. 15:45
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net - 그래프 탐색을 활용하는 구현 문제이다. - 시간 복잡도는 알 수가 없다.. 언제까지 인구 이동이 일어날 지를 모르기 때문 - 가장 먼저, 모든 영역에 대해 BFS를 진행한다. 단 이미 다른 연합에 속한 영역은 진행하지 않는다. BFS를 진행할 때 마다 연합의 번호를 초깃값 1부터 1씩 늘려주면서 연합의 번호를 표시를 한다. 이는 나중에 인구 이동을 하기 위함이다. - 그 후, 모..
-
백준 15686 치킨 배달Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 18. 12:02
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net - 브루트포스 백트래킹 문제이다. - 치킨집 최대 13개 중 M개를 고르는 경우의 수 중 최대값은 13C6이며, 해당 경우에 각 집마다 치킨집과의 거리를 구해야 하므로 시간복잡도 값은 13C6∗2∗50∗13=2230800 정도가 나온다. - a벡터에 치킨집 m개의 좌표를 push 해 가면서 m개를 채우는 모든 경우의 수가 될 때 마다 치킨거리를 구하는 식으로 구현을 한다. 초..
-
백준 15685 드래곤커브Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 17. 19:19
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net - 시간복잡도는 신경 쓸 필요 없는 문제이다. g가 최대 10일때, 2^10 + 2^9 .. 정도의 계산량밖에 되지 않기 때문 - 규칙을 찾아내면 된다. 스택2개와 큐 1개를 사용했는데, 더 간단한 방법이 있지 않을까 생각한다. - x,y좌표는 계속해서 최신화하면서, 어느 방향으로 전진해야 하는 지를 구한다. 예를 들어 0과 1을 사용하여 전진을 했다면, 다음 세대에서 ..