728x90

알고리즘 31
[알고리즘]백준 1238: 파티

다익스트라 알고리즘최단경로 → 다익스트라(Dijkstra) 알고리즘다익스트라 알고리즘은 한 정점에서 각 정점까지의 최단경로를 찾는 알고리즘으로 우선순위큐를 사용하는 경우 O(MlogN)의 시간복잡도를 가진다.(이때, N: 정점의 개수, M: 간선의 개수)  로직초기화시작 정점까지의 거리는 0으로 초기화후, 우선순위 큐에 넣음시작 정점 외의 다른 정점까지의 거리를 무한대로 초기화(dist 배열)인접한 정점의 거리 update우선순위큐에서 정점을 뽑아, 현재 정점으로 설정현재 정점에서 인접한 정점까지의 거리 update(시작 정점 → 인접한 정점까지의 거리보다 현재 정점을 거쳐서 가는 경우가 더 빠르다면, dist 배열을 초기화하고 우선순위큐에 넣음)우선순위큐가 빌때까지 2번을 반복 코드import java..
알고리즘/백준 2024.06.23

[알고리즘]백준 10986: 나머지 합

처음에는 슬라이딩 윈도우 기법으로 풀었으나 이 경우 시간복잡도가 O(N^2)으로 N의 최대값이 10^6이기 때문에 시간초과가 발생했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int N,M; static int[] numbers; static int answer; public static void main(String[] args) throws IOException { BufferedReader br = ..
알고리즘/백준 2024.06.19

[알고리즘]최소신장트리: kruskal,prim알고리즘 - Java로 구현하기

📖최소신장트리 최소신장트리란 1)모든 정점을 포함하면서 2)간선의 가중치 합이 최소인 트리를 말한다. 최소신장트리를 찾는 알고리즘 중 대표적으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. 🔍Kruskal 알고리즘 간선 중심 → edgeList가 필요 1. 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 2. 가중치가 낮은 간선부터 선택하면서 트리를 증가시킨다. 이때, 사이클이 존재하면 남아 있는 간선 중 그 다음으로 가중치가 낮은 선택 =>N-1개의 간선이 선택될 때까지 2반복 *서로소 집합(Disjoint-set)을 이용한 Kruskal 알고리즘의 구현 서로소 집합(Disjoint-set)은 중복 포함된 원소가 없는 집합을 의미한다. import java.io.BufferedReader; ..
알고리즘 2024.02.24

[알고리즘]순열, 조합, 부분집합 - Java로 구현하기

📖순열, 조합, 부분집합 1. 순열(Permutation) : 순서에 따라 배열된 원소들의 모든 가능한 조합(순서 O, 중복 X) - 주어진 원소들을 나열하는 경우의 수 계산 2. 조합(Combination) : 순서에 상관없이 선택된 원소들의 모든 가능한 조합(순서X, 중복X) - 주어진 원소들을 뽑는 경우의 수 계산 3. 부분집합(Subset) : 어떤 집합의 일부 원소로 이루어진 집합 - 주어진 집합의 모든 부분집합 계산 🔍순열 구현 1. 중복원소를 boolean 배열을 이용해서 확인 import java.util.Arrays; // 중복 원소를 배열을 이용해서 체크하기 // 9P9 : 0.01 (안전) // 10P10 : 0.1초 컷(약간 위험) public class PermutationTest..
알고리즘 2024.02.24

B12460. 구슬탈출2

13460번: 구슬 탈출 2 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 최단거리⇒bfs(⇒Queue) Queue에 원소가 없다면 종료 Queue의 원소가 있다면? 종료조건 확인 꺼내서 구슬을 움직임(구현) 큐에 다음 수행 추가 python from collections import deque N,M=map(int, input().split(" ")) board=[] for i in range(N): board.append([]) string = input(..
알고리즘/백준 2024.02.04

[알고리즘]동적 계획법

1.동적계획법(Dynamic Programming, DP) 전체 문제를 작은 부분 문제로 나누어 해결하는 방법 동적계획법의 대표적인 예인 피보나치 수열을 통해 개념을 살짝 이해해보자. 피보나치 수열은 다음과 같다. 1,1,2,3,5,8,13,21,... 다음과 같이 N번째 값은 N-1번째 값과 N-2번째 값이 더해져서 만들어진다는 규칙이 있다. 그럼 이것을 점화식으로 표현해보면 F(N)=F(N-1)+F(N-2)와 같다. def fibo(n): if n==1: return 1 elif n==2: return 1 else: return fibo(n-2)+fibo(n-1) 위 코드대로 실행해보면 성공적으로 피보나치 수열이 구해지는 것을 볼 수 있다. 근데 문제점이 있다. 매개변수의 값이 너무 커지면 실행시간이..
알고리즘 2021.01.18
1 2 3 4
더보기
728x90

티스토리툴바