'Algorithm' 카테고리의 글 목록

본문 바로가기

Algorithm

[Algorithm/Java][백준] 2775번 부녀회장이 될테야 [BOJ] 2775번 부녀회장이 될테야 https://www.acmicpc.net/problem/2775 문제 접근 백준에서 에제로 준 입력과 출력을 하나씩 쓰다보면 규칙이 보이게 된다. 000 -> 0 001 -> 1 002 -> 2 003 -> 3 100 -> 0 101 -> 1 102 -> 3 103 -> 6 200 -> 0 201 -> 1 202 -> 4 203 -> 10 이때 103호에는 003호와 102호를 합친 값이 있고, 203호에는 103호와 202호를 합친 값이 있다. 이를 점화식으로 바꿔보면 (k0n)호 = k-10n호 + k0n-1호 코드로 바꿔보면 dp[floor][room] = dp[foor-1][n] + dp[floor][n-1]이 된다. 이를 코드로 바꾸면 다음과 같다. Co.. 더보기

[Algorithm/Java][백준] 14226번 이모티콘 [BOJ] 14226번 이모티콘 https://www.acmicpc.net/problem/14226 문제 접근 화면에 있는 이모티콘을 S개 만드는 최소 시간을 구하는 문제이다. 화면에 있는 이모티콘 개수와 클립보드에 있는 이모티콘 개수 그리고 시간 정보를 저장할 수 있는 Emoticon 클래스를 만들고 isVisited 배열을 화면에 있는 이모티콘 수와 클립보드에 있는 이모티콘 수를 고려할 수 있도록 2차원 배열로 만들었다. 그리고 BFS를 이용해서 화면에 있는 이모티콘을 클립보드에 저장하는 경우, 화면에 있는 이모티콘 한개를 제거하는 경우, 클립보드에 있는 이모티콘을 붙여넣는 경우 세가지를 고려해서 문제를 해결했다. 문제를 보고 이차원 배열로 해결할 생각을 하지 못해서 푸는데 꽤나 오래걸렸다...근데 .. 더보기

[Algorithm/Java][백준] 2252번 줄 세우기 [BOJ] 2252번 줄 세우기 https://www.acmicpc.net/problem/2252 문제 접근 위상 정렬을 통해서 쉽게 푼 문제이다. 위상 정렬이란 순환이 없는 그래프에서 정점간의 순서를 구할 수 있는 알고리즘이다. 각각의 학생들을 정점이라고 생각하고, 입력으로 들어오는 순서들을 그래프들의 간선이라고 생각하면 쉽게 문제가 풀린다. 위상 정렬이란 우선 들어오는 간선의 개수를 세는 linkCnt의 값이 0인 정점들을 큐에 넣고, 하나씩 큐에서 빼면서 해당 정점과 연결된 정점들에 대해서 linkCnt를 -1 해주고 다시 linkCnt의 값이 0인 정점들을 큐에 넣는 방식으로 진행된다. Code import java.util.ArrayList; import java.util.LinkedList; .. 더보기

[알고리즘] 최소 스패닝 트리_ Kruskal & Prim 최소 스패닝 트리 (MST, Minimum Spanning Tree) 스패닝 트리란, 그래프에서 순환 없이 모든 정점을 잇는 부분 그래프를 의미한다. 최소 스패닝 트리란, 이러한 스패닝 트리 중에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 의미한다. 이러한 최소 스패닝 트리를 구하는 알고리즘으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있다. 크루스칼 (Kruskal) 알고리즘 크루스칼 알고리즘은 모든 간선 중에서 가장 가중치가 작은 간선부터 연결해 주면서 최소 스패닝 트리를 만드는 알고리즘이다. 간선들을 연결하면서 순환이 발생한다면 해당 간선을 버리고 다음 간선을 선택하게 되는데 이 때, Union-Find 연산을 사용한다. 알고리즘 간선들을 가중치를 기준으로 오름차순으로 정렬한다. .. 더보기

[Algorithm/Java][백준] 1197번 최소 스패닝 트리 [BOJ] 1197번 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 문제 접근 모든 정점을 최소 값으로 순회할 수 있는 트리를 구하는 문제이다. 대표적으로 Kruskal과 Prim 알고리즘이 있기 때문에 두 알고리즘을 이용해서 구현하였다. Code Kruskal 알고리즘 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Edge implements Comparable { int from; int to; int cost; public Edg.. 더보기

[알고리즘] 최단 경로 문제_다익스트라 & 벨만포드 다익스트라 & 벨만포드 이 두 알고리즘은 그래프에서 최단 경로 문제를 해결할 때 사용되는 알고리즘이다. 최단 경로 문제? 최단 경로란 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 최단 경로 문제를 푸는데 다양한 방법이 있지만, 다익스트라와 벨만포드를 정리해보려고 한다. 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 그래프에서 음의 가중치가 없을 때 최단 경로를 찾을 수 있다. V개의 정점과 양의 가중치를 가진 E개의 간선을 가진 그래프에서 출발 정점으로부터 모든 최단 경로를 찾을 수 있다. 알고리즘은 다음과 같이 진행된다. 현재 정점에 연결되어 있는 정점들을 모두 본다. 현재 정점과 연결되는 다음 정점으로의 거리와 시작 정점과 현재 정점까지의 최단 거.. 더보기

[Algorithm/Java][백준] 1916번 최소비용 구하기 [BOJ] 1916번 최소비용 구하기 https://www.acmicpc.net/problem/1916 문제 접근 양의 가중치를 가진 간선으로 이루어진 그래프에서 최단 경로를 찾는 문제여서 다익스트라와 벨만포드 알고리즘 2개를 모두 적용해서 구현했다. 다익스트라 알고리즘은 우선순위 큐를 이용해서 시간복잡도를 줄였고, 다익스트라와 벨만포드 알고리즘은 포스트에 정리했다. [알고리즘] 다익스트라 & 벨만포드 Code 다익스트라 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Node implements Comparable { int to; int .. 더보기

[알고리즘] 투 포인터 & 슬라이딩 윈도우 투 포인터 & 슬라이딩 윈도우 알고리즘 1차원 배열을 2회 이상 반복적으로 탐색을 해야할 경우 단순하게 한다면 O(N^2) 이상 시간 복잡도가 걸리지만 투 포인터와 슬라이딩 윈도우 알고리즘을 사용하게 된다면 부분 배열을 이용하여 시간 복잡도를 O(N)으로 줄일 수 있는 공통점이 있다. 투 포인터는 부분 배열의 길이가 변할 수 있지만, 슬라이딩 윈도우는 부분 배열의 길이가 고정적이라는 차이점이 있다. 투 포인터(Two Pointer) 투 포인터 알고리즘은 1차원 배열에서 각각 다른 원소를 가리키는 2개의 포인터를 조작해가면서 원하는 것을 얻는 알고리즘이다. 이러한 특성 때문에 투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 문제에 적용시킬 수 있다. 투 포인터로 해결해야.. 더보기

이전 1 2 3 4 ··· 9 다음

티스토리툴바