완전 탐색과 백트래킹은 코딩 테스트에서 중요한 탐색 기법으로, 문제에서 가능한 모든 경우의 수를 고려하여 최적의 해답을 찾는 데 사용된다. 오늘은 완전 탐색과 백트래킹이 어떤 개념인지 알아보도록 하겠다. 완전 탐색 (Brute Force)  완전 탐색(Brute Force)은 모든 가능한 경우를 무식하게 하나하나 다 확인하는 방식으로 문제를 해결한다. 가능한 모든 조합, 모든 배열 등을 전부 시도해본 뒤 조건에 맞는 결과를 찾는다.따라서 완전 탐색은 가장 단순한 방법이지만, 시간 복잡도가 클 수 있으니 입력의 크기를 잘 확인해야 한다. 간단한 문제로 확인해보겠다.   백준 2309번: 일곱 난쟁이https://www.acmicpc.net/problem/2309 ✅ 코드 확인더보기#include #incl..

순열과 조합은 코딩 테스트에서 자주 등장하는 개념으로, 데이터를 나열하거나 선택하는 문제를 해결하는 데 필수적이다.  이러한 개념을 이해하고 활용하면 효율적인 알고리즘 설계와 문제 해결에 큰 도움이 된다. 오늘은 순열과 조합에 대해 개념과 코드에 대해 알아보도록 하겠다. 순열(permutation) 순열(permutation): 여러 개의 요소를 특정 순서에 따라 배열하는 경우의 수  예를 들어, 3개의 숫자 1, 2, 3을 모두 사용해 순열을 구하는 경우 P(3, 3) = 3! = 6이 되어 6가지 경우의 수가 나온다.- (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) 시간 복잡도는 얼마일까?O(n!)이다. n개의 요소가 있다면 첫 번..

최근 개발자들이 취업을 준비할 때 필수 관문이 된 코딩 테스트에서 다양한 언어들이 사용되지만, 그중에서도 많은 개발자들이 C++을 선호하는 경향이 있다. 오늘은 C++이 코딩 테스트에서 유리한 이유과 장점에 대해서 분석해보도록 하겠다. 빠른 실행 속도 C++의 실행 속도는 다른 언어에 비해 상당히 빠른 편이다. 일반적인 알고리즘 문제의 경우, Python보다 약 10 ~ 100배 정도 빠른 실행 속도를 보이며, Java보다 약 1.2 ~ 2배 정도 빠른 것으로 평가된다. 특히 수백만 개의 반복 연산이나 대규모 데이터 구조를 다룰 때 속도 차이가 두드러진다.  C++은 컴파일 시점에 기계어 코드로 변환되므로, 실행 시간에는 기계어 수준에서 곧바로 연산이 이루어진다. 반면 Python과 같은 인터프리터 언어..

Unity 에셋 번들은 게임의 리소스를 효율적으로 관리하고 최적화하는 데 중요한 역할을 한다. 특정 리소스를 에셋 번들로 묶어 필요할 때만 다운로드하고 로드함으로써 메모리 사용을 줄이고 게임 로딩 속도를 개선할 수 있다. 현업에서 중요한 기술 중 하나이므로 에셋 번들에 대해 알아보도록 하겠다. 에셋 번들(Asset Bundle)이란? 에셋 번들: 여러 에셋들을 하나로 묶어 주는 파일 포맷 유명한 모바일 게임들을 다운해본 적이 있는가?이때 바로 플레이가 가능하지 않고 패치가 시작된다.그 이유는 에셋 번들을 다운로드하기 때문이다. 에셋 번들 없이 게임을 빌드한다면?게임 용량이 엄청 커지고, 에셋이 변경될 때마다 매번 에셋 전체를 다운받아야 해서 비효율적이다.그래서 모바일 게임은 에셋 번들이 필수이다.   에..

싱글톤 패턴이란?싱글톤 패턴: 특정 클래스의 인스턴스가 단 하나만 생성되는 것을 보장하는 디자인 패턴 Player 및 Monster 같은 경우 여러 개의 인스턴스가 존재할 수 있으니 싱글톤의 대상이 아니다.GM(GameManager) 인스턴스는 씬에서 단 하나만 존재하기 때문에 싱글톤의 대상이다. 아직 감이 오지 않는다면 예를 더 들어보겠다.어떤 게임에 Stage 클래스와 StageManager 클래스가 있다고 가정하자.이때, Stage는 스테이지 데이터 및 행동 관리 클래스이며 StageManager는 Stage를 관리하는 클래스이다.Stage는 게임에 여러 개로 존재할 수 있으므로 싱글톤 패턴을 적용할 수 없다.하지만 StageManager가 10개의 Stage를 관리하는 클래스이며 단 하나만 존재하..

