우노

그래프란? 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 의미합니다. 그래프 탐색이란? 하나의 정점으로부터 시작하여, 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미합니다. 너비 우선 탐색(BFS, Breadth First Search)이란? 루트 노드 또는 임의의 노드에서 시작하여, 일정 노드와 인접한 노드들을 우선으로 탐색하는 방법입니다. 주로, 어떤 두 노드 사이의 최단 경로를 구할 때 사용되며, 주로, 큐(Queue)라는 자료구조를 사용해 구현됩니다. 너비 우선 탐색 예제 BFS 는, 아래와 같은 간단한 알고리즘에 의해 작동됩니다. 큐에서 하나의 노드를 꺼냅니다. 해당 노드와 연결된 노드들 중, 방문하지 않은 노드들을 큐에 삽입하며, 방문 처리합니다. 반복합니다...

문제 링크 https://www.acmicpc.net/problem/2178 풀이 중요 내용 (0, 0) 에서 (N-1, M-1) 까지의 최소 칸수를 구하는 문제 최단 경로 탐색 시, 현재까지 이동한 칸의 개수를 저장해나가며 탐색하는게 중요하므로, 이동한 칸의 개수를 2차원 배열에 저장하며 진행 탐색은 상하좌우로만 진행하며, 아직 방문하지 않았고, 이동 가능한 칸일 경우에만 이동함 좌측 미로를 BFS 탐색할 경우, 이동칸 결과는 우측과 같음 코드 #include #include #define MAX 101 using namespace std; int N, M; // 미로 크기 int maze[MAX][MAX]; // 미로 표현용 2차원 배열 int visited[MAX][MAX]; // 방문 기록용 2차..

문제 링크 https://www.acmicpc.net/problem/9466 풀이 중요 변수 설명 done : 팀 매칭 결과 배열 0 : 아직 팀 매칭 결과를 모르는 학생 1 : 팀 매칭 결과를 아는 학생 visited : 방문 배열 0 : 아직 방문하지 않은 학생 1 : 방문한 학생 알고리즘 반복문을 통해, 현재 학생이 아직 방문한 적이 없는 학생이라면, 탐색 시작 현재 학생은 방문한 것으로 처리 현재 학생이 원하는 다음 학생이, 이전에 방문된 적이 없다면, 다음 학생을 탐색 현재 학생이 원하는 다음 학생이, 이전에 방문된 적은 있지만, 아직 팀 매칭이 끝나지 않은 학생이라면 현재 학생과 다음 학생을 기준으로, 연결된 사이클을 확인하며, 사이클에 속한 인원을 계산 4 → 7 → 6 → 4 인 경우, 팀..

들어가기 앞서, 딥러닝 모델을 특정 디바이스 상에서 효율적으로 동작시키기 위해서는, 동작시킬 딥러닝 모델을, 타겟 디바이스에서 최적의 속도와 정확도를 낼 수 있는 머신 코드로 변환해야합니다. 이러한 코드 변환 작업을 자동으로 지원해주는 도구를, ‘딥러닝 컴파일러’라고 합니다. 딥러닝 컴파일러 개념도 딥러닝 컴파일러는, 다양한 딥러닝 플랫폼에서 학습된 딥러닝 모델을 입력으로 받아, 특정 하드웨어에서 동작 가능한 머신 코드(또는, 백엔드 코드)를 자동으로 생성합니다. 최근 제안된 XLA, TVM, Glow 와 같은 딥러닝 컴파일러들은, TensorFlow, Pytorch, MxNet, ONNX 등의 프레임워크로 작성된 모델을 입력으로 하여, CPU 및 GPU 용 백엔드 코드를 생성하고 있습니다. CPU 용 ..

TensorFlow Lite(TFLite) 란? TensorFlow Lite(TFLite)는 구글에서 개발한, TensorFlow(keras) 모델 최적화 라이브러리입니다. TensorFlow(keras) 모델만 최적화할 수 있습니다. TFLite 는 TFLite Converter 와 TFLite Interpreter 로 구성되어있습니다. TFLite Converter TensorFlow 모델을, Interpreter가 사용할 수 있도록 최적화하는 역할입니다. 효율적이고, 용량이 적으며, 성능은 유지하도록 TFLite Interpreter 최적화된 모델을 다양한 하드웨어에서 돌아갈 수 있도록 도와주는 역할입니다. 모바일 폰, 임베디드 리눅스 디바이스, 마이크로 컨트롤러 등... 따라서, TFLite 는 ..

