본문 바로가기

기타/자료구조, 알고리즘17

[자료구조, 알고리즘] 리스트#3 - js로 CircularLinkedList 구현, 자바로 생각해보기 [연결리스트]- 메모리 상에서는 떨어져있는 데이터 : 각각 연결하여 1열의 개념의 데이터 저장공간을 만듦- 핵심(1) node : 현재 데이터와 현재와 연결된 다음 데이터를 가리키는 주소를 함께 저장 - node -> data, next(2) node 간 어떻게 연결할 것인가, 연결되어져있는 node 탐색방법 - 연결 형태에 따라 단순/원형/양방향 연결리스트 나뉨 [원형 연결리스트]- 단순 연결리스트와 마찬가지로 단방향 : 역방향까지 지원하는 양방향 연결리스트는 다음 포스팅!- 처음 추가된 node와 마지막 node가 연결되어 원형을 띔 - 단순 연결리스트는 head -> tail node로 가기위해 tail에서 next node로 순차탐색=> 위의 그림처럼 head를 둬도 되지만, 원형 연결리스트의 특.. 2017. 9. 6.
[자료구조, 알고리즘] 리스트#2 - LinkedList 구현, syntax + develop tip [연결리스트 특징 및 구현할 때 생각해야할 것]- ArrayList는 배열(array)로 구현된 List, 연결리스트는 메모리에 동적으로 할당되는 데이터들을 하나의 리스트로 만듬- Node 인스턴스(object)를 동적으로 할당하되 하나의 리스트로 엮음 : LinkedList- 구현하면서 가장 중요하게 생각해야하는 것 : node간 연결방법, node를 순차적으로 탐색하는 방법 [자바스크립트로 LinkedList 구현하기(feat. 자바스크립트 프로토타입 기반 객체지향)]- node를 head로만 추가함=> head 와 tail 추가하는 방법을 구현하면됨=> 중간 node를 제어하는 방법도 생각해봅시다 : setRuleList 추가 - LinkedList 객체 : 추상화, private / public .. 2017. 9. 1.
[자료구조 알고리즘] 리스트#1 - ADT, ArrayList js구현, syntax tip [리스트 특징]- 1열에 나란히 데이터를 저장함 : 1줄로 연결된 형태, 탐색- 중복된 데이터를 허용함 - 데이터 참조가 쉬움, 내부적으로 index를 기반으로 first / next 동작 - 삭제 과정에서 이동이 빈번하게 일어남, 외부적으로는 index를 기준으로해서 옮기는 것이 아니라 first / next 함수를 호출해서 cursor를 움직임=> 탐색이 빈번하게 일어나는 기능에서 자료를 저장하는 구조로서는 부적합 [리스트 구현방법에 따른 종류]- 주의할 점 : 구현 방법에 따라 나눈 것이지 ADT가 다른 것이 아님- 순차리스트 : 배열을 가지고 구현한 리스트- 연결리스트 : 메모리 동적할당을 가지고 구현한 리스트 [C로 배운 리스트 자바스크립트로 구현하기]- 어차피 ADT가 달라지는 것도 아니고, .. 2017. 8. 26.
[자료구조, 알고리즘] 재귀호출 - 헷갈리면 모르는것 [특징 및 이해할 때 필요한 개념](1) 재진입 개념이 아닌 복사본 개념 : 스택에 쌓인 함수는 각각의 함수(2) 반복 : 이전의 연산에 기반해서 현재의 것을 연산할 때 사용 : 함수에서 함수를 호출=> 동일 패턴 반복 (3) 문제 -> 논리 세우기 -> 코드화 / 패턴화(함수, 0 - 1 - ---- - n-1 - n - n+1)(4) 메모리(코드) - CPU(연산) : 언어 런타임 별 메모리 할당 구조 살펴보기(5) 함수 호출 관계 - 순서 한번쯤 따져보기=> 호출한 함수가 모두 끝난 후(return) 되돌아와서 실행=> 수학의 함수 개념 : 정의역, 공역, 치역(특정 값을 도출해내기위한 패턴) (6) 성능상 좋지않으나(재귀 두갈래 이상 out of memory 조심) 간결한 코드 [예시](1) 팩토.. 2017. 8. 21.
[자료구조 알고리즘] 재귀 호출 : 논리를 코딩하기 [재귀함수 호출]- S(n) 결과값 도출을 위해 S(n-1)이 필요할 때 재귀 호출을 사용 => 패턴화를 위해 예시 경우의수 2~3가지를 대입해서 실행해보고 패턴화해서 코드로 짜기 123456789101112void Recursive(int num) { if(num 복사본(Recursive) -> 복사본(Recursive) -> 복사본(Recursive) => 원본의 복사본 실행 => 명령문 실행 : 명령문은 CPU로 이동(복사)되어 실행 => 메모리(스택)에 이전 함수(복사본)의 주소가 저장 : 마지막 호출된 복사본이 종료되면 이전 함수(복사본)으로 돌아감 - 재귀 함수 탈출 조건 : 끝남 조건, 무한루프 X => OutOfMemory - 반복문을 간결하게 작성함 : 함수를 스택에 쌓고 연산하는 것보다.. 2017. 7. 31.
[자료구조 알고리즘] 자료구조, 알고리즘, 함수(패턴), 빅-오 표기 [자료구조와 알고리즘]- 프로그램 : 데이터 표현(자료구조)하고, 표현된 데이터를 처리(알고리즘)하는 것임=> 어떤 자료구조를 사용했을 때 효율적(알고리즘 : 시간, 공간)으로 처리할 수 있을 것인가?=> 어떤 결과값을 리턴해내야하는가 : 어떤 결과가 필요한가부터 정하고 => 반 학생(36명) 중 아침을 먹고온 사람이 있는지 없는지 체크할 때 : 배열, 순차탐색 알고리즘 (1) 선형구조 : 리스트, 스택, 큐(2) 비선형구조 : 트리, 그래프(3) 파일구조 : 순차파일, 색인파일, 직접파일(4) 단순구조 : 정수, 실수, 문자, 문자열 - 알고리즘 맛 보기(1) 순차탐색알고리즘12345678int LSearch(int arr[], int len, int target){ for(int i=0; i 주변에 .. 2017. 7. 24.
[자료구조 알고리즘] 공부를 시작하기에 앞서서 - 왜 필요한가 [알고리즘 공부가 필요한 이유]- 문제를 인식할 수 있는 능력 - 문제 해결 방법을 생각하는 능력- 문제 해결 방법을 구현하는 능력 관찰하는 자세(사람 만나고 어떤 일들이 일어나는지 여러 매체를 통해 관심을 가져보고 직접 겪은 일들에 대해서도 생각해보고)해결 방법을 찾는 훈련(알고리즘)구현 하는 능력(프로그래밍 - 자료구조) 3박자를 고루 가지고 있어야 실력 있는 프로그래머가 아닐까싶다. 이제 공부를 시작하겠습니다.재미부터 붙이고 - 백준의 누워서 읽는 알고리즘부터 2017. 7. 6.

티스토리툴바