mondegreen

[Part1-Chapter-01-Clip03] - 백준 1919 자바 처음에는 카운팅 배열을 생각하지 못하고 정렬을 한 후 각각의 char 값을 비교하면서 조건문에 따라 투포인터 방식으로 배열의 인덱스를 바꿔가며 답을 구했다. 관련 코드는 왼쪽 아래와 같다. 런타임 에러가 났던 이유는 인덱스가 배열의 크기를 넘어가지 않도록 while 문 조건에 넣었어야 했는데 꼼꼼하게 조건을 걸지 못했다. 망할... 두번째 방식은 강의를 듣고 아차라는 생각과 함께 곧바로 구현한 방식이다. 바로 카운팅 배열을 활용해 각 문자열에 소문자가 몇개씩 존재하는지 확인하고 차이 만큼 답에 더해주어 도출하는 방식이다. 자료구조나 매서드 모를 때는 제일 먼저 활용하려 했던 것이 카운팅 배열이었는데 이것저것 많이 알게 되면서 오히려 활..

패캠으로 다시 알고리즘 재활치료를 시작했다. 알고리즘 스터디와 병행하며 기초부터 다시 다져보자. [Part1-Chapter1-Clip01] 1. Java 문자열 클래스를 사용하기 위해 Java.lang 패키지를 사용하는데 별도의 import 문 없이 사용 가능하다고 한다. 코딩 테스트를 풀 때 항상 'import java.util.*;' 만 작성해도 문자열을 사용할 수 있었던 이유였다. 2. String은 한번 인스턴스가 생성되면 수정할 수 없다. 무슨 말이냐면 우리가 보통 array 에서 한 인덱스를 추출해서 값을 변경할 수 있었지만 String은 charAt(idx)로 해당 위치의 값을 조회(참조, 추출) 할 수는 있지만 그 값을 바꿀 수는 없었다. 그 대신 할 수 있었던 것은 1) char배열로 선..

동적계획법의 개념 그리지 알고리즘과 같이 최적화 문제를 해결하는 방법으로서 먼저 작은 부분의 문제들의 해를 구하고 이들을 이용하여 보다 큰 부분 문제를 해결한다. 이러한 방식으로 최종적으로 원래 주어진 문제를 해결하는 방법 동적계획법의 특징 1) 상향식 방법으로 접근한다. 2) (중복 부분문제 구조) 부분 문제 간 연관이 있어야만 적용 가능하다. 3) (중복 부분문제 구조) 모든 부분 문제는 한번만 계산한 뒤 결과를 저장하여 그 결과값만 재사용한다. (재계산 아님) 4) (최적화의 원칙) 전체 문제의 해가 최적이려면 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다. 5) 수행 속도가 빠름 => 재귀와 달리 중복 계산이 없고, 반복문 사용으로 함수 호출없다. => 이 '중복 부분문제 구조 Over..

위상정렬의 개념 위상정렬이란 순서가 있는(즉, 방향이 있는) 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프(Directed Acyclic Graph)의 모든 노드를 주어진 "선행순서를 위반하지 않으면서" 나열하는 것이다. 예시: 대학교 선수과목, 공장의 작업 순서, 요리 순서... 특정 정점을 진행하기 위해 거쳐야 하는 정점의 수(간선으로 연결된)를 진입차수라 하고 특정 정점에서 넘어가야 할 다음 정점의 수를 진출차수라고 한다. 그 중 선행 조건이 되는 진입차수가 중요하다. 위상정렬의 특징 1) 하나의 방향그래프에서는 여러 위상 정렬이 가능하다. 2) 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라 한다. 3) 위상 정렬의 과정에서 그래프..

최단 경로의 개념 간선의 가중치가 있는 그래프에서 "두 정점 사이의 경로들 중"에 간선의 가중치의 합이 최소인 경로 1) 다익스트라(음의 가중치 허용하지 않음) 2) 벨만-포드(음의 가중치 허용함) 다익스트라의 개념 시작 정점에서 끝 정점까지 거리가 최소인 정점을 선택해가며 최단 경로를 구하는 방식 프림과 유사하나 당장의 가중치 한 개의 값이 아닌 "가중치의 합"을 고려해야 하는 알고리즘이다. 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 다익스트라 동작 과정 1) 시작 정점 선택 2)..

