HJ's Devlog

오늘은 삼성 역량SW테스트의 뱀 문제를 풀었다. www.acmicpc.net/problem/3190 해당 문제는 2차원 배열의 특정 위치에서 동, 남, 서, 북의 위치로 이동하는 기능을 구현해야 한다. 또한 매 시점마다 뱀이 존재하는 위치를 항상 2차원 리스트에 기록해야 한다. 이러한 시뮬레이션 문제 유형은 문제에서 주어진 TC를 직접 그려보는 것이 이해하는 데 좋다. 풀이 시간은 40분으로 예전에 뱀 게임을 MFC로 경험해본 적이 있어서인지 문제 이해 자체는 수월했다. 이번 문제를 통해 새로 알게된 점을 정리해보았다. 파이썬 2차원 리스트 선언 예를 들어 전부 0으로 초기화된 N x N 리스트를 만들고자 한다. 기존에 내가 만들던 방식은 다음과 같았다. data = [] for i in range(n)..

위상 정렬은 정렬 알고리즘의 일종으로 '방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 위상 정렬 알고리즘을 살펴보기 전에 진입차수(Indegree)에 대해 알아야 한다. 진입차수란 특정한 노드로 "들어오는" 간선의 개수이다. 이제 위상 정렬의 알고리즘을 살펴보면 다음과 같다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. i) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 ii) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 큐가 빌 때까지 계속 큐에서 원소를 꺼내서 처리하는 과정을 반복한다. 만약 이때 모든 원소를 방..

신장 트리(Spanning Tree)는 그래프 알고리즘 문제로 자주 출제되는 유형으로, 신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리의 조건이기도 한다. 그리하여 이런 그래프를 신장 트리라고 부르는 것이다. [크루스칼 알고리즘] 문제 상황에서 가능한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. 신장 트리 중에서 최소 비용으로 만들 수 있는 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 한다. 대표적인 최소 신장 트리 알고리즘으로 크루스칼 알고리즘이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류되며 알고리즘은 다음과 같다. 1. 간선 데이터를 비용에 ..

코딩 테스트에서 출제 비중이 낮은 편이지만 제대로 알아야 하는 그래프 알고리즘들을 정리해보자 한다. 그래프에 대해 간단히 복습하고 넘어가면, 그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조이다. 알고리즘 문제에서 '서로 다른 개체(객체)가 연결되어 있다'라는 문장을 마주치면 그래프 알고리즘을 가장 먼저 떠올려야 하다. 또한 그래프 자료구조 중 트리 자료구조는 여려 알고리즘에서 사용되므로 꼭 기억해야 한다. 이전에 정리한 알고리즘 중 다익스트라 최단경로 알고리즘에서 우선순위 큐가 사용되었다. 우선순위 큐를 구현하기 위해선 최소 힙이나 최대 힙을 사용한다고 했는데 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다. 2021.03.22 - [프로..

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘으로 다양한 종류의 알고리즘 유형이 있는데 상황에 맞는 효율적인 알고리즘은 정립되어 있다. 그 중 코딩테스트에 자주 출제되는 다익스트라 최단 경로와 플로이드 워셜 알고리즘이 있는데 이에 대해 정리해봤다. [다익스트라 최단 경로 알고리즘] 다익스트라(Dijkstra) 최단경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 음의 간선(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다..

다이나믹 프로그래밍은 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법이다. 다만 항상 사용할 수 있는 것은 아니며, 다음 조건을 만족할 때 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션(Memoization)은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 말한다. 메모이제이션은 값을 저장하는 방법이기에 캐싱(Caching)이라고도 한다. 구현 방법은 한 번 구한 정보를 리스트에 저장하는 것이다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 예전에..

이진탐색에 대해 알아보기 전 기본 탐색 방법인 순차 탐색에 대해 먼저 알아둘 필요가 있다. 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법을 말한다. 따라서 데이터의 개수가 N개 일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색은 최악의 경우 시간 복잡도가 O(N)이다. 이진탐색(Binary Search)은 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 이미 정렬되어 있을 경우 매우 빠르게 데이터를 찾을 수 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 것으로 위치를 나타내는 변수 3개를 사용한다. 1. 탐색하고자 하는 범위의 시작점 2. 끝점 3. 중간점..

정렬 알고리즘은 이진탐색의 전처리 과정이기도 하다. 정렬 알고리즘의 종류 - 선택 정렬 - 삽입 정렬 - 퀵 정렬 - 계수 정렬 [선택 정렬] 데이터가 무작위로 여러개 있을 때, 가장 작은 데이터를 선택하는 가장 원시적인 방법 무작위로 나열된 데이터 N개가 있을 때, 선택 정렬은 가장 작은 데이터를 맨 앞으로 보내는 행위를 N-1번 반복하면 정렬이 완료된다. /*선택 정렬*/ array = [7, 5, 9, 0, 3, 1, 6, 2, 4] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[j] < array[min_index]: min_index = j array[i], array[min_index] = ..

[DFS] DFS는 Depth-First Search의 약자로 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 프로그래밍에서 그래프를 표현하는 방식은 크게 2가지가 있다. - 인접 행렬: 2차원 배열로 그래프의 연결관계를 표현 연결되어 있지 않은 노드는 무한(INF)로 표현 모든 관계를 저장하므로 노드 개수가 많아질수록 메모리 낭비 하지만 연결관계 정보를 얻는 속도는 빠름 - 인접 리스트: 리스트로 그래프의 연결 관계를 표현 C++나 자바에선 연결리스트를 사용, Python의 경우는 2차원 리스트 사용 메모리 공간의 낭비가 적음 연결관계 정보 얻는 속도가 느림 (특정 노드에 대한 인접 리스트를 앞에서부터 차례대로 다 확인해야 하기 때문) DFS는 스택 자료구조를 ..