알고리즘
-
[백준] 구간 합 구하기(2042번)알고리즘/백준 2021. 9. 19. 12:09
문제 링크 풀이 쉬운 문제는 아닙니다. 세그먼트 트리를 이용해야 합니다. 먼저 배열을 통해 살펴보겠습니다. 1. 구간 합 구하기 2. 특정 위치 값 변경 1번의 경우 점화식을 이용해서 푼다면 다음과 같으므로 O(N)입니다. s[0] = a[0]; for (int i = 1; i < n; ++i) { s[1] = s[i-1] + a[i]; } 2번은 a[4] = 3;의 방법으로 이루어지기 때문에 O(1)입니다. 1번이 M번, 2번이 K번 이루어진다면 O(NM + K)입니다. 문제에서 N, M, K는 적은 숫자가 아니기 때문에 O(NM + K)는 충분히 오래 걸릴 수 있습니다. 세그먼트 트리를 이용하면 O((M+K)*log₂N)에 가능합니다. O(NM + K)와 크게 다르지 않은 것처럼 보일 수 있는데, 문..
-
[백준] 유기농 배추(1012번)알고리즘/백준 2021. 9. 17. 09:41
문제 링크 풀이 전형적인 그래프 탐색 문제입니다. 문제에서 X좌표는 (행, 열) 중에 '열', Y좌표는 '행'에 해당합니다. 밭을 이차원 벡터로 표현하고 배추를 탐색한 곳은 확인하는 bool형 이차원 벡터도 필요합니다. 코드 #include #include #include using namespace std; int main() { int T, M, N, K; // c r 배추 scanf("%d", &T); int r_dir[] = {0, 1, 0, -1}; int c_dir[] = {1, 0, -1, 0}; while (T--) { scanf("%d", &M); scanf("%d", &N); scanf("%d", &K); vector map(N, vector(M, 0)); vector checked(N..
-
[프로그래머스] 순위알고리즘/프로그래머스 2021. 9. 16. 12:46
문제 링크 풀이 이 문제는 모든 정점에 대해 최단 경로를 찾는 플로이드-워셜 알고리즘을 이용해 풀 수 있습니다. 주어진 예제를 통해 이 알고리즘을 어떻게 적용하는지 알아보겠습니다. 주어진 예제는 {4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5} 입니다. {A, B}에서 A는 B를 항상 이깁니다 - 2는 네 번의 경기를 하므로 순위가 확정적으로 정해집니다 - 5번이 2번에게 확실하게 지는 거라면, 5번은 2번을 이기는 모든 선수에게도 집니다 - {4,2} {2,5}에서 {4,5}가 도출됩니다 - 그러므로 {4, 5}, {3, 5}, {1, 5}, {2, 5}가 성립합니다 코드 #include #include using namespace std; int solution(int n, vec..
-
[프로그래머스] 정수 삼각형알고리즘/프로그래머스 2021. 9. 15. 19:53
문제 링크 풀이 점화식 d[i][j]는 왼쪽 대각선 위인 d[i-1][j-1]와 오른쪽 대각선 위인 d[i-1][j] 중에서 큰 값을 triangle[i][j]와 더해준 값입니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + t[i][j] 코드 #include #include using namespace std; int wrap(int a) { return a < 0 ? 0 : a; } int solution(vector triangle) { int answer = 0; int size = triangle.size(); vector d(size, vector(size, 0)); for (int i = 0; i < triangle.size(); ++i) for (int j = 0..
-
[프로그래머스] 디스크 컨트롤러알고리즘/프로그래머스 2021. 9. 15. 18:29
문제 링크 풀이 1) 지금 처리되고 있는 작업이 끝나는 시간(현재 시간)을 초과하지 않으면 2) 요청된 작업들은 우선 순위 큐에 담아 작업 시간이 빠른 순서대로 처리합니다. 3) 그렇지 않은 작업은 요청 시간이 도래할 때까지 기다렸다가 1번, 2번을 반복합니다. 우선 순위 큐에 비교 함수를 넣을 때 함수 객체를 넣어도 되고 람다 표현식을 넣어도 됩니다. 내부적으로 생성자를 호출하는데 람다식은 생성자가 없기 때문에 직접 초기화해줘야 합니다. 템플릿으로 넣어주는 것은 타입이기 때문입니다. 코드 #include #include #include #include using namespace std; int solution(vector jobs) { int answer = 0, current_time = 0; in..
-
[hacker rank] The bomberman game알고리즘/Hacker Rank 2021. 9. 10. 21:32
문제 링크 풀이 주어진 예제로 테스트 해보면 주기를 구할 수 있습니다. 3, 7, 11초..에 그리드의 형태가 같고, 5, 9, 13초..에 그리드의 형태가 같습니다. 첫 번째 주기는 폭발이 한 번 일어날 때며 두 번째 주기는 폭발이 두 번 일어날 때입니다. 이 규칙을 이용해 n의 크기를 줄여주면 됩니다. 코드 vector bomberMan(int n, vector grid) { vector pos; if (0 == n % 2) { for (size_t i = 0; i < grid.size(); ++i) for (size_t j = 0; j < grid[i].size(); ++j) grid[i][j] = 'O'; return grid; } else if ((n + 1) % 4 == 0) n = 3; el..
-
[hacker rank] The grid search알고리즘/Hacker Rank 2021. 9. 10. 10:41
문제 링크 풀이 그리드 배열에서 패턴 배열의 첫 번째 요소과 일치하는 문자열의 위치를 찾을 때마다 나머지 패턴을 비교했습니다. 패턴 배열의 첫 번째 요소와 일치하는 그리드 배열의 행의 위치가 패턴 배열의 크기보다 작으면 탐색을 멈춥니다. 탐색을 멈출 때까지 return이 이뤄지지 않았다면 그리드 배열에서 패턴을 찾지 못한 것입니다. 코드 string gridSearch(vector G, vector P) { for (size_t i = 0; i G.size() - P.size()) break; size_t col = 0; while (true) { col = G[i].find(P[0], col); if (string::npos == col) break; e..
-
[hacker rank] The time in words알고리즘/Hacker Rank 2021. 9. 9. 22:29
문제 링크 코드 string timeInWords(int h, int m) { std::string time[] = { "o' clock", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "tweleve", "thirteen", "fourteen", "quarter", "sixteen", "seventeen", "eighteen", "nineteen", "twenty" }; const int size = 40; char buf[size] = {}; if (0 == m) snprintf(buf, size, "%s %s", time[h].c_str(), time[m].c_str()); else i..