알고리즘

[프로그래머스] 2023 KAKAO BLIND RECRUITMENT - 이모티콘 할인행사 (자바 Java)

[unrated] 이모티콘 할인행사 - 150368 문제 링크 성능 요약 메모리: 72.9 MB, 시간: 0.04 ms 구분 코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT 채점결과 정확성: 100.0 합계: 100.0 / 100.0 문제 설명 카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다. 이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것. 이모티콘 판매액을 최대한 늘리는 것. 1번 목표가 우선이며, 2번 목표가 그 다음입니다. 이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다. n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니..

[알고리즘] 플로이드-워샬 알고리즘

플로이드-워샬 알고리즘 모든 쌍 최단 경로 알고리즘: 모든 정점 쌍 사이의 최단 경로를 구하는 방법 단순 최단 경로 알고리즘 m개의 간선을 사용해서 i에서 j까지 이르는 최단거리 모든 정점 k에 대해 최대 m-1개의 간선을 사용해서 i에서 k까지 이르는 최단거리 $d_{ik}^{m-1}$에다가 $w_{kj}$를 더한 값을 구하고, 이 중 가장 짧은 것을 택함 for (i=1 to n) for (j=1 to n) d(i to j, k=0) = w[i][j]; for (m=2 to n-1) for (i=1 to n) for (j=1 to n) d(i to j, k=m) = min(d(i to k, k=m-1) + w[k][j]) 시간 복잡도: $\theta(n^4)$ 플로이드-워샬 $d_{ij}^{k}$ =..

[알고리즘] 위상 정렬 Topological Sort (자바 Java)

위상 정렬 사이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬 간선 (i, j)가 존재하면 정점 i는 반드시 j보다 앞에 위치 방식 1: 큐 활용 topologicalSort(G, V) { for i

[백준] 9370 - 미확인 도착지 (자바 Java)

[Gold II] 미확인 도착지 - 9370 문제 링크 성능 요약 메모리: 283148 KB, 시간: 1220 ms 분류 다익스트라(dijkstra), 그래프 이론(graphs) 문제 설명 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교..

[알고리즘] 유니온-파인드 (Union-Find) (자바 Java)

목차 유니온 파인드 (Union-Find) 서로소 집합(Disjoint-sets) 서로 중복 포함된 원소가 없는 집합들 → 교집합이 없다 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자(representative)라고 함 연산 Make-Set(x): 원소 x로만 구성된 집합을 만든다 Find-Set(x): 원소 x를 가진 집합을 알아낸다 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다 표현 방법 연결 리스트, 트리 1. 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표원소로 삼음 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 2. 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모노드를 ..

[SWEA] [모의 SW 역량테스트] 5656 - 벽돌 깨기 (자바 Java)

dfs와 bfs를 활용하여 문제를 풀었다. dfs는 벽돌 깨기를 진행하는 과정을, bfs는 특정 벽돌을 깨뜨렸을 때의 연쇄 작용을 구현하기 위해 사용했다. 벽돌 깨기의 경우 한 번 깬 벽돌의 column에 대해서도 다시 벽돌을 깰 수 있으니 방문 여부를 저장할 필요가 없다. // col에 따라 벽돌깨기 진행 for (int i = 0; i < W; i++) dfs(i, 0); dfs는 N번 진행하기 때문에 N이 되었을 때 남은 벽돌 수를 세어서 ans와 비교하였다. 그리고 세로줄 (column)에 대해 벽돌을 깨야 하니까 i열에 대해 map[r][i]가 0이 아닌 경우에 벽돌 깨기 (game)을 진행했다. static void dfs(int i, int depth) { if (depth == N) { i..

[백준] 1197 - 최소 스패닝 트리 (자바/Java)

[Gold IV] 최소 스패닝 트리 - 1197 문제 링크 성능 요약 메모리: 230420 KB, 시간: 1196 ms 분류 그래프 이론(graphs), 최소 스패닝 트리(mst) 문제 설명 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며,..

[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra), 벨만-포드 (Bellman-Ford) (자바/Java)

목차 최단 경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라 (dijkstra): 음의 가중치 허용x 벨만-포드(Bellman-Ford) : 음의 가중치 허용o 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 1. Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 탐욕 기법을 사용 - 프림 알고리즘과 유사 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재 이때 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지으 ㅣ최단 경로로 구성됨 s→t = s→x + x→t 시간복잡도 : O(ElogV) 과..

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) (자바/Java)

목차 최소 신장 트리 (MST) 신장트리: 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리 최소신장트리: 신장 트리 중에서 사용된 가중치의 합이 최소인 트리 특징 무방향 가중치 그래프 그래프의 가중치 합이 최소여야 한다 N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선을 사용 사이클을 포함하면 안된다. 크루스칼 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 올므차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 (사이클 존재: 대표가 같으면 사이클(Find-Set)) n-1개의 간선이 선택될 때까지 2)를 반복 Kruskal(G) { A

[알고리즘] 최장 공통 부분 수열 (Longest Common Subsequence LCS)

목차 LCS (Longest Common Subsequence) 최장 공통 부분 수열 LCS의 길이 찾기 $$ x_m = y_n 이면 LCS(X_m, Y_n) = LCS(X_{m-1}, Y_{n-1})+1 $$ $$ x_m \neq y_n 이면 LCS(X_m, Y_n) = max(LCS(X_{m-1}, Y_{n}), LCS(X_{m}, Y_{n-1})) $$ https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence 문제 예시 9251번: LCS C[i-1][j] = A의 i-1번째, B의 j번째까지의 LCS Xi와 Yj가 같지 않다면 새로운 값을 추가할 수 없으니, 이전의 LC..