CSE 전공노트

다익스트라 알고리즘(Dijkstra Algorithms)은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 다른 노드로 가는 최단 경로를 구해주는 알고리즘으로, 각각의 노드들 간의 가중치 (비용) 값이 음수가 아닐 때만 제대로 동작합니다. 다익스트라 알고리즘은 기본적으로 매번 가장 비용이 낮은 간선을 선택하기 때문에 그리디 알고리즘을 따른다고 볼 수 있습니다. 다익스트라 알고리즘은 기본적으로 다음과 같은 단계를 거칩니다. 1. 출발 노드를 설정한다. 2. distance 배열을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 3번과 4번 과정을 반복한다. 위에서도 알 수..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 이 문제는 DFS와 다이나믹 프로그래밍을 함께 이용하여 해결할 수 있습니다. dfs에 관한 기본적인 내용은 아래 문제의 풀이에서 볼 수 있습니다. jooona.tistory.com/65 [BOJ] 1303 - 전쟁 - 전투 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 스택을 이용할 수도 있지만, 저는 재귀를 이용해 문제를 해결했습니다. 문자열에서 '('를 만나면 재귀 함수를 시작하고 ')'를 만나면 재귀를 탈출하는 형식으로 코드를 작성했습니다. 재귀 함수의 동작은 아래와 같습니다. 1. '('를 만나면 재귀 함수 시작 2. 또 다른 '(' 또는 ')'를..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 기본적인 문제의 풀이는 아래의 문제와 같습니다. jooona.tistory.com/104 [BOJ] 1463 - 1로 만들기 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이.. jooona.tistory.com..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 기본적으로는 BFS를 이용해 문제를 해결할 수 있습니다. 단지 고슴도치와 물의 위치를 모두 탐색해 주어야 하므로, 큐와 BFS 함수를 따로따로 만들어주었습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다. jooona.tistory.com/63 [BOJ] 2178 - 미로 탐색 -개인적인 풀이일 뿐..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 굉장히 전형적인 다이나믹 프로그래밍 문제처럼 보이지만, 다이나믹 프로그래밍으로 해당 문제를 구현 시 메모리 초과가 나는 것을 확인할 수 있었습니다. 이 문제는 다이나믹 프로그래밍이 아닌 그리디 알고리즘으로 접근을 해야 합니다. B에서부터 뒤에 1을 뗄 수 있으면 떼주고, 2로 나눌 수 있으면, 2로 나누어주면서 A까지 이동하는 것입니다. 물론 1을 떼는 것에 우선순위를 둡니다. 그리고 중간에 1을 뗄 수도, 2로 나눌 수도 없는 ..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 문제의 시간제한을 봐도 알 수 있듯이, 이 문제는 다이나믹 프로그래밍을 이용해서 해결해야 합니다. 문제는 1을 만드는 것이지만, 구현은 반대로 1에서 N을 만드는 최소 연산 수를 구하는 식으로 했습니다. 배열을 하나 만들어, 반복문을 돌며 배열의 i 번째 칸에 i까지 오는데 걸리는 연산의 최소 횟수를 저장해주고, 마지막에 배열의 N번째 칸에 들어있는 값을 출력해주면 됩니다. i 번째 칸까지 오는데 필요한 연산의 최소 횟..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/16172 16172번: 나는 친구가 적다 (Large) 첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 문제의 의도는 KMP 알고리즘을 이용하여 문자열 비교를 수행하는 것입니다. KMP 알고리즘에 대해서는 아래의 글을 참고하시면 좋을 것 같습니다. jooona.tistory.com/102 [알고리즘] KMP Algorithm KMP(Knuth-Morris-Pratt) ..

KMP(Knuth-Morris-Pratt) 알고리즘은 두 문자열 s1과 s2가 주어지고, s1가 s2보다 길 때, s1 안에 s2가 포함되어 있는지를 탐색하는 알고리즘입니다. 1. 필요성 가장 기초적으로 브루트 포스를 이용해 s1에 s2가 포함되는 지를 확인하기 위해서는 아래와 같은 단계를 거쳐야 합니다. 2중 반복문을 통해 한 칸씩 옆으로 이동하며 비교를 해야 하기 때문에 시간 복잡도는 O(s1.length * s2.length)가 나오게 됩니다. 이를 개선하기 위해 등장한 알고리즘이 바로 KMP 알고리즘입니다. 위의 사진에서 첫 비교 부분만 분리해서 가져와 보겠습니다. 이미 앞에 세 자리는 같다는 것을 확인했고, 네 번째 자리에서 불일치가 발생했습니다. 그렇다면 '앞에서 이미 연산을 한 세 자리 정보..

UML(Unified Modeling Language)는 시스템 개발 과정에서 시스템 개발자와 고객 또는 개발자 상호 간의 의사소통이 원활하게 이루어지도록 표준화한 대표적인 객체지향 모델링 언어입니다. UML은 사물(Things), 관계(Relationships), 다이어그램(Diagram)으로 이루어집니다. 1. 사물 사물은 모델을 구성하는 가장 중요한 기본 요소입니다. 다이어그램에서 관계가 형성될 수 있는 대상들을 말합니다. 사물은 아래의 4가지로 분류할 수 있습니다. 1. 구조 사물 - 시스템의 개념적, 물리적 요소를 표현 (Class, Use Case, Component...) 2. 행동 사물 - 시간과 공간에 따른 요소들의 행위를 표현 (Interaction, State Machine...) 3..