알고리즘 (20) 썸네일형 리스트형 [ 알고리즘 ] 시간 복잡도 구하는 법 시간 복잡도에 대해서 많이 들어보셨을텐데요. 이 시간 복잡도를 구하는 방법을 알아보겠습니다. 시간 복잡도란? 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다. - 위키피디아- 시간 복잡도의 종류에는 크게 3가지가 있습니다. => O(Big-O), Ω(Omega), Θ(Theta) 보통은 Big-O 표기법을 사용하여 시간 복잡도를 나타내기 때문에 Big-O 표기법만 다뤄보겠습니다. ( 더 궁금하신 분들은 검색을,,) 코드를 예시로 하여 좀 더 알아보겠습니다. int sum = 0; for(int i =0; i [ 알고리즘 / Kotlin ] 이진 탐색(Binary Search) 알고리즘 이진 탐색 알고리즘은 배열 내부에서 특정한 값을 찾아내는 알고리즘입니다. 이진 탐색 알고리즘의 과정부터 설명하겠습니다. 1) 배열의 중간에 있는 값을 선택하여 찾고자 하는 값 x와 비교 2) x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, 3) x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색 4) 값을 찾을 때까지 2번 3번 반복 즉 , 이진 탐색 알고리즘은 정렬되어있는 배열에서 사용해야합니다.( 크기로 비교하기 때문이죠) 예시를 들어볼게요 1 2 4 6 9 10 11 19 이러한 배열이 있다고 했을 때, 4라는 값을 찾는 과정입니다. 1) 먼저 이 배열의 중간값은 6입니다. 배열의 끝점의 인덱스가 7이므로 그의 중간은 3.5에서 소수점을 버리기 때문이죠. 2) 4 hig.. [ 알고리즘 / Kotlin ] 위상 정렬 알고리즘 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 백준에 나와있는 문제로 예시를 들겠습니다! www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한.. [ 알고리즘 / Kotlin] 플로이드 와샬(Floyd Warshall) 알고리즘 플로이드 와샬 알고리즘은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구할 때 사용하는 알고리즘입니다! 흔히들 알고 있는 최단 경로 알고리즘인 다익스트라 알고리즘에서는 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 특징이 있습니다. 이러한 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 의거합니다! 모든 경로에 대해 최솟값으로 갱신해주거든여!! package floydwarshall import kotlin.math.min private lateinit var arr: Array private const val INF = 1000000000 private fun main() { arr = arrayOf( in.. [ 알고리즘 / Kotlin ] 백준 17144 미세먼지 안녕! 안녕하세요 gyub(귭)입니다 ㅎㅎㅎ 이번 문제는 미세먼지 안녕!!!!입니다 www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을.. [ 알고리즘 / Kotlin ] 백준 3190 뱀 안녕하세요 gyub(귭)입니다 ㅎㅎㅎ 이번에 풀어본 문제는 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 입니다! 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀.. [ 알고리즘 / Kotlin ] 백준 15686 치킨 배달 안녕하세요 gyub(귭)입니다 ㅎㅎㅎ https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨 배달 문제입니다!! 브루트 포스 문제이져ㅎ 전 백트래킹을 사용했습니다 문제를 간단하게 요약하면 이렇습니다. 주어진 치킨 집들 중 m개의 치킨 집과 모든 집의 거리의 최솟값을 구하는 문제입니다. 문제 내용 자체가 그리 어렵지 않으니 이렇게만 요약하고 넘어가겠습니다 (^~^) 접근 방법 치킨 집들 중 중복 없이 m개를 뽑은 후 각 집들과.. [ 알고리즘 / Kotlin ] 백준 2688 줄어들지 않아 안녕하세요 gyub(귭)입니다 ㅎㅎㅎ https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 문제 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다. 예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, www.acmicpc.net dp를 이용해서 푸는 문제인데요! 다소 쉬운편에 속하는 문제 같아요 왜냐면 제가 진짜 dp를 못 풀어서 요즘 한창 dp만 풀고 있는데 이 문제는 비교적 수월하게 풀렸기 때문이죱 ㅎㅎ 갠적인 생각입니다 먼저 이 문제를 간단하게 요약하면 각 테스트 케이스마다 자릿수가 주어지고 그 자릿수에 해당하는 '줄어들지 않는 수'의 개수를 구하는 문제에요 '줄어.. 이전 1 2 3 다음
