알고리즘 문제/BOJ17 [BOJ][20529] 가장 가까운 세 사람의 심리적 거리 문제 : www.acmicpc.net/problem/20529 완전탐색을 하면 O(N^3)의 시간복잡도를 가지는데 제한 사항을 보면 N이 10만이기 때문에 TLE가 발생할것이다. 시간을 줄일만한게 어디없나 보면 MBTI는 총 16가지이다. 이걸 사용할 수 있을 것 같다. 사람들은 16개 중 하나를 가지는데 최대한 겹치지 않게 MBTI를 가지고 있다고 가정하자. 그럼 16명의 사람까지는 동일한 MBTI를 가지지 않고 모두 고유한 값을 가질 수 있다. 16 ~ 16*2 명의 사람까지는 동일한 MBTI를 가지는 사람이 최대 두 명까지 나올 수 있다. 그러면 16 * 2 + 1 이상의 사람은 어떻게 되는가. 16*2 명의 사람들은 동일한 MBTI를 가지는 사람이 2명이 있다. (각 MBTI 모두 2명의 사람) .. 2021. 1. 1. [BOJ][20528] 끝말잇기 문제 : https://www.acmicpc.net/problem/20528 입력 문자열이 모두 팰린드롬 문자열이라고 확정되었으므로 굳이 팰린드롬 문자열인지 확인할 필요는 없다. 문자열들의 가장 앞에 문자만 비교하여 만약 다른 문자가 나온다면 0, 모두 같은 문자라면 1이 정답이된다. 시간복잡도는 O(N) 소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/20528.%20%EB%81%9D%EB%A7%90%EC%9E%87%EA%B8%B0.cpp 2021. 1. 1. [BOJ][17143] 낚시왕 문제 : www.acmicpc.net/problem/17143 시뮬을 돌려봅시당. 상어의 위치를 key값, 상어 정보(크기, 방향, 속도)를 value로 하는 map을 하나 만든다. 낚시꾼은 열의 왼쪽부터 오른쪽으로 한 칸 씩 정기적으로 이동한다. 따라서 0열부터 R-1까지 이동하면서 탐색중인 열의 0행부터 C-1까지 상어들을 탐색하며 가장 위에 있는 상어 정보를 가져온다. 해당 상어를 낚시왕이 잡게 될 것이고 따라서 이 ㄴ상어의 크기를 정답에 더해준 뒤 상어 map에서 삭제한다. 낚시왕이 어떤 상어를 잡게 될지 시뮬해보았기 때문에 이제 상어들을 이동시킨다. 상어의 이동방향대로 이동시키면 되는데 문제는 속도이다. 속도의 최대값은 1000이여서 모든 상어들(RxC = 10000)을 낚시왕이 상어를 잡는 동.. 2020. 11. 15. [BOJ][17144] 미세먼지 안녕! 문제 : www.acmicpc.net/problem/17144 구현문제. 먼지가 이동한 뒤의 모습을 저장할 배열 (let, newArr)을 하나 만든다. newArr은 0으로 초기화한다. 먼저 먼지의 확산된 모습을 newArr 배열에 담는다. 집 배열을 탐색하면서 해당 칸(let, (x,y))의 값이 -1 이면 공기청정기 이므로 나중에 공기청정기 확산할 때를 대비해 해당 좌표를 cleaners 배열에 담아두고 다음을 탐색한다. 0 이면 먼지가 없다는 뜻이므로 다음을 탐색한다 양수값이면 먼지가 확산시킨다. 상하좌우로 이동한 좌표값을 (nx, ny)라 하자. (nx, ny)가 RxC 배열칸을 넘어가지 않고 집에서 nx, ny 좌표값이 -1이 아닌경우(공기청정기) 해당 칸으로 먼지가 확산될 수 있으므로 new.. 2020. 11. 8. [BOJ][16235] 나무 재테크 문제 : www.acmicpc.net/problem/16235 N x N 크기의 땅. 처음 모든 땅에는 5만큼의 양분이 들어있다. 한 칸의 땅에는 여러 개의 나무가 심어질 수 있다. M 개의 나무를 심었다. (x, y, z) = (x 좌표, y 좌표, 나이) K 년 후 살아있는 나무 개수를 구하라. 봄 : 나무가 자신 나이만큼의 양분을 먹으면 나이가 1 증가. 양분 못 먹으면 죽는다. 자신의 칸의 양분만 먹을 수 있다. 나이가 작은 순 부터 양분 섭취. 여름 : 죽은 나무가 양분(나이/2)으로 변한다. 가을 : 나무의 나이가 5의 배수일 때 인접한 8 칸에 나이가 1인 나무가 생긴다. 겨울 : A 배열만큼의 양분이 추가된다. 구현 문제. 배열은 총 3개를 사용했다. lands : 각 칸에 있는 나무의 나.. 2020. 11. 7. [BOJ][14890] 경사로 문제 : www.acmicpc.net/problem/14890 구현 문제. 행 탐색시 왼쪽에서 오른쪽. 열 탐색시 위에서 아래로 탐색한다. 탐색 중 이전 배열 값을 before, 현재 탐색 중인 값을 now라 하자. let, i = 탐색중인 배열 인덱스 int now = (direction == ROW) ? arr[start][i] : arr[i][start]; int before = (direction == ROW) ? arr[start][i-1] : arr[i-1][start]; now, before 값만 알면 되기 때문에 구현시 탐색하려는 행, 열 값과 행, 열 탐색 방향만 알면 위와 같은 방법으로 알 수 있다. 같은 높이를 가진 길이 연속적으로 나오는 수를 cnt라 하자. [그림1]에서 왼쪽은 b.. 2020. 11. 6. 이전 1 2 3 다음
