이왕 발 디딘 이승, 원없이 즐겨야하지 않겠소?

구현의 두번째, 이동 알고리즘이다. 내가 생각하기엔 이동 알고리즘부터 본격적인 구현의 내용이라 생각한다. 이동 알고리즘의 최종적인 목표는 2차원 or 3차원 상의 좌표에서, 1명 or n명의 이동을 코드로 나타내는 것이다. 1. 이동 알고리즘 1-1. 1차원 이동 아래와 같은 맵에서 사람이 오른쪽으로 이동하는 모습을 코드로 구현하면 어떻게 해야할까? 일단 맵을 표현하는 방법은 여러가지가 있지만, 이 게시물에서는 1차원, 2차원 맵 모두 배열로 표현했다. int arr[6] = { 1, 0, 0, 0, 0, 0 }; Colored by Color Scripter 위 코드처럼 사람이 있는 곳을 1, 사람이 없는 곳을 0이라 표시했다. arr[0] = 0; arr[1] = 1; 사람을 오른쪽으로 이동시키기 위..

Study/Algorithm 2022. 3. 21. 01:40

이번 게시물에서는 구현의 첫번째인 회전 알고리즘에 대해 작성해보려 한다. 사실 회전 알고리즘은 너무 간단한 내용이라 게시물로 따로 정리할까 말까 고민하기도 했다..... 체계적으로 정리하기에 간단한 내용이라도 나눠서 정리하는게 낫다 생각해서 '회전 알고리즘'에 대해 따로 정리하기로 했다. 1. 회전 알고리즘 회전 알고리즘은 말 그대로 '회전'에 대한 내용이다. 코딩테스트에서 아래와 같은 회전판이 나온다면 코드로 어떻게 구현할지에 대한 내용이다. 여러가지 방법이 있겠지만, 이 게시물에서는 1차원 배열로 나타내는 방법을 작성하려 한다. 1 int arr[4] = { 1, 2, 3, 4 }; cs 1차원 배열로 나타내면 단순하게 다음과 같이 나타낼 수 있다. 처음에 말했던 것처럼 진짜 엄청 쉽다...... 그..

Study/Algorithm 2022. 3. 21. 01:36

이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다. 동적계획법을 기반으로 구현되는 알고리즘이다. 위키백과의 정의를 보자. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. 정의를 보다시피 최단 경로를 찾기에 좋은 알고리즘이다. 시간복잡도는 3개의 반복문을 통해 O(n^3) 이다. 플로이드 알고리즘은 3개의 반복문이면 구현된다. 코드를 보면 굉장히 짧고 간단하다. for (int k = 0;..

Study/Algorithm 2022. 3. 19. 23:16

이 글은 합병정렬(merge sort) 또는 머지소트 라고 불리는 정렬 알고리즘을 다룬다. 누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다. 빠른 정렬에 분류되고 퀵정렬과 많이 언급되는 정렬이다. 이유는 분할 정복 방식을 따르기 때문이다. 퀵 정렬 - http://mygumi.tistory.com/308 1. 합병정렬이란 무엇인가? 2. 합병정렬은 어떻게 구현하는가? 3. 합병정렬의 유용한 예는 언제인가? 합병정렬은 분할 정복 방법을 통해 구현된다. 분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다. (* 이전 글에서 다룬 퀵정렬도 분할 정복 방식을 가진다.) 시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다. 또한 안정 정렬로 속한다. (안정 정렬의 의미를 모..

Study/Algorithm 2022. 3. 19. 23:15

이 글은 힙 정렬(heap sort), 힙 소트 라고 불리는 정렬 알고리즘을 다룬다. 누구나 한번쯤은 들어봤고, 구현해본 정렬 중 하나이다. 빠른 정렬에 분류되고, 시간복잡도가 같은 퀵정렬과 합병정렬과 함께 언급된다. 퀵정렬 - http://mygumi.tistory.com/308 합병정렬 - http://mygumi.tistory.com/309 참고 링크 - https://www.geeksforgeeks.org/heap-sort/ 1. 힙 정렬이란 무엇인가? 2. 힙 정렬은 어떻게 구현하는가? 3. 힙 정렬은 어디에서 사용하는가? 힙 정렬은 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다. 완전 이진 트리는 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 말한다. 힙..

Study/Algorithm 2022. 3. 19. 23:13

DFS (깊이 우선 탐색) 소개 Root Node 혹은 다른 임의의 노드에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. Stack과 재귀함수(Recursion)으로 구현한다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 사용용도 경로찾기 u, v가 주어졌을 때 u -> v로 가는 경로를 찾을 때 그래프의 사이클을 찾을 때 back edge 즉, 순환을 만들어 주는 마지막 edge를 찾는다. 시간복잡도 두 가지의 자료구조(인접 리스트, 인접 행렬)로 구현할 수 있다. 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V)..

Study/Algorithm 2022. 3. 19. 23:12

BFS (너비 우선 검색) 정리 소개 Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다. Queue를 사용해서 구현한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) class Graph { private int V; private LinkedList adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i

Study/Algorithm 2022. 3. 19. 23:11

백준 온라인 저지 1992번 '쿼드트리' Java 알고리즘 문제풀이 풀이 이 문제는 분할정복(Divide and Conquer)로 풀면된다. 분할정복 사실은 정말 쉬운 개념이다. 복잡한 문제를 해결할 수 있는 작은 단위로 나누어 처리하고 이것을 합치면 된다. 이 문제를 풀면 백준 1780번 문제 종이의 개수도 아주 쉽게 풀 수 있을 것이다. (유사한 문제 풀기 -> 백준 1780번 문제종이 https://developer-mac.tistory.com/38) 그리고 쿼드트리는 단순히 노드가 4개 있는 것이라고 생각하면 된다. 즉, 4개로 쪼개서 4개의 노드가 생겨난다고 생각하면 된다. 먼저 입력을 받은 후 divide 함수에서 재귀적으로 동작하고 if 문을 두어 모든 원소가 0이거나 1일때 빠져나오게 하면..

Study/Algorithm 2022. 3. 19. 23:10