Unity를 개발하다보면 잦은 GetComponent 호출은 성능을 크게 떨어뜨린다는 말을 자주 듣습니다. '그렇다면 GetComponent는 얼마나 느릴까요?' 오늘은 이 궁금증을 해결하기 위해 실험을 준비했습니다 :) GetComponent 성능 실험 실험 구성은 다음과 같다. 1. Unity 빈 프로젝트 환경 구성2. 단순 연산을 N번 돌렸을 때, 1ms가 나오는 N을 선택3. Update 함수에서 N번의 GetCompoent 돌려서 성능 체크 바로 시작해보자.  Scene에는 카메라, 직사광선, 그리고 테스트용 스크립트가 있음 테스트용 스크립트에는 특정 액션의 수행 시간을 체크하는 메서드를 보유함 public void MeasurePerformance(Action action, int loopCo..

최소 신장 트리(MST: Minimum spanning tree)는 그래프에서 모든 노드를 연결할 때 사용된 Edges의 가중치의 합을 최소로 하는 트리를 의미한다. MST의 특징은 다음과 같다. 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없는 모순 발생) N개의 노드가 있다면 Edge의 개수는 N-1개다. MST를 구할 때 사용하는 알고리즘은 다음과 같다. 크루스칼(kruskal) 알고리즘 프림(Prim) 알고리즘 이 포스터에선 크루스칼 알고리즘으로 MST를 구현해보도록 하겠다. MST: 크루스칼 알고리즘 크루스칼 알고리즘으로 MST를 구할 땐 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘에 대해 익숙하지 않다면 아래 포스터를 참고하자. https..

플로이드-워셜(Floyd-warshall) 알고리즘은 모든 노드에 대해 그래프에서 최단 거리를 구하는 알고리즘이다. 이 알고리즘의 특징은 다음과 같다. 음수 가중치가 있어도 수행할 수 있다. 동적 계획법(Dynamic Programming) 원리를 따른다. 시간 복잡도는 O(V ^ 3)으로 많이 느린 편에 속한다. 그래서 N이 1000개 이상인 경우에는 사용하기 어렵다. 플로이드-워셜 자료구조 먼저 그래프를 표현할 인접 행렬이 필요하다. 인접 행렬은 2개의 노드 인덱스와, 1개의 거리 요소로 구성되어 있다. 이 자료구조 하나로 플로이드-워셜 알고리즘을 구현할 수 있다. 플로이드-워셜 원리 플로이드-워셜의 핵심 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존..

벨만-포트(Bellman-ford) 알고리즘은 다익스트라 알고리즘과 유사하게 특정 노드로부터 그래프에서 최단 거리를 구하는 알고리즘이다. 차이점은 아래과 같다. Edge 가중치가 음수를 가질 수 있다. 음수 사이클의 존재 여부를 판단할 수 있다. 시간 복잡도: O(V * E) 벨만-포드 자료구조 벨만-포드는 Edge 기반으로 동작하기 때문에 엣지 리스트로 그래프를 표현한다. 엣지 리스트는 보통 Edge 구조체로 저장한다. 그리고 다익스트라와 마찬가지로 최단 거리를 저장하기 위한 정답 리스트가 필요하다. 시작 노드는 0으로, 나머지는 무한대에 가까운 Dummy 값으로 초기화해준다. 벨만-포드 원리 벨만-포드는 Edge에 대해 for문을 돌기 때문에 업데이트 반복 횟수는 (N-1) 이다. 음수 사이클이 없을..

다익스트라(Dijkstra) 알고리즘은 그래프에서 특정 지점에서 모든 노드를 지나는 최단 거리를 구할 때 사용하는 알고리즘이다. 이때 그래프가 다음 특성을 가질 때 사용 가능하다. 모든 Edge의 비용이 양수여야 한다. 다익스트라의 시간 복잡도는 O(E * log V)이다. 다익스트라 자료구조 먼저, 그래프를 표현하기 위해서 인접 리스트 자료구조를 사용한다. 인접 리스트의 인덱스는 Start 노드이며, 각 인덱스에 해당하는 요소는 (End 노드, 가중치)이다. 만약 양방향 그래프의 경우 이방향에 대해 저장해줘야 한다. 추가로 최단 거리 배열이 필요하다. 이것은 다익스트라 원리를 구현하기 위해 필요한 자료구조이다. 처음에는 무한대에 가까운 Dummy 값으로 초기화해준다. (시작 노드는 0으로 초기화) 또한..