kark's

브루트 : 무식한명칭처럼 무식하게 탐색하는 알고리즘이다. 문제를 해결하기 위해 모든 경우의 수를 확인해본다 라고 생각하면된다.그럼 완전탐색 알고리즘과 백트레킹 알고리즘과 거의 유사해 보이지만, 브루트포스는 그냥 완전히 확인하는 것이라 생각하면 된다. 모든 경우의 수를 확인하는 점은 최적의 결과를 반환시켜 주지만, 반대로 시간이 오래걸린다는 점이 단점이 된다. 브루트포스 : 모든 탐색을 진행완전탐색 : 모든 탐색을 진행하지만 가능하다면 조건을 활용해 불필요한 탐색을 제거백트레킹 : 명확한 조건을 두어, 불필요한 탐색을 제거하는 가지치기 방식 예시 문제https://www.acmicpc.net/problem/2798주어지는 카드들로 3장의 카드를 골라서 주어지는 값에 가장 근접하게 만들어 내야한다.대신 반드..

라우팅 알고리즘은 네트워크에서 데이터 패킷이 목적지까지 가장 효과적으로 전달될 수 있게 최적의 경로를 결정하는 알고리즘이다. 라우팅 알고리즘의 여러가지 방식1. 정적 라우팅과 동적 라우팅 - 정적 라우팅경로가 미리 설정 고정되어 있어 관리자가 직접 경로를 설정한다.네트워크 환경이 변하지 않는 경우에 적합하지만 이후 변화에 대응하기가 어렵다. - 동적 라우팅네트워크 상태에 따라 경로가 자동으로 변경된다.라우팅 프로토콜을 통해 실시간으로 네트워크 상태 정보를 교환하여 최적 경로를 선택할수 있다.정적 라우팅에 비해 상태 변화에 쉽게 대응이 가능하며 유연성이 높다.2. 거리 벡터 알고리즘과 링크 상태 알고리즘- 거리벡터 알고리즘각 라우터가 인접한 라우터와 정보를 교환하고 최단 경로를 바탕으로 목적지까지의 거리와..

문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 조건 수열의 크기 1 = right) break; mid = (right + left) / 2; if(lis[mid] = arr[i]) lis[left] = arr[i]; } } System.Console.WriteLine(lis.Count); 미흡하거나 개선될수 있는 부분이 있다면 답글 ..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 조건 수열의 크기는 1

해당 카테고리는 가장 긴 부분수열만 다룰예정 위와같은 수열이 있을때 가장 길게 증가하는 수열은 10 20 30 50 으로 이루어진다. 이처럼 여러 문제의 조건에 따라 어떻게 접근하는지에 대해 정리해볼 예정이다.

동적 계획법은 복잡한 문제를 여러개의 간단한 문제로 분리해 부분문제를 해결함으로 복잡한 문제의 답을 구하는 방법을 의미한다. 핵심 이론은 ① 큰 문제를 작은 문제로 나눈다. ② 작은 문제들이 반복되고, 작은문제들의 결과값은 항상 같아야한다. ③ 모든 작은문제는 한번만 계산돼 DP 테이블에 저장한 뒤 재사용할때는 이 테이블을 이용한다 동적계획법에는 두가지 방식 탑다운 방식과 , 바텀업 방식으로 나눠진다. 탑다운 문제를 파악하고 점차 내려오는 방식으로, 주로 재귀함수 형태로 코드를 구현한다. 이 방식은 코드의 가독성이 좋고, 이해하기 편한 장점이 있다. int[] memo; int Fibo(int n) { if (memo[n] != -1) return memo[n]; if (n

메모이제이션은 동적 프로그래밍 기법의 일환으로, 이전에 계산된 결과를 저장해두고 필요할때 재사용해 중복 계산을 피하는 최적화 방법이다. 예로, 재귀적으로 피보나치의 수를 구할때 같은값을 여러번 계산하는 것을 메모이제이션으로 방지할수 있다. 기본 재귀함수의 경우 어떠한값이 필요할때 비효율적인 중복되는 계산을 여러번 처리해야한다. 메모이제이션 기법을 사용함으로써 한번 계산된결과를 저장해둔 뒤에 똑같은 계산결과가 필요할때 계산과정을 거치지 않고 필요한 값을 바로 불러오는 방법이다. 이처럼 눈에 보이는 장점과 단점이 있는데, 장점이라면 피보나치의 수처럼 계산 비용이 높은 경우 프로그래밍의 성능을 개선시킬수 있다는점 단점이라면 추가적인 메모리가 필요한점이다. 사용해야하는경우는 비용과 이익을 고려해봐야 하겠지만 보..

이진트리란 하나의 노드가 있을때, 자식노드가 2개 이하인 트리를 말한다. 자식노드가 3개라면 이진트리라 부를수 없다. 트리를 사용하는 이유는 데이터를 계층적으로 구성하며 효율적으로 관리하기 위해 사용된다. 계층적 구조를 이룸으로써 빠른 검색, 삽입, 삭제가 가능하다. 이러한 트리구조에서 모든 노드를 빠르게 확인하거나, 처리를 하기위해선 순회 방법을 알아야한다. 순회 방법으로는 전위순회 중위순회 후위순회가 있다. 전위순회 Preorder , 중위순회 Inorder , 후위순회 , Postorder 각 접두사를 확인해보면 Pre, In, Post 로 앞에 , 안에 , 뒤에 로 유추할수 있다. 단어의 각 위치는 트리의 Root의 위치를 의미한다. 위와 같은 간단한 트리가 있을때, Root는 A 로 Left는 ..

함수 안에서 자기 자신의 함수를 호출되는 형태를 의미 재귀를 사용함으로 복잡한 문제를 간단하게 해결할수 있다. 재귀함수는 반복적인 작업을 수행할때 반복문을 사용하는 대신 자기 자신을 호출해 문제를 해결한다. 재귀 함수는 보통 2개의 단계로 구성된다. ① 기저조건 재귀호출을 멈추는 조건을 의미 이 조건이 없다면 함수는 무한하게 호출되므로 프로그램이 정상적으로 작동되지 않는다. ② 재귀단계 자기 자신을 호출하는 부분이다. 이구간을 통해 문제의 규모를 줄여가며, 최종적으로 ① 기저조건을 만나 재귀 호출이 종료되게된다. 장점 복잡한 문제를 간결한 코드로 작성할수 있으며 반복문보다 좀더 직관적일수도 있다. 단점 호출이 많아지면 스택 오버플로우가 발생될수있음 깊은 재귀의 경우 스택 메모리사용량이 증가된다. 시각화와..

프림 알고리즘또한 MST 를 해결하는 알고리즘이다. 이 알고리즘의 특징은 그리디한 방식으로 문제를 접근하며, 프림 알고리즘은 어떠한 자료구조를 사용하는지에 따라 효율성이 달라진다. Priority Queue 를 활용하면 간선의 선택을 효율적으로 할수있고 이경우 시간복잡도는 O((V+E log V)) 가 된다. ① 시작 정점을 기반으로 인접한 정점을 확인한뒤 우선순위 큐에 가중치 기준으로 데이터를 넣어준다. 이때 시작 정점은 방문된 상태라고 표기해준다. ② 큐에서 추출된 정점을 방문으로 표기해준뒤 인접한 정점을 확인한뒤 ①의 과정과 마찬가지로 큐에 넣어준다. ③ 위 과정을 반복하며 모든 정점을 방문하게 되면 MST가 구해진다. 시작 1번 정점으로 부터 인접한 정점과 가중치를 확인 큐에 넣어주고 1 정점은 ..