3109번: 빵집 문제 링크: 3109번: 빵집 개요 n*m 크기의 맵이 주어지면 왼쪽부터 오른쪽까지 연결하는 파이프라인을 겹치지 않게 설치할 수 있는 최대 개수를 구하는 문제이다. 최대한 많은 파이프라인을 만들어야 하기 때문에 왼쪽 가장 위 칸에서부터 시작하며, 오른쪽으로 파이프를 연결할 때는 위, 중간, 아래 순으로 진행한다. 풀이 ...
[백준 1517번] 버블 소트 [C++]
1517번: 버블 소트 문제 링크: 1517번: 버블 소트 개요 주어진 수열에 대해 버블 소트를 수행하여 오름차순으로 정렬할 때 발생하는 Swap의 횟수, 즉 각 원소의 자리 변화의 총 횟수를 구하는 문제이다. n의 범위가 (1 ≤ n ≤ 500,000)이기 대문에 정직하게 버블 소트를 진행하며 Swap의 횟수를 세면 시간복잡도가 O(n^2)...
[백준 13537번] 수열과 쿼리 1 [C++]
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으로 작기 때문에 회전을 직접 이동시켜서 구현해도 시간초과가 발생하지 않을 듯 하지만(*진위여부 파악 필요) 나는 원판을 회전시키지...