개발🐶🐾노트

본문 바로가기

전체 글

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

[책 정리] 객체 지향의 사실과 오해 http://www.yes24.com/Product/Goods/18249021 객체 지향의 사실과 오해를 읽고 나름대로 정리했는데, 막상 정리하려고 보니 굉장히 어려웠다... 메모하면서 책을 읽는 방식으로 해봐야 할 것 같다. 학교에서 배웠던 객체지향과 비교하면서 책을 읽으니까 더 재밌고 쉽게 읽었던 것 같고, 사람들이 말하는 TDD와 DDD가 왜 중요한지를 알게된 계기가 되었다. 개념 1. “객체지향이란 실세계를 직접적이고 직관적으로 모델링할 수 있는 패러다임” 이라는 설명은 객체지향의 기반을 이루는 철학적인 개념을 설명하는데는 적합하지만 유연하고 실용적인 관점에서 설명하기에는 적합하지않다. 실제 객체지향의 목표 = 새로운 세계를 창조하는 것이다. 객체지향에서 가장 중요한 3가지 개념 = 협력, 역할,.. 더보기

[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개의 포인터를 조작해가면서 원하는 것을 얻는 알고리즘이다. 이러한 특성 때문에 투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 문제에 적용시킬 수 있다. 투 포인터로 해결해야.. 더보기

[Algorithm/Java][백준] 1806번 부분합 [BOJ] 1806번 부분합 https://www.acmicpc.net/problem/1806 문제 접근 투 포인터를 이용해서 문제를 풀었다. deque와 이분 탐색을 이용해서도 풀 수 있다고 하는데 분류가 투 포인터라서 투 포인터를 사용해서 풀었다. start와 end인 두 개의 인덱스를 사용하고 sum이 t(목표 값)보다 작거나 같으면 end를 +1해서 한개를 더 더하도록 하고, sum이 t(목표 값)보다 크면 start를 +1 해서 합에서 한개를 빼서 목표 값에 접근하도록 한다. 투 포인터를 사용하게 되면 O(N)으로 문제를 해결할 수 있게 되는 장점이 있다. Code import java.io.BufferedReader; import java.io.IOException; import java.io.. 더보기

[Algorithm/Java][백준] 1700번 멀티탭 스케줄링 [BOJ] 1700번 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 문제 접근 예전에 운영체제 시간에 배웠던 페이지 교체 알고리즘과 비슷해서 쉽게 풀 수 있었다. 멀티탭에 자리가 있거나, 이미 꽂혀있을 때는 고려할 것 없이 그냥 꽂거나 넘어가면 되지만 자리가 없을때 고려해야 될 경우의 수가 있다. 경우의 수를 정리해 보면 다음과 같다. 멀티탭에 자리가 있는 경우 이미 멀티탭에 꽂혀 있는 경우 멀티탭에 자리가 없는 경우 3.1. 사용하지 않을 전자기기가 꽂혀 있는 경우 3.2. 모든 전자기기가 다시 사용할 전자기기인 경우 사용하지 않을 전자기기가 꽂혀 있으면 그 전자기기를 제거하고 새로운 전자기기를 꽂으면 해결된다. 모든 전자기기가 다시 사용할 전자기기인 경우 우선순위를.. 더보기

이전 1 2 3 4 5 ··· 13 다음

티스토리툴바