본문 바로가기

전체 글221

[알고리즘] ep7++) 다익스트라 확장 알고리즘 다익스트라 확장 알고리즘은 기본 다익스트라 알고리즘을 수정하여 단일 출발점에서 목표 지점까지의 최단 경로뿐만 아니라 최단 경로의 수까지 계산할 수 있도록 한다. 이 문제에서 요구하는 것은 다익스트라 알고리즘을 사용하여 각 정점까지의 최단 거리를 계산하고, 동시에 각 정점에 도달하는 최단 경로의 수를 세는 기능을 추가한 것이다.  위 샘플그래프 G에 대해 아래 정점쌍 4개를 s(ource) 및 t(arget) 인자쌍으로 각각 사용하여 수행하라(즉, 프로그램을 4회 수행함). 각 수행 결과는 아래 예시처럼 인쇄할 것 [출력예시]source    target    최단거리    최단경로 수C             A            1                 1 C             F      .. 2024. 8. 2.
Java 14 - 새로운 switch문(switch expression) 기존의 switch문에 대한 개발자들의 불만이 많았다 switch문을 사용하는 이유에 가장 큰 이유는 가독성이지만, switch문은 가독성이 그닥 좋지 않은 데다가 코드줄만 더 잡아먹었다2020년 Java 14에서 도입된 새로운 switch 문은 더 간결하고 표현력이 뛰어나게 만들기 위해 설계되었다 이 새로운 switch 문은 "switch expression"이라고도 불리며, 실제 현업에서도 종종 사용되니 잘 알아두자 기존의 switch 문과 다른 주요 특징은 다음과 같다1. 표현식으로 사용 가능새로운 switch 문은 값으로 평가될 수 있다. 즉, 변수에 결과를 할당할 수가 있다.int numLetters = switch (day) { case MONDAY, FRIDAY, SUNDAY -> 6;.. 2024. 7. 28.
[알고리즘] ep7+) 다익스트라와 벨만-포드 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라.  문제1) 무방향 양의 가중그래프 -> 다익스트라 알고리즘무방향 양의 가중그래프(undirected weighted graph) G와 출발정점이 주어지면, 출발정점에서 다른 모든 정점으로 가는 최단거리를 구하는 프로그램을 작성하라.  입력 그래프의 성질:◦ n(1 ≤ n ≤ 100)개의 정점과 m(1 ≤ m ≤ 1,000)개의 간선으로 구성.. 2024. 7. 27.
[알고리즘] ep7) 최단경로 ㅁ최단경로 문제(shortest path problem): 가중그래프 두 개의 정점 u와 v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제최단경로길이: 간선들의 무게 합 응용: 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 [최단경로 속성 2가지]속성1)최단경로의 부분경로(subpath) 역시 최단경로이다 속성2)출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다 - 단일점 최단경로(single-source shortest path)  - 최단경로는 무방향뿐만 아니라 방향그래프에서도 정의가 가능하다- 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다- 최단경로트리(shortest path tree)는 루트.. 2024. 7. 26.
[알고리즘] ep6+) Prim-Jarnik과 Kruskal 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) Prim-Jarnik 알고리즘 구현입력으로 주어지는 그래프를 Prim-Jarnik 알고리즘을 이용하여 최소신장트리(Minimum Spanning Tree, MST)를 생성하는 프로그램을 작성하고, 최소신장트리의 생성 과정과 총무게를 결과로 출력하시오.  입력 그래프의 성질: n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m .. 2024. 7. 26.
[알고리즘] ep6) 최소신장트리(MST) ㅁ가중그래프(weighted graph): 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프 무게의 예: 거리, 비용, 시간 등 이 철도 그래프에서는 간선의 무게가 여행거리를 표현한다  신장 부그래프: 그래프 G의 모든 정점들을 포함하는 부그래프신장트리(spanning tree): 모든 정점이 다 이어져 있으면서, 싸이클이 없는 무방향 그래프 (자유 트리인 신장 부그래프)ㅇ최소신장트리(MST, Minimum Spanning Tree): 가중그래프의 총 간선 무게가 최소인 신장트리응용: 통신망, 교통망 [MST 속성 2가지] - MST 알고리즘 정확성 검증에 이용1. 싸이클 속성T를 가중그래프 G의 MST라 하자e를 T에 존재하지 않는 G의 간선으로, C를 T에 추가하여 형성된 싸이클로 가정그.. 2024. 7. 25.
휴리스틱(heuristic) 알고리즘 ㅇ휴리스틱(heuristic): 문제 해결, 학습, 또는 발견을 위한 경험적 기법 또는 방법론 최적의 해결책을 보장하지는 않지만, 실용적으로 충분히 좋은 해결책을 빠르게 찾는 데 유용하다 [활용 분야] 컴퓨터 과학: 알고리즘 설계에서, 특히 탐색 알고리즘에서 휴리스틱을 사용하여 탐색 공간을 줄이고 효율성을 높인다의사결정: 불확실한 상황에서 결정을 내릴 때, 휴리스틱은 빠른 결정을 돕는 도구로 사용된다심리학: 인지 심리학에서 사람들의 문제 해결과 의사결정 과정을 설명하기 위해 휴리스틱 개념을 사용한다 예를 들어, 가용성 휴리스틱(availability heuristic)은 사람들이 머릿속에 쉽게 떠오르는 정보를 바탕으로 결정을 내리는 경향을 설명합니다   ㅇ휴리스틱 알고리즘: 불충분한 시간이나 정보로 인하.. 2024. 7. 25.
[알고리즘] ep5-3++) 분할통치법 vs DP 문제) 여행의 최소비용을 구하는 알고리즘을 작성하라.airtelDC(분할통치 버전)와 airtelDP(동적프로그래밍 버전)를 구현하고 실행시간을 비교 프로그램 요구사항: 1)  각 해결버전의 정방향, 역방향 버전 가운데 자유롭게 하나를 선택하여 구현하라. 2)  출력예시: 최종적으로 다음과 같이 인쇄되어야 한다. ※ 참고1) 아래는 MAX = 30인 경우의 인쇄결과임.2) X.XXXXXXXX는 cputime in milliseconds.  주의:반드시 아래 가이드라인의 main 함수 내용과 동일하게 실행하고 출력을 구하라.n = 6로 한 테스트실행 결과가 수작업실행 결과와 일치하는지 확인한 후 n = MAX로 한 본실행을 시도할 것.경로가 아닌 최소비용만을 요구하는 문제이므로, 만약 최소비용 경로가 두 .. 2024. 7. 24.
배열의 인덱스가 0부터 시작하는 이유 혹시 배열의 인덱스가 1이 아닌 0부터 시작하는 이유에 대해서 잘 아는가?아마 많은 사람들이 당연하게 인덱스를 0부터 사용하면서 그 이유는 잘 모를 것이다배열의 인덱스를 1이 아닌 0부터 사용하는 데에는 많은 이유가 있다지만, 그중에서 가장 중요하고 본질적인 이유는 바로 "메모리 주소 계산의 용이성"이다  배열은 메모리에서 연속적인 블록으로 할당된다. 배열의 첫 번째 요소의 주소를 기준으로 다른 요소의 주소를 계산할 때, 인덱스가 0부터 시작하면 포인터 산술이 간단해진다. 예를 한 번 들어보면, array[i]는 배열의 첫 번째 요소 주소에 i * 요소 크기를 더한 값과 같게 된다. 인덱스가 0부터 시작하면 첫 번째 요소의 주소에 0을 더하는 것이 되어 매우 직관적이게 된다.C언어와 같은 초기 프로그래밍.. 2024. 7. 24.

티스토리툴바