들어가기 앞서, ‘프레임’ 이라는 단어는, 게임을 좋아하는 유저라면 한 번쯤은 들어봤을 법한 단어입니다. ex) “프레임 드랍이 너무 심하다.” 하지만, ‘프레임’ 이라는 단어가 정확히 어떤 뜻을 가지고 있는지에 대해서는 잘 모르고 있는 경우가 많습니다. 따라서, 해당 포스트에서는 프레임에 대해서 자세히 알아보겠습니다. 프레임(Frame) 이란? 프레임(Frame) 이란, 화면에 뿌려지는 정지 영상의 낱장을 의미합니다. 연속된 장면을 통해 움직임을 만들어내는 애니메이션이나 영화에서 유래된 용어입니다. 즉, 화면에 보여지는 정지 화면 한장을, 프레임이라고 할 수 있습니다. 초당 프레임(FPS, Frame Per Second) 이란? 초당 몇장의 정지 화면이 하나의 화면을 이루는지에 대한 단위를, 초당 프레..

들어가기 앞서, 모바일이나 임베디드 환경에서, 딥러닝 모델을 사용한 추론은 어렵습니다. 일반 PC 와 달리, 메모리, 성능, 저장공간 등의 제한이 있기 때문입니다. 따라서, 딥러닝에서는 모델 경량화와 관련된 연구들이 많이 진행되고 있습니다. 즉, “모델을 가볍게 만드는 연구”라고 이해할 수 있습니다. 이러한 경량화 연구는 크게 두 가지로 나눠집니다. 모델을 구성하는 알고리즘 자체를 효율적인 구조로 설계하는 연구 기존 모델의 파라미터들을 줄이거나 압축하는 연구 전자의 경우, 대표적인 방법으로 “모델 구조 변경”, “효율적인 합성곱 필터 기술”, “경량 모델 자동 탐색 기술” 이 존재합니다. 모델 구조 변경 모델 구조를 변경함으로써 경량화하는 방법 (ResNet, DenseNet, SqueezeNet, et..

문제 링크 https://www.acmicpc.net/problem/2110 풀이 중요한 부분 문제가 원하는 것은, 가장 인접한 두 공유기 사이의 거리가 최대인 것이지만, 결국, 모든 공유기들의 간격이 공평하게 설치되기를 원한다고 해석할 수 있습니다. 따라서, 모든 공유기들을 공평하게 설치할 수 있는 간격을 이분 탐색을 통해 찾아야합니다. 진행 순서 공유기 설치 좌표들을 오름차순으로 정렬합니다. 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한 뒤, 공유기를 가장 공평하게 설치할 수 있는 간격(mid)을 구합니다. 첫 번째 집에 공유기를 설치한 뒤, 첫 번째 집에서 나머지 집들 간의 간격을 확인하며, mid 이상으로 떨어져 있는 집을 탐색합니다. 첫 번째 집으로부터 mid 이상 떨어진 집을 찾은 경..

문제 링크 https://www.acmicpc.net/problem/2447 풀이 N 은 반드시 3의 거듭제곱(3, 9, 27, ...)입니다. 따라서, 우선 작은 N 을 가지는 정사각형에 별을 찍어보며, 어떤 좌표값이 공백인지를 확인해, 공백인 좌표를 일반화 해야합니다. N=3 3x3 크기 기준, 중앙 공백 좌표 (1, 1) i % 3 == 1 && j % 3 == 1 N=9 9x9 크기 기준, 중앙 공백 좌표 (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5) (i / 3) % 3 == 1 && (j / 3) % 3 == 1 3x3 크기 기준, 중앙 공백 좌표 (1, 1), (1, 4), (1, 7), (4, 1), (4, 4..

문제 링크 https://www.acmicpc.net/problem/6086 풀이 우선, 해당 문제를 해결하기 위해선, Network Flow 의 기본 개념과 주요 알고리즘에 대해서 알고 있어야합니다. https://wooono.tistory.com/401 해당 문제는, A 부터 Z 까지의 최대 유량을 구하는 것입니다. Network Flow 주요 알고리즘인 에드몬드-카프 알고리즘을 사용해 해결할 수 있습니다. 주의할 점은, 해당 문제의 모든 간선은 양방향이므로, A → B 간선의 유량을 입력 받았을 때, B → A 간선의 유량도 동일하게 할당해야한다는 것입니다. 코드 #include #include #include #include using namespace std; #define MAX_NODE 52..