전체 글 93

[Boj] 백준 C++ #16948 데스 나이트

📍 문제 링크 : https://www.acmicpc.net/problem/16948 📍 알고리즘 분류 : BFS 📍 문제 풀이이 문제는 큐를 이용해서 BFS로 해결할 수 있다. (r,c)의 위치에서 이동할 수 있는 칸은 아래 그림과 같이 총 6개이다. 따라서 한 위치에 대해 이동할 수 있는 6개의 위치를 모두 탐색해주면 된다.체스판을 넘어가거나, 이미 방문한 위치가 아니면 큐에 넣어준다.이미 방문했다면, 지금 방문한 것은 최단 횟수의 방문이 아니라는 것이므로 고려해줄 필요가 없다. 모든 지점은 처음으로 방문했을 때가 최단 횟수의 방문이다. 위 과정을 큐가 빌 때까지, 혹은 목표 지점에 도달할 때까지 반복한다. 이 문제의 핵심 로직은 모든 지점은 처음으로 방문했을 때가 최단 횟수의 방문이라는 것이다..

Boj 2025.01.07

[Boj] 백준 C++ #2138 전구와 스위치

📍 문제 링크 : https://www.acmicpc.net/problem/2138 📍 알고리즘 분류 : 그리디 알고리즘 📍 문제 풀이 신기한 점이 어떤 전구를 먼저 켜고 끄든, 순서가 중요하지 않다는 것이다!따라서 우리는 첫 번째 전구부터 순서대로 탐색하면 된다. 그리디하게. 현재에 최적이 되도록.첫 번째 전구를 목표 상태와 비교하고 다르다면 전구의 상태를 바꾸고, 같다면 그냥 두면 된다. 그런데 전구는 자신의 왼쪽, 자신, 자신의 오른쪽 이렇게 3개의 전구의 상태에 영향을 미치게 되는데그리디하게 접근할 경우 이 조건이 훨씬 쉽게 만들어진다. 현재 보고 있는 i번째 전구를 변경하고자 할 경우 할 수 있는 것은 i+1번째 전구를 누르는 것이라는 것이다! i-1번째 전구나 i번째 전구를 누르면 안되는..

Boj 2025.01.05

[Boj] C++ #1339 단어 수학

📍 문제 링크https://www.acmicpc.net/problem/1339 📍 알고리즘 분류그리디 📍 문제 풀이직관적으로 높은 자리에 큰 수가 와야된다는 것을 파악할 수 있다. 그런데 단어가 하나가 아니기 때문에, 어떤 단어에서는 높은 자리수의 알파벳이 다른 단어에서는 가장 낮은 자리수에 위치해있을 수도 있다. 따라서 모든 단어를 종합하여 판단해야 한다. ABC와 CADB가 주어졌다고 해보자.단어 수의 합은 (100*A + 10*B + C) + (1000*C + 100*A + 10*D + B) = (1000*C + 200A + 11B + C)가 될 것이다.이게 최대가 되기 위해서는 가장 큰 수를 곱하는 알파벳부터 9, 8, 7, 6, .. 순서대로 바꿔주면 된다.따라서 C = 9, A = 8, ..

Boj 2025.01.04

[Flutter] Stateful 위젯이 두 개의 클래스로 나눠진 이유

Flutter 앱을 구성하는 위젯은 Stateful 위젯과 Stateless 위젯으로 구분할 수 있다. 이렇게 구분하는 이유는 효율적인 상태 갱신을 위해서이다. 예를 들어 도움말 페이지는 사용자에 의해 화면이 바뀔 내용이 거의 없이 정적으로 화면을 보여주면 된다. 이런 경우 StatelessWidget 클래스를 상속받아서 위젯을 만든다. 하지만 마이페이지에서 이름을 변경하면 변경된 이름으로 화면이 갱신되어야 할 것이다. 이런 경우 StatefulWiddget을 상속받아서 만든다. 앱이 위젯의 상태를 감시하고 있다가 위젯이 특정 상태가 되면 알맞은 처리를 수행해야 한다. 상태가 연결된 동적인 위젯이 StatefulWidget이다. Stateful 위젯은 계속 상태를 지켜봐야하므로 그만큼 메모리나 CPU 등..

Flutter 2024.12.27

[Boj] 백준 C++ #1202 보석 도둑

📍문제 링크https://www.acmicpc.net/problem/1202 📍알고리즘 분류그리디, 우선순위 큐 📍 풀이 방법최대한 많은 보석을 훔치기 위해서는 최대한 비싼 보석을, 많이 담아야 한다.따라서 비싼 보석부터 담아야 하는데, 최대로 용량을 채울 수 있는 가방에 넣어야 한다.반복문을 통해 가방을 하나씩 그리디하게 보면서 넣을 보석을 정해준다.우선순위 큐를 이용해서 하나의 가방 안에 들어갈 수 있는 무게의 보석들 중 가격이 가장 비싼 것을 담으면 된다. 어떤 가방부터 보아야할까?용량이 큰 가방부터 본다면, 비싼데 크기가 작은 보석이 용량이 큰 가방에 담길 것이다. 더 보석을 가져갈 수 있을텐데 용량이 낭비될 것이다.따라서 용량이 작은 가방부터 탐색한다. 작은 가방에 담기는 무게 중에서 비싼..

Boj 2024.12.27

[알고리즘] MST(Minimum Spanning Tree, 최소신장트리) - Kruskal, Prim 구현 (C++)

더보기목차1. Greedy 알고리즘이란2. MST란3. Kruskal 알고리즘- 이론, 구현4. Prim 알고리즘- 이론, 구현1. Greedy 알고리즘이란Greedy 알고리즘이란 욕심장이 기법으로 당장 이 순간에서 최적이 되는 해를 구하는 것에, 즉 현재에 집중하는 알고리즘입니다. 과거와 미래는 전혀 신경쓰지 않습니다. Greedy 알고리즘의 핵심 단계는 다음과 같습니다.  1) Selection Procedure (선택)현재를 기준으로 가장 최적이 되는 해를 선택하는 단계입니다. 최적 해를 선택하여 집합에 추가합니다. 이 과정을 위해 선행되는 핵심은 어떤 값을 먼저 볼 것인지에 대한 우선순위 결정입니다. 2) Feasibility Check (유효성 검사)앞에서 선택한 해를 포함한 집합이 문제를 해결..

알고리즘 2024.11.25

딥러닝의 양자화 Quantization

* 아래 블로그를 보고 공부하며 작성했습니다.https://gaussian37.github.io/dl-concept-quantization/#quantization-%EC%9D%B4%EB%9E%80-1 딥러닝의 Quantization (양자화)와 Quantization Aware Traininggaussian37's bloggaussian37.github.io  양자화란 모델의 파라미터를 lower bit로 표현함으로서 계산과 메모리 access 속도를 높이는 경량화 기법이다. 실수형 변수를 정수형 변수로 변환하는데, 보통 FP32 타입을 INT8 타입 형태로 변환하는 방법을 사용한다.  Weight Quantization 5가지 전제조건Inference Only양자화는 inference에서만 사용한다...

엣지컴퓨팅 2024.11.19