tonirr

탐색의 개념 여러 데이터 중에서 원하는 값을 가진 데이터를 찾는 것 데이터 형태 -> 리스트, 트리, 그래프 등 내부탐색 vs 외부탐색 연산 -> 탐색 + 초기화(정렬), 삽입, 삭제 등 순차 탐색 리스트 형태로 주어진 원소들에 대해서 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법 탐색 실패의 경우 -> 항상 n번 비교 O(n) 탐색 성공의 경우 -> 최소 1번 ~ 최대 n번 비교 O(n) 삽입 -> O(1) 삭제 -> O(n) 삭제할 데이터에 대한 탐색이 필요 특징 모든 리스트에 적용 가능 원소가 무순서로 연속해서 저장된 비정렬 데이터 탐색에 적합 데이터가 큰 경우에는 부적합 탐색과 삭제 -> O(n) 이진 탐색 개념과 원리 정렬된 배열 형태로 주어진 원소들을 절반씩 줄여가면서..

합병 정렬과 퀵 정렬 주어진 배열을 동일한 크기의 두부분 배열로 분할 정렬된 두 부분 배열을 합쳐서 하나의 정렬된 배열을 만듦 합병 정렬의 성능과 특징 최선/최악/평균 수행 시간이 모두 O(nlogn) 안정적인 정렬 알고리즘 퀵 정렬 퀵정렬의 성능과 특징 최악 수행 시간 O(n^2), 최선/평균 수행 시간 O(nlogn) 피벗 선택의 임의성만 보장되면 평균 성능을 보일 가능성이 매우 높음 제자리 정렬 알고리즘 안정적이지 않은 정렬 알고리즘 힙 정렬 힙 자료구조의 장점을 활용한 정렬 (최대)힙 완전 이진 트리 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다. 힙의 장점 임의의 값 삽입과 최대값 삭제가 용이 힙의 구현 일차원 배열 부모노드: i 자식노드: 2i+1(왼쪽 노드), 2i+2(오른쪽 노드)..

정렬의 개념 정렬이란 주어진 데이터를 값의 크기 순서에 따라 재배치 하는 것 정렬수행시점에 데이터가 어디에 저장되어 있는가? 내부정렬 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식 비교 기반 알고리즘 버블정렬, 선택정렬, 삽입정렬, 셸정렬 O(n^2) 합병정렬, 퀵정렬, 힙정렬 O(nlogn) 데이터 분포 기반 알고리즘 계수 정렬, 기수 정렬 O(n) 외부 정렬 모든 데이터를 주기억장치에 저장할 수 없는 경우 모든 데이터를 보조기억장치에 저장한 채 그중 일부데이터씩 반복적으로 주기억장치에서 읽어들여서 정렬하는 방식 안정적 stable 정렬 동일한 값을 갖는 데이터가 여러개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식 제자리 in-place 정렬 입력 데이터를 저장한 공..

최단경로 가중방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로 플로이드 알고리즘 모든 정점 간의 최단 경로 동적 프로그래밍 방법 적용 O(|V|^3) 가중치의 합이 음수인 사이클이 없다고 가정 플로이드 Floyd 알고리즘 다익스트라 Dijkstra 알고리즘 모든 정점 간의 최단 경로 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 (단일 출발점 최단 경로) 동적 프로그래밍 방법 적용 그리디 방법 적용 O(|V|^3) O(|V|^2) 가중치의 합이 음수인 사이클이 없다고 가정 음의 가중치를 갖는 간선이 없다고 가정 다익스트라 알고리즘 거리 d[v] 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 출발점에서 시작하여 거리 d[..

해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구함 greedy -> 탐욕적 방법, 탐욕 알고리즘, 그리디 알고리즘 동적 프로그래밍 방법 그리디 알고리즘 최적화 문제 해결에 주로 사용 최적성의 원리가 적용된 방법 소문제의 여러 최적해로부터 다음 크기의 문제에 대한 최적해가 결정 -> 항상 전체적인 최적해를 구함 소문제(각 단계)에 대해서 하나의 최적해만을 고려 -> 전체적인 최적해를 구하지 못할 수도 있음 그리디 알고리즘 방법의 원리 그리디 알고리즘의 한계 예를들어 가장 멋진바지, 가장 멋진 넥타이, 가장 멋진 자켓을 입는다고 할 때 그런 옷을 입은 멋쟁이씨는 과연 세상에서 가장 멋쟁이라고 할 수 있..

www.acmicpc.net/problem/1952 1952번: 달팽이2 M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다. 위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int [][]arr = new int[m][n]; int max = m * n; int x = m; ..

package baekjoon; import java.util.Scanner; public class Dalpaeng { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int size = sc.nextInt(); int tsize = size; int n = sc.nextInt(); int max = size * size; int [][] arr = new int[size][size]; int j = 0; int i = -1; int count = 1; while(true) { for(int t = 1; t

두 문자열 X와 Y사이의 편집 거리 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도 X = x1x2x3 ... xn, Y = y1y2 ... ym 문자열 X를 Y로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용 특정 위치에 새 문자를 삽입하는 연산 -> 삽입 비용 특정 위치의 문자를 삭제하는 연산 -> 삭제 비용 특정 위치의 문자를 다른 문자로 변경하는 연산 -> 변경 비용 최적성의 원리 X와 Y사이의 편집거리는 이들의 부분 문자열 사이의 편집 거리를 포함 Xi = x1x2 ... xi와 Yi = y1y2 ... yj 사이의 편집 거리 성능 삭제할 때 성능: O(n) 삽입할 때 성능: O(n) 변경할 때 성능: O(nm) P(i, j) E(i, j)로 선택되는 최소값이 어떤 연산으로 결정되는..