알고리즘
-
공원 산책알고리즘/프로그래머스 2023. 5. 11. 10:38
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/172928 해설 이차원 배열로 공원 맵을 만들면 편하게 작업할 수 있다. 공원의 길이가 가로, 세로 각각 50이기 때문에 O(N^2)의 시간복잡도를 가져도 괜찮다. 코드 class Solution { public int[] solution(String[] park, String[] routes) { int[] startPoint = new int[2]; int height = park.length; int width = park[0].length(); char[][] parkMap = new char[park.length][park[0].length()]; for (int i = 0; i ..
-
추억 점수알고리즘/프로그래머스 2023. 5. 11. 10:32
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/176963 해설 길이가 많이 길지 않으므로 O(N^2)로 편하게 풀면 된다 코드 import java.util.*; class Solution { public int[] solution(String[] name, int[] yearning, String[][] photo) { Map nameYearingMap = new HashMap(); int size = name.length; for (int i = 0; i < size; ++i) { nameYearingMap.put(name[i], yearning[i]); } List answer = new ArrayList(); for (int i..
-
[Java] 달리기 경주알고리즘/프로그래머스 2023. 5. 3. 12:04
문제 링크 callings의 길이가 최대 1,000,000개이므로 이중 반복문을 사용해서 시간 복잡도가 O(N^2)이 나오도록 작업하면 시간 초과가 뜹니다. class Solution { public String[] solution(String[] players, String[] callings) { for (int i = 0; i < callings.length; ++i) { for (int j = 0; j < players.length; ++j) { if (callings[i].equals(players[j])) { String temp = players[j - 1]; players[j - 1] = players[j]; players[j] = temp; break; } } } return player..
-
[백준] 구간 합 구하기(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..