프로그래밍/Algorithm & Structure (6) 썸네일형 리스트형 20.01.06) DataStructure - LinkedList(ongoing) 목차 연결리스트란? 연결리스트 구현 코드 핵심 연결리스트는 배열의 삽입과 삭제를 보완한 자료구조이다. 연결리스트란? 연결리스트는 각 원소가 포인터로 연결되어 있는 자료구조를 말한다. 왜 태어났을까? 배열이 가진 단점을 보완하기 위해 등장했다. 배열은 원소의 삽입과 삭제 시 그 뒤에 있는 원소들이 줄줄이 움직여야 한다. 그렇기에 삽입과 삭제시 선형 시간 복잡도를 가진다. 연결리스트는 이런 배열의 단점을 포인터로 극복한다. 각 원소는 메모리에서 따닥따닥 붙어 있지 않다. 각 원소는 이전 혹은 이후 원소의 주소를 참조한다. 주소를 참조하기 때문에 메모리에 따닥따닥 붙어있지 않는다. 그러면 삽입과 삭제의 시간이 단축될까? 그렇다. 삽입과 삭제시 주변 원소의 포인터를 조정해주면 된다. 그러면 상수 시간 복잡도를 .. 19.12.25) Algorithm - Recursive Blob 출처 : KOCW 부경대학교 권오흠 교수 알고리즘 강의 참고 목차 Counting cells in a blob 입력과 출력 문제에 대한 재귀적 사고핵심 연습! 연습! Counting cells in a blob 이 문제는 2차원 그리드에서 하나의 좌표가 주어지면 그 좌표를 포함하고 있는 blob이 몇 개의 픽셀로 이루어져 있는지 리턴하는 문제다. 만약 blob에 속해져 있지 않은 좌표라면 0을 리턴한다. Blob 이미지 참조 입력과 출력 입력 N * N 크기의 2차원 그리드 하나의 좌표 (x, y) 출력 픽셀 (x,y)가 포함된 blob의 크기 (x,y)가 어떤 blob에도 속하지 않은 경우에는 0 문제에 대한 재귀적 사고 현재 픽셀이 속한 blob의 크기를 카운트 하려면 현재 픽셀이 image colo.. 19.12.25) Algorithm - Recursive Maze 출처 : KOCW 부경대학교 권오흠 교수 알고리즘 강의 목차 미로찾기 재귀적 사고 Psudocode 핵심 연습! 연습! 미로찾기 재귀적 사고 현재 위치에서 출구까지 가는 경로가 있으려면 현재 좌표가 출구거나 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구로 가는 방법이 있거나. Psudocode boolean findPath(x, y) { if (x,y) is either on the wall or a visited cell return false; else if (x,y) is the exit return true; else mark (x,y) as a visited cell; for each neighbouring cell (x', y') of (x,y) do if findPat.. 19.12.25) Algorithm - Design recursion 목차 재귀 알고리즘 기본 조건 매개변수를 암시화(implicit)하지말고 명시화(explicit)하라핵심 재귀 알고리즘 구현할 때 매개변수를 명시화하라. 재귀 알고리즘 기본 조건 프로그램이 끝나는 base case가 있어야 한다. 재귀 알고리즘 영역이 base case로 수렴해야 한다. 매개변수를 암시화(implicit)하지말고 명시화(explicit)하라 왜? 재귀 알고리즘을 사용할 땐 자기 자신이 다시 호출되는 상황이 발생한다. 그 때 명시화된 매개변수는 호출할 때 다시 사용되기 때문이다. 한마디로 재귀 알고리즘 구현할 때 편해진다. 순차탐색(linear search) // Iterative linear search public static int IterLinearSearch(int[] arr, i.. 19.12.24) Algorithm - recursive thinking 목차 재귀적 사고 간단한 재귀 함수들핵심 재귀적 사고도 프로그램을 바라보는 관점 중 하나이다. recursive thinking(재귀적 사고) 절차 지향 프로그램, 객체 지향 프로그램처럼 프로그램을 바라보는 관점 중 하나이다. 간단한 재귀 함수들 문자열의 길이 구하기 // 문자열의 길이 구하는 재귀 함수 private static int printLength(String str) { if (str.equals("")) return 0; else { return 1 + printLength(str.substring(1)); } } 문자열의 프린트 // 문자열 프린트하는 재귀 함수 public static void printChars(String str) { if (str.length() == 0) retu.. 19.12.23) Algorithm - recursion 목차 Recursion이란? 다양한 재귀 함수핵심 재귀는 원리를 이해하면 구현이 편해진다 Recursion(재귀) 재귀의 의미는 자기 자신을 다시 부르는 것을 의미한다. 함수에 적용하면 자기 자신을 다시 호출하는 함수를 말한다. 재귀 함수는 base case가 있어야 함수가 종료될 수 있다. 없다면 무한 루프를 만든다. 하지만 base case만 있다고 종료되는 것은 아니고 recursive case가 base case로 수렴해야 한다. 다양한 재귀 함수 0 ~ n까지의 합 구하기. 0 ~ n 까지의 합 = (0 ~ n-1 까지의 합 + n)이다. n = 0 이면 결과는 0이다. 이걸 코드로 구현해보자. 포인트는 n까지 합을 구하기 위해선 n-1까지 합과 n이 더해진다는 점 이게 다른 재귀 함수에도 적용.. 이전 1 다음