최소 신장 트리의 개념 신장 트리 중에서 사용된 간선의 가중치의 합이 최소인 트리' 최소 신장 트리의 특징 1) 무방향 가중치 그래프 2) 그래프 가중치의 합이 최소 3) N개의 정점이 있는 그래프에 대해 반드시 N-1개의 간선을 사용해야 함 4) 사이클을 포함하면 안 된다 => 사이클 포함 = 불필요한 간선 존재 최소 신장 트리의 실 사용 비용이 최소가 되어야 하는 도로망, 통신망과 같은 다양한 분야 최소 신장 트리 구현 1) 크루스칼(Kruskal); 그리디 알고리즘의 한 종류 => 희소 그래프 인 경우 적합 간선을 하나씩 선택하며 MST를 찾는 알고리즘 (1) 모든 간선을 가중치에 따라 오름차순 정렬 (2) 가중치가 낮은 간선부터 선택하며 트리 증가 => 사이클이 존재*하면 그 다음 가중치를 가진 ..

서로소 집합의 개념 서로 중복 포함된 원소가 없는 집합들로서 즉, 교집합이 없는 집합이다. 집합에 속한 하나의 특정 멤버를 통해(→ 대표자; 대표자는 딱 하나 존재한다) 각 집합들을 구분한다. 특정 원소의 대표자를 가져왔을 때 동일하면 같은 집합에 속해있다고 판단할 수 있다. Union-Find의 개념 서로소 집합을 표편할 때 사용하는 알고리즘으로서 트리를 이용해 구현 가능 ; 그밖에 비트 벡터, 배열, 연결리스트를 이용해서도 구현 가능 Union-Find의 연산 연산1) Make-Set(x): 집합 생성 역할(x라는 원소를 대표자로 만든다) 연산2) Find-Set (x): x의 대표자를 가져오는 역할 (부모가 아님) 연산3) Union(x, y): x와 y 두개의 원소를 하나의 그룹으로 만드는 역할 ..

깊이우선탐색의 개념 1) 루트 노드(또는 임의의 노드)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 직전의 갈림선이 있는 정점을 되돌아가야 하기 때문에 재귀적으로 구현하거나, 후입선출 구조의 스택을 활용 ; 시작 정점의 한 방향으로 갈 수 있는 가장 깊은 경로까지 탐색하다가 끝을 만나면 직전의 갈림선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 탐색하는 방법 깊이우선탐색의 특징 1) 자기 자신을 호출하는 순환 알고리즘의 형태이다. 2) 위와 같은 이유로 방문한 노드는 그 여부를 반드시 검사해야 무한 루프에 빠지지 않는다. 3) 전위 순회, 중위 순회, 후위 순회 모든 형태의 트리 순회는 모두 DFS의 한 종류이다. 4) 인접 행렬 또는 ..

너비우선탐색 개념 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 그 시작점과 인접한 정점을 다시 차례로 방문하는 방식을 말한다. 이 때 방문했던 인접 정점도 순서대로 다시 인접 정점을 탐색해야 하므로 선입선출 형태의 자료구조인 Queue(큐)를 활용한다. 방문 여부 검사를 통해 무한루프에 빠지지 말아야 한다. 너비우선탐색 특징 1) 시작 노드로부터 단계적으로 거리에 따라 탐색한다. 2) 재귀적으로 작동하지 않는다. 3) 프림 및 다익스트라 알고리즘과 유사하다. 구현 방식1) 인접행렬 두 정점이 연결되어 있는 여부를 한 눈에 확인 가능하나, 시간도 많이 사용하고 메모리 낭비가 심하다. 들어오고 나가는 간선이 한 눈에 보이기 때문에 간선이 많을 때(밀집 그래프)..

그래프의 개념 - 아이템들과 이들 사이의 연결관계를 표현하는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조 - 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가진 원소들을 표현하기에 편리함 - 정점: 그래프의 구성요소로서 하나의 연결점 - 간선: 두 정점을 연결하는 선 - 차수: 정점에 연결된 간선의 수 그래프의 종류 무향 그래프 유향 그래프 가중치 그래프 사이클 없는 방향 그래프(Directed Acyclic Graph) 완전 그래프: 정점들에 대해 가능한 모든 간선을 가진 그래프 부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프의 표현 1) 인접행렬: 2차원 배열 이용하여 간선 정보 저장 희소 그래프인 경우, 즉 정점 수 대비 간선 수가 ..