13537번: 수열과 쿼리 1 문제 링크: 13537번: 수열과 쿼리 1 개요 배열 크기 n과 쿼리의 수 m이 최대 100,000이므로 각 구간에서 k보다 큰 값을 찾을 때마다 구간을 전부 탐색하면 시간복잡도가 O(n×m)이 되어 시간 초과와 맞닥뜨리게 될 것이다. 세그먼트 트리의 각 노드에 자신과 자식 노드의 모든 원소를 정렬한 vector...
[백준 14438번] 수열과 쿼리 17 [C++]
14438번: 수열과 쿼리 17 문제 링크: 14438번: 수열과 쿼리 17 개요 배열 크기 n과 쿼리의 수 m이 최대 100,000이므로 매 구간 최솟값을 출력할 때마다 구간을 전부 탐색하는 시간복잡도 O(n×m)의 방식으로는 시간 초과와 마주할 수밖에 없다. 각 구간의 최솟값을 세그먼트 트리에 저장하여 사용해야 한다. 세그먼트 트리의 개념...
[백준 4342번] 유클리드 게임 [C++]
4342번: 유클리드 게임 문제 링크: 4342번: 유클리드 게임 개요 매 턴 큰 수에서 작은 수의 배수를 빼서 큰 수를 0으로 먼저 만드는 사람이 이기는 게임 이론 문제이다. 두 플레이어가 최적의 방법으로 게임을 하므로, 이번 턴에 만들 수 있는 상황 중 다음 턴에 그 상황에 처한 상대방이 질 수밖에 없는 경우가 하나라도 있으면 이번 턴의 ...
[백준 1774번] 우주신과의 교감 [C++]
1774번: 우주신과의 교감 문제 링크: 1774번: 우주신과의 교감 개요 최소 스패닝 트리(Minimum Spanning Tree, MST)는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 다시 말하면 n개 노드가 있을 때, n-1개 간선만을 이용해 가장 적은 가중치로 모든 노드를 ...
[백준 11438번] LCA 2 [C++]
11438번: LCA 2 문제 링크: 11438번: LCA 2 개요 최소 공통 조상(Lowest common ancestor, LCA)는 트리에 어떤 두 정점 u와 v가 있을 때, u 자신이거나 u의 조상인 동시에 v 자신이거나 v의 조상인 노드들 중 가장 깊은 노드이다. LCA 알고리즘의 기본 흐름은 다음과 같다. 두 정점 중 깊이가...
[Unity] 객체 지향과 유니티 기초 개념
객체 지향의 개념 객체 지향이란 프로그래밍 패러다임 중 하나이다. 기존에는 프로그램을 명령어의 모음으로 인식했으며, 명령어의 순서에 초점을 맞춘 절차지향 프로그래밍이 사용되었다. 그러나 객체지향은 프로그램을 독립된 단위인 객체들과, 각 객체들 간의 상호작용에 초점을 맞춘다. 클래스 클래스는 객체 지향 프로그래밍에서 객체의 상태를 나타내는 멤버 변수와...
[백준 10159번] 저울 [C언어]
10159번: 저울 문제 링크: 10159번: 저울 개요 어떤 정점에서 다른 정점으로 가는 최단경로를 알고 싶을 때 사용하는 알고리즘은 대표적으로 다익스트라(Dijkstra) 알고리즘과 플로이드 와샬(Floyd–Warshall) 알고리즘이 있다. 플로이드 와샬 알고리즘은 3중 반복문을 사용하기 때문에 우선순위 큐를 사용하지 않는 다익스트라 ...
[백준 17822번] 원판 돌리기 [C언어]
17822번: 원판 돌리기 문제 링크: 17822번: 원판 돌리기 개요 시키는 대로 구현만 잘 하면 되는 시뮬레이션 문제이다. n(원판의 개수), m(한 원판 안의 숫자 개수), k(원판 회전 횟수)가 최대 50으로 작기 때문에 회전을 직접 이동시켜서 구현해도 시간초과가 발생하지 않을 듯 하지만(*진위여부 파악 필요) 나는 원판을 회전시키지...
[백준 2143번] 두 배열의 합 [C언어]
2143번: 두 배열의 합 문제 링크: 2143번: 두 배열의 합 전체 코드 #include <stdio.h> #include <stdlib.h> #pragma warning(disable:4996) #pragma warning(disable:6031) #define MAX_LEN 1000 int cmp(cons...
[CS] 여러가지 정렬 알고리즘
빅오 표기법 빅오 표기법((big-O notation)은 점근표기법 중 하나로, 알고리즘의 성능을 상한선을 기준으로 하여 수학적으로 표기하는 방법이다. 알고리즘의 시간 복잡도(시간 효율성)과 공간 복잡도(메모리 공간 효율성)를 나타낼 수 있다. 여기서 알고리즘의 시간 복잡도는 실제 알고리즘의 러닝타임을 의미하는 것이 아닌, 데이터나 사용자 수의 증가...