본문 바로가기

분류 전체보기590

그래프, DFS, BFS 그래프의 정의 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때, G = (V, E)이다. 정점 사이의 인접 관계를 나타내는 방법에는 크게 두 가지가 있다.행렬을 이용하는 방법은 인접 행렬(Adjacency Matrix)이라 하고 리스트를 이용하는 방법은 인접 리스트(Adjacency List)라고 한다. 인접 행렬 장점 : vertex간의 인접 여부를 빠르게 알 수 있다.단점 : 정점의 크기 * N^2 만큼의 메모리가 사용된다. 그래프 순회DFS (깊이 우선 탐색)1. 시작 정점을 밟은 후 이 정점을 ‘방문했음’으로 표시한다.2. 그리고 이 정점과 이웃하고 있는 정점(인접 정점) 중에 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼아 다시 깊이 우선 탐색을 시작한다. 즉 1단계를.. 2018. 3. 18.
탐색 알고리즘 바이너리 서치정렬된 데이터 집합에서 사용할 수 있는 ‘고속’ 탐색 알고리즘데이터 집합이 배열인 경우에만 사용할 수 있다. 1. 데이터 집합의 중앙에 있는 요소 선택2. 요소의 값과 찾고자 하는 목표 값을 비교3. 찾고자 하는 값이 작다면 요소의 값 왼쪽 데이터 집합에서 1~2 실행, 크다면 오른쪽 데이터 집합에서 1~2 실행 4. 찾고자 하는 값을 찾을 때까지 1~3번 과정 반복 int BinarySearch(int DataSet[], int Size, int target){int mid = 0;int left = 0;int right = Size - 1; while (left 해더파일의 중복 선언 문제를 예방하기 위해서 쓰는 전처리문이다.*/ #include #include typedef int Ele.. 2018. 3. 14.
정렬 알고리즘(퀵 정렬, 삽입 정렬, 계수 정렬) 삽입 정렬 알고리즘 #include #include void insertionSort(int DataSet[], int Length ){int i = 0;int j = 0;int value = 0;for (i = 1; i < Length; i++){if (DataSet[i - 1] value){//배열에서 한칸씩 값 옮기기memmove(&DataSet[j + 1], &DataSet[j], sizeof(DataSet[0]) * (i - j));DataSet[j] = value;break;}}}} int main(){int DataSet[] = { 6, 4, 2, 3, 1, 5 };int Length = sizeof DataSet / sizeof DataSet[0];int i = 0; insertionSor.. 2018. 3. 14.
백준 1697 숨바꼭질 import java.util.Scanner; public class testPorject{static int N, K;public static void main(String[] args){Scanner sc = new Scanner(System.in);N = sc.nextInt();K = sc.nextInt();move(N);sc.close();}private static void move(int location){//queue에는 변동 후 위치를 저장하고, visit 배열에는 몇번째에 방문하는지를 저장한다.int[] visit = new int[200001];Queue queue = new Queue(200001);visit[location] = 1;queue.push(location);while(!.. 2018. 1. 13.

티스토리툴바