분류 전체보기
-
백준 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에 해당 좌..
-
백준 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) 작다면 먹..