Devjo의 코딩

그래프 이해 알고리즘: 그래프(Graph)의 탐색과 메소드 이해&구현 그래프와 트리의 차이 사이클의 유무이다. 노드를 출발해 간선의 방향으로 따라 출발한 노드로 다시 돌아올... blog.naver.com 문제 예시: 백준 2178 번 문제링크 배열 안에서 경로의 최소값을 구하는 문제입니다. 어떤 방식을 생각할 수 있을까요? ​ 1. DP (Dynamic Programming) 연속된 무언가의 최소값이나 최대값을 구할 때 가장 먼저 떠오르는 키워드 중 하나는 DP일 것입니다. 여기서는 다루지 않고 넘어가겠습니다! ​ 2. DFS (깊이 우선 탐색) 방문정점 구하기 그래프를 배우기 전에는 2차원 배열은 단순히 2차원에 값을 저장하는 도구입니다. 하지만 그래프를 학습하면서 DFS와 BFS 탐색법을 배우고 그..

그래프와 트리의 차이 사이클의 유무이다. 노드를 출발해 간선의 방향으로 따라 출발한 노드로 다시 돌아올 수 있다면 사이클이 존재한다고 한다. 하나의 사이클이라도 존재한다면 트리가 될 수 없다. 즉 그래프는 트리를 포함하는 개념이다. ​ 그래프 노드(=정점)와 간선으로 이루어진 자료구조를 뜻한다 ​ 구분 간선에 방향을 표기한 단방향 그래프 연결관계만 표기한 무방향 그래프 ​ 행렬화 노드와 노드의 연결관계를 행렬로 표현해 연산효율을 높힌다 ​ 예시 A에서 두 번 움직여서 갈 수 있는 곳은? = 위 행렬을 제곱한다 ​ 위 행렬에서 필요한 정보 1. A에서 갈 수 있는 노드를 구한다 = A에서 갈 수 있는 노드는 B이다 ​ 2. 다시 B에서 출발해 도착할 수 있는 곳을 구한다 = 총 2 곳 일반화 행렬을 n제곱..

