알고리즘
-
Swift /** https://www.acmicpc.net/problem/1260 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄..
DFS와 BFSSwift /** https://www.acmicpc.net/problem/1260 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄..
2023.11.09 -
Swift import Foundation extension Array where Element: Comparable { private mutating func partition(_ left: Int, _ right: Int) -> Int { var low = left var high = right + 1 let pivot = self[left] print("partition(\(left), \(right))") repeat { repeat { low += 1 } while low = left && self[high] > pivot print("low: \(low), high: \(high)") if low < high { swapAt(low, high) print("swapAt(\(low), \(hig..
퀵소트Swift import Foundation extension Array where Element: Comparable { private mutating func partition(_ left: Int, _ right: Int) -> Int { var low = left var high = right + 1 let pivot = self[left] print("partition(\(left), \(right))") repeat { repeat { low += 1 } while low = left && self[high] > pivot print("low: \(low), high: \(high)") if low < high { swapAt(low, high) print("swapAt(\(low), \(hig..
2023.08.03 -
Swift // https://school.programmers.co.kr/learn/courses/30/lessons/49189 import Foundation func bfs(n: Int, graph: [Int: [Int: Int]], beginnigNode: Int, visit: (_ node: Int, _ distance: Int) -> Void) { var queue = [(Int, Int)]() var visited = [Bool](repeating: false, count: n) queue.append((beginnigNode, 0)) visited[beginnigNode - 1] = true while !queue.isEmpty { let (visitingNode, distance) = q..
BFSSwift // https://school.programmers.co.kr/learn/courses/30/lessons/49189 import Foundation func bfs(n: Int, graph: [Int: [Int: Int]], beginnigNode: Int, visit: (_ node: Int, _ distance: Int) -> Void) { var queue = [(Int, Int)]() var visited = [Bool](repeating: false, count: n) queue.append((beginnigNode, 0)) visited[beginnigNode - 1] = true while !queue.isEmpty { let (visitingNode, distance) = q..
2023.08.03 -
C++ #include #include #include #include using namespace std; typedef struct Edge { int to, w; } Edge; typedef struct Node { int no, dist; bool operator n.dist; } } Node; vector edge[4001]; bool visited[4001]; int dist[4001]; priority_queue to_visit; int main() { int N, M; scanf("%d%d", &N, &M); for (int i = 0; i < M; i++) { int A, B, C; scanf("%d%d%d", &A, &..
다익스트라C++ #include #include #include #include using namespace std; typedef struct Edge { int to, w; } Edge; typedef struct Node { int no, dist; bool operator n.dist; } } Node; vector edge[4001]; bool visited[4001]; int dist[4001]; priority_queue to_visit; int main() { int N, M; scanf("%d%d", &N, &M); for (int i = 0; i < M; i++) { int A, B, C; scanf("%d%d%d", &A, &..
2019.06.20 -
C++ #include #include #include using namespace std; typedef struct Edge_t Edge; struct Edge_t { int from, to, weight; bool operator s[J]) { r[J] = I; } else if ..
최소 스패닝 트리C++ #include #include #include using namespace std; typedef struct Edge_t Edge; struct Edge_t { int from, to, weight; bool operator s[J]) { r[J] = I; } else if ..
2019.06.20 -
C++ #include #include #define MINIMUM_POWER_OF_2_GREATER_THAN_MAXIMUM_N 131072 int T[MINIMUM_POWER_OF_2_GREATER_THAN_MAXIMUM_N*2]; int M = 1; void init(int N) { while (M 0) { T[index] += delta; index /= 2; } } int sum(int left, int right) { left = left + M - 1; right = right + M - 1; int sum = 0; while (..
인덱스 트리C++ #include #include #define MINIMUM_POWER_OF_2_GREATER_THAN_MAXIMUM_N 131072 int T[MINIMUM_POWER_OF_2_GREATER_THAN_MAXIMUM_N*2]; int M = 1; void init(int N) { while (M 0) { T[index] += delta; index /= 2; } } int sum(int left, int right) { left = left + M - 1; right = right + M - 1; int sum = 0; while (..
2019.06.20 -
스택 C++ int stack[MAX_SIZE]; int stack_size; void stack_init() { stack_size = 0; } bool stack_push(int val) { if (stack_size == MAX_SIZE) return false; stack[stack_size++] = val; return true; } int stack_pop() { return stack[--stack_size]; } bool stack_empty() { return stack_size == 0; } Swift struct Stack { private var storage = Array() var stackPointer: Int { storage.count } mutating func push(..
스택, 큐, 데큐, 힙스택 C++ int stack[MAX_SIZE]; int stack_size; void stack_init() { stack_size = 0; } bool stack_push(int val) { if (stack_size == MAX_SIZE) return false; stack[stack_size++] = val; return true; } int stack_pop() { return stack[--stack_size]; } bool stack_empty() { return stack_size == 0; } Swift struct Stack { private var storage = Array() var stackPointer: Int { storage.count } mutating func push(..
2019.06.20 -
입력 C/C++ #include int N; scanf("%d", &N); int A[1003]; for (int i = 0; i < N; i ++) { scanf("%d", A+i); } Java import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 한 줄에 정수 하나가 주어지는 경우 int N = Integer.parseInt(br.readLine()); // 한 줄에 정수 N개가 공백으로 분리되어 주어지는 경우 int[] A = new int..
빠른 입출력입력 C/C++ #include int N; scanf("%d", &N); int A[1003]; for (int i = 0; i < N; i ++) { scanf("%d", A+i); } Java import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 한 줄에 정수 하나가 주어지는 경우 int N = Integer.parseInt(br.readLine()); // 한 줄에 정수 N개가 공백으로 분리되어 주어지는 경우 int[] A = new int..
2019.06.20 -
덧셈, 뺄셈, 대입 연산은 상수시간이 걸리며 이를 O(1)라고 표현한다. 입력 데이터의 수 N에 대한 연산량을 계산한 수식의 최고차항만 취하여 표현한다. O(1) < O(ln N) < O(N) < O(N ln N) < O(N²) < O(N³) ln : 밑이 2인 log 실행환경에 따라 차이가 있지만 보수적으로 계산했을 때 1000만 건 정도의 연산이면 1초안에 결과가 나온다고 알려져 있다. 더 자세한 내용은 여기를 참조하세요.
복잡도 계산덧셈, 뺄셈, 대입 연산은 상수시간이 걸리며 이를 O(1)라고 표현한다. 입력 데이터의 수 N에 대한 연산량을 계산한 수식의 최고차항만 취하여 표현한다. O(1) < O(ln N) < O(N) < O(N ln N) < O(N²) < O(N³) ln : 밑이 2인 log 실행환경에 따라 차이가 있지만 보수적으로 계산했을 때 1000만 건 정도의 연산이면 1초안에 결과가 나온다고 알려져 있다. 더 자세한 내용은 여기를 참조하세요.
2019.06.20