분류 전체보기
-
Graph Optimization Problems and Greedy AlgorithmsCS/알고리즘 2023. 11. 22. 20:08
Optimization Problem 최적해 (Optimal Solution) : Minimizing the total costs or Maximizing the total benefits Anaylyze all possible outcomes Make a series of choices -> Effect is to achieve the optimal Greedy Algorithms Making choices in sequence such that Each individual choice is the best Once a choice is made, it cannot be undone Possible drawback : Actions with a small short-term cost may be lea..
-
Graphs and Graph TraversalsCS/알고리즘 2023. 11. 21. 22:00
Definition 1. Directed Graph Digraph, a pair $G = (V, E)$ $V$ : Set of vertices (Node) $E$ : Set of ordered pairs of elements of $V$ 2. Undirected Graph A pair $G = (V, E)$ $V$ : Set of vertices (Node) $E$ : Set of unordered pairs of distinct elements of $V$ 3. Weighted Graph A triple $G = (V, E, W)$ $(V, E)$ is graph (directed or undirected) For an edge, $W(e)$ : weight 4. Graph Representations..
-
[C++] 이동 의미론 Move Semantics프로그래밍 언어 2023. 11. 20. 23:20
C++11부터 복제를 통한 자원의 낭비를 줄이기 위해 객체 자원의 소유권을 이전할 수 있도록 추가된 개념이다. Foreword 이전에는 복제를 통해 자원의 소유권을 이전했었다. 복제 방식은 2가지로 얕은 복제(Shallow Copy)와 깊은 복제(Deep Copy)가 있다. 얕은 복제란 원본 객체의 데이터 맴버를 대상 객체로 단순히 복제하거나 대입하는 방식으로 참조는 복제되지만 참조되는 객체는 복제되지 않는다. 얕은 복제 사용 시 객체의 할당 메모리를 해제할 경우 허상 포인터나 미아(Orphan)으로 인한 메모리 누수의 문제점이 존재한다. 이런 문제점을 해결하기 위해 깊은 복제를 사용하는데 깊은 복제란 참조값의 복제가 아닌 참조된 객체 자체가 복제되는 것을 뜻한다. 단, 깊은 복제를 사용하기 위해선, 클..
-
입실론 테스트프로그래밍 언어 2023. 11. 20. 21:54
이번 글에선 실수를 비교하기 위한 방법인 입실론 테스트에 대해 알아보고자 한다. Foreword 코딩을 하면서 두 실수가 정확하게 같은지를 비교하는 로직을 작성할 때가 많다. 하지만 때때론 잘못된 결과를 출력하는 경우가 발생한다. 예를 들어, 어떤 실수가 정확하게 0과 같은지를 비교할 때이다. float f = sqrt(9.0f) - 3.0f; // 9^2 - 3 if (f == 0.0f) // Works only sometimes { // Equal } Problem Explanation 우선, 이러한 문제는 정수를 비교할 땐 절대 발생하지 않는다. 만약 int타입의 $3$을 int타입의 $3$을 뺀다면, 항상 $0$을 출력할 것이다. 이러한 문제는 실수(C++에선 float 타입과 double 타입)..
-
백준 2667 : 단지 번호 붙이기백준 2023. 11. 20. 19:05
1. 문제 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2. 문제 접근 2차원 배열이 주어지고 이를 조건에 따라 탐색. -> DFS나 BFS를 사용하여 그래프를 탐색 3. 문제 해결 주어진 단지 정보를 순차적으로 탐색. $(i, j)$ 노드가 아파트가 존재한다면 BFS나 DFS 탐색 시작. $(i, j)$ 노드가 이미 방문한 노드라면 탐색하지 않음. 노드의 갯수를 차례대로 저장하여 마지막에 정렬 후 반환. 4. 코드 #include #in..
-
객체 지향 설계 SOLID프로그래밍 언어 2023. 11. 16. 21:40
C++는 객체 지향 언어이고 객체 지향 프로그래밍 및 설계를 위한 5가지 법칙이 있다. 이를 SOLID 법칙이라고 칭하며 이는 소스 코드가 읽기 쉽고 확장하기 쉽게 될 때까지 리펙토링(Refactoring)을 위한 지침이다. 단일 책임 원칙 Single Responsibility Principle 단일 책임 원칙이란 "한 클래스는 하나의 책임만 가져야 한다"라고 정의할 수 있으며, 이는 "모든 클래스는 하나의 책임만 가지며, 클래스는 그 책임을 완전히 캡슐화해야 함."를 의미한다. 여기서 책임이란 해당 클래스를 변경해야 하는 이유이며, 단일 책임 원칙을 다시 정의해 보면 "클래스나 모듈은 반드시 한 가지의 이유에 의해 변경되어야 한다"라고 생각할 수 있다. 단일 책임 원칙을 지켜야 하는 이유는 어떠한 코..
-
백준 2468 : 안전 영역백준 2023. 11. 16. 17:28
1. 문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 2. 문제 접근 장마로 인한 물의 높이가 얼마인지 주어지지 않았으며, 안전지대의 개수는 지역의 높이에 따라 규칙 없이 달라짐. -> 최소 높이인 $0$부터 지역의 최대 높이인 $100$까지 모두 확인해야 함 -> 완전 탐색 2차원 배열이 주어지고 이를 조건에 따라 탐색. -> DFS나 BFS 사용 3. 문제 해결 높이 $h$를 $0$부터 $100$까지 설정하고 안전 지대 개수를 확인 주어진..
-
Zero Division with Floating-Point Numbers프로그래밍 언어 2023. 11. 16. 02:04
개발을 하면서 어떠한 값을 0으로 나누는 미친 짓을 하는 개발자는 없겠지만 (그게 나야) 부동소수점에서의 Zero Division을 알아보고자 한다. 우선 두 가지의 배경 지식이 필요하다. 부동 소수점 계산 첫 번째로 흔한 개발자 상식으로 나오는 문제를 살펴보자. $1.1 + 0.1 == 1.2$는 $true$일까? 아님 $false$일까? 정답은 $false$이다. 이는 부동 소숫점을 어떻게 표현하는지에 대해 확인하면 왜 $false$가 나오는지 알 수 있다. float의 경우 부호 $1$비트, 지수 부분 $8$비트, 가수 부분 $23$비트로 구성되고, double의 경우 부호 $1$비트, 지수 부분 $11$비트, 가수 부분 $52$비트로 이루어져있다. 정수와 다르게 부동 소숫점은 정확한 값으로 표현할..