문제) 12와 20의 최대공약수를 구하시오 어떻게 푸시나요? ​ 보통 나눗셈을 합니다 최대공약수 = 2X2 = 4​ 하지만 주어진 두 수가 엄청 크다면 어떤 수로 나눠야할지 일일히 찾아야하기 때문에 컴퓨터 연산에서는 비효율적입니다 ​ ​ 최대공약수 A와 B의 나머지 연산으로 최대공약수를 구한다 ​ 두 수(12, 20)만으로 최대공약수를 구해봅시다​ 20 % 12 = 8 (20을 12로 나눈 나머지) 12 % 8 = 4 (12를 8로 나눈 나머지) 8 % 4 = 0 (나머지가 0일 때 그 수는 최대공약수) ​ 논리가 매우 단순해졌죠??​ 메소드로 만들면 다음과 같습니다 static int GCD(int A, int B) { //B를 A로 나눈 나머지를 구합니다 if(A==0)return B; // 마지막 ..

백트래킹 해를 찾는 중에 현재 선택한 루트(노드)가 해와 관련이 없다는 것을 알아차리면 중단하고(가지치기) 이전 단계로 돌아가 다른 루트를 탐색한다 해가 될 수 있는 노드(유망한 노드)만을 이용해 부분 탐색을 수행한다 ​​ DFS 깊이 우선 탐색(Depth-First-Search), 맨 위 노드(루트)에서 하나의 가지(branch, 분기)를 완전히 탐색하고 다음 가지(분기) 넘어가는 방법 전체 탐색을 전제로 한다 ​ DFS의 사용 자기 자신을 호출(재귀 호출)하는 순환 알고리즘 형태이다 무한 루프에 빠지지 않기 위해 방문했다는 기록을 남겨준다 ​ 예시 위의 트리를 탐색하는 메소드를 논리로 만들어보자(전위순회) 1. 현재 위치를 탐색하고 왼쪽 아래 노드로 이동합니다 2. 만약 왼쪽 아래 노드가 없거나 방문..

안정 정렬 Stable sort, 정렬 전의 순서를 유지하고 정렬된다 삽입(Insertion) 정렬, 버블(Bubble) 정렬, 병합(Merge) 정렬이 있다 삽입 정렬 두번째 자료부터 시작해 자신보다 앞 자료들과 크기를 비교해 알맞은 자리에 끼워넣는다 버블 정렬 서로 인접한 자료들을 계속해서 정렬해준다. 1번 회전이 될 때 가장 큰 수가 맨 오른쪽에 위치한다 병합 정렬 현재 배열을 두 개로 나눈 뒤 각각 정렬을 수행한다. 정렬된 두 배열의 처음 값들을 비교해 작은 값을 먼저 원래 배열에 넣어준다 위의 예시는 원리를 설명하기 위한 병합정렬의 맨 마지막 과정이다. 자세히 보면 크기가 4인 배열들이 이미 정렬되어 있다. 크기가 4인 배열을 정렬하기 위해 크기가 2인 배열로 나누고 다시 크기가 1인 배열로 나..

그리디 알고리즘 greedy(욕심많은, 욕심쟁이의) 알고리즘 뜻 그대로 선택의 이후를 고려하지 않고 순간 순간마다의 최적의 해를 찾는 방식이다 그리디 알고리즘의 이해 그리디 알고리즘은 동적 계획법을 보완하는 개념이다 브루트 포스, 동적 계획법 그리고 그리디 알고리즘을 비교한다 위 그림을 참고해 서울 → 부산을 가는 최소 경로를 구해보자 브루트 포스, 동적 계획법, 그리고 그리드 알고리즘을 토대로 구해볼 것이다 브루트 포스 서울에서 부산으로 갈 수 있는 모든 해를 구한다(왼쪽부터) 250km + 100km / 80km / 120km 200km + 100km / 80km / 120km 300km + 100km / 80km / 120km 위 9개의 값 중 최소값인 280km를 결과로 반환한다 동적 계획법 1항..

동적 계획법 Dynamic Programming 또는 DP라고 부른다 1940년대 리차드 벨만이 사용하던 용어이다. 어떤 문제가 주어질 때 본래의 문제를 분석하고 반복되는 연산을 찾아낸다 연산을 기준으로 문제를 작은 문제들로 나눈 다음 각 문제들의 결과값을 기록하며 본래의 문제의 해답을 구하는 방법이다 단계를 구체화하면 다음과 같다 문제 ➡ 점화식 발견 ➡ 작은 문제들로 나누기 ➡ 각 문제의 해답을 기록 ➡ 해답 피보나치 수열 피보나치 수열을 통해 동적계획법을 이해한다 점화식 발견, 연산한 값을 기록하는 것이 dp의 핵심이라 볼 수 있다 피보나치 수열의 0항과 1항은 1이고 n항은 다음과 같이 표현된다 f(n) = f(n-1) + f(n-2) dp를 사용하지 않고 피보나치 특정항을 구해보자 40항을 구하..

덱 Double-Ended Queue 큐의 양쪽에 데이터를 넣고 뺄 수 있는 자료구조 큐 또는 스택으로도 사용할 수 있다 덱의 분류 한 쪽으로만 입력이 가능한 덱 = Scroll 한쪽으로만 출력이 가능한 덱 = Shelf 덱은 인터페이스 Deque의 자료구조는 interface로 정의되어있다 그렇기에 이를 구현해주는 클래스를 같이 쓰는데 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등이 있다 Java에서의 덱(Double-Ended Queue) Deque는 입력 출력의 방향이 자유로운 만큼 많은 메소드가 존재한다 클래스 연결 큐와 마찬가지로 2개를 import 해주어야 한다 import java.util.ArrayDeque; im..

큐 먼저 들어간 것이 먼저 나가는 구조 FIFO(First In First Out) 상황으로 이해한다 a라는 일을 하고 있는데 a가 끝나면 b를 하라는 지시가 왔다 a가 끝나지 않은 상황에서 할 일을 모두 마치면 c를 하라는 지시가 왔다 a가 끝나지 않은 상황에서 할 일을 모두 마치면 d를 하라는 지시가 왔다 a가 끝났다. 다음의 할 일은? 큐는 보통 관모양으로 설명한다 관은 양쪽이 뚫려있다 a, b, c순으로 들어왔을 때 pop을 두번하면 c만 남는다 투 포인터, 슬라이딩 윈도우를 사용할 때 자주 사용하는 개념이다 큐의 활용 요세푸스 순열 요세프스 순열의 기원은 요세프스라는 인물이 유대-로마 전쟁시에 살아 남은 일화를 바탕으로 한다. 제1차 유대-로마 전쟁에서 예루살렘에서 갈릴리로 파견되어 갈릴리의 마..

스택 먼저 들어온것이 나중에 나오는 자료 LIFO(Last In First Out) 상황으로 이해 짱구아빠는 a라는 일을 하고 있다 이 일을 마치기 전에 b라는 일을 해달라고 연락이 왔다 b를 마치기 전에 c라는 일을 해달라고 연락이 왔다 c를 마치기 전에 d라는 일을 해달라고 연락이 왔다 d를 끝냈다. 짱구아빠가 다음에 할 일은? 스택은 컵모양으로 설명한다 컵모양으로 위 예시를 설명하면, 위에서부터 d, c, b, a가 된다 용어 정리 push: 스택에 값을 넣는 것 pop: 스택의 가장 위의 값을 제거 top: 스택 가장 위에 있는 값을 출력 사용 예시 인터넷 브라우저 인터넷 브라우저의 뒤로 가기, 앞으로 가기 기능은 스택을 이용해서 구현할 수 있다 역순 문자열 만들기 문자열을 스택에 순서대로 집어넣..