달력

8

« 2020/8 »

  •  
  •  
  •  
  •  
  •  
  •  
  • 1
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  •  
  •  
  •  
  •  
  •  


 

 

Selection Sort(선택정렬)

선택정렬(Selection Sort) 알고리즘은 반복적으로 특정 값을 정렬된 최종 위치에 배치시킴으로써 값들의 목록을 정렬한다. , 목록의 위치에 대해서 위치에 배치되어야 하는 값을 선택하고, 값을 곳에 배치하게 됩니다.

 


 

 

단계

설명


 

정렬되지 않은 데이터


 

3에서 시작합니다.

3 최소값에 넣고 오른쪽 방향으로 작은값이 있는지 비교해 갑니다.


 

오른쪽의 9 3보다 작지 않습니다.

그러므로 다음 오른쪽의 값과 비교를 진행하기 위해 넘어갑니다.


 

오른쪽의 6 3보다 작지 않습니다.

다음 비교를 위해 오른쪽으로 진행합니다.


 

1 3보다 작으므로 Minimum Value 집어넣고 3 1 1 3으로 서로 위치를 바꿔줍니다.

최소값이 변경되었으며 다시 오른쪽으로 진행하면서 비교합니다.


 

오른쪽의 2 1보다 작지않습니다.

다음 비교를 위해 오른쪽으로 진행해야 하지만 모든 요소를 순회했으므로 현재 비교는 종료됩니다.


 

다음 비교를 위해 비교값 위치를 다음으로 이동합니다.

어떤 값도 비교되지 않은 상태이므로 현재 값인 9 Minimum Value 됩니다.

비교를 위해 오른쪽으로 진행합니다.


 

오른쪽의 6 9보다 작습니다.

그러므로 Minimum Value 6으로 변경한

서로위치를 변경합니다.

다음 비교를 위해 오른쪽으로 진행합니다.


 

오른쪽의 3 6보다 작습니다.

그러므로 Minimum Value 3으로 변경한

서로위치를 변경합니다.

다음 비교를 위해 오른쪽으로 진행합니다.


 

오른쪽의 2 3보다 작습니다.

그러므로 Minimum Value 2 변경한

서로위치를 변경합니다.

다음 비교를 위해 오른쪽으로 진행합니다.


 

다음 비교를 위해 비교값 위치를 다음으로 이동합니다.

어떤 값도 비교되지 않은 상태이므로 현재 값인 9 Minimum Value 됩니다.

비교를 위해 오른쪽으로 진행합니다.


오른쪽의 6 9보다 작습니다.

그러므로 Minimum Value 6 변경한

서로위치를 변경합니다.

다음 비교를 위해 오른쪽으로 진행합니다.


 

오른쪽의 3 6보다 작습니다.

그러므로 Minimum Value 3 변경한

서로위치를 변경합니다.

모든 순회를 마쳤습니다.



 

다음 순회를 위해 위치를 오른쪽으로 이동합니다.

어떤 값도 비교되지 않은 상태이므로 현재 값인 9 Minimum Value 됩니다.

비교를 위해 오른쪽으로 진행합니다.

 



 

오른쪽의 6 9보다 작습니다.

그러므로 Minimum Value 6 변경한

서로위치를 변경합니다.

모든 순회를 마쳤습니다.


다음 순회를 위해 위치를 오른쪽으로 이동합니다.

어떤 값도 비교되지 않은 상태이므로 현재 값인 9 Minimum Value 됩니다.

비교를 위해 오른쪽으로 진행해야 하지만 비교할 값이 없으므로 선택 정렬을 종료합니다.

 

 

선택 정렬의 결과를 보면 1, 2, 3, 6, 9 정렬된 상태로 변경된 것을 확인할 있습니다.

 

 

 



Posted by codedragon codedragon

댓글을 달아 주세요



 

 

3차원 배열을 이용한 선형 리스트의 구현

 

분기별 XXX 판매량 리스트

 

1

년도\분기

1/4분기

2/4분기

3/4분기

4/4분기

2070

74

86

147

132

2080

175

209

251

312

 

2

년도\분기

1/4분기

2/4분기

3/4분기

4/4분기

2070

63

80

131

144

2080

169

178

239

320

 

 

2차원 배열로 구현

int sale[2][2][4] = {

{{74, 86, 147, 132},

{175, 209, 251, 312}},

{{63, 80, 131, 144},

{169, 178, 239, 320}}

};

논리적 메모리 구조

분기별 판매량 선형 리스트의 논리적 구조

 


 

 

물리적 메모리 구조

분기별 판매량 선형 리스트의 물리적 구조

3차원 배열의 물리적 저장방법은 두가지가 있습니다. (3차원 논리적 구조에 대해 1차원의 물리적 구조로 저장됩니다.)

 

 

 

 

3차원 배열의 물리적 저장 방법

3차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법을 사용합니다.

 

·       우선 순서 방법(Plane Major Order)

·       우선 순서 방법(Column Major Order)

 

 

우선 순서 방법(Plane Major Order)

3차원 배열의 번째 인덱스인 번호를 기준으로 사용하는 방법입니다.

sale[0][0][0]= 74, sale[0][0][1]= 86, sale[0][0][2]=147, sale[0][0][3]=132, sale[0][1][0]=175, sale[0][1][1]=209, sale[0][1][2]=251, sale[0][1][3]=312,

sale[1][0][0]= 63, sale[1][0][1]= 80, sale[1][0][2]=131, sale[1][0][3]=144, sale[1][1][0]=169, sale[1][1][1]=178, sale[1][1][2]=239, sale[1][1][3]=320,


 

면의 개수가 ni이고 행의 개수가 nj이고, 열의 개수가 nk 3차원 배열 A[ni][nj][nk],

시작 주소가 α이고 원소의 길이가 , i j k 원소

 

A[i][j][k] 위치 = α + {(injnk) + (jnk) + k}

 

ni

면의 개수

nj

행의 개수

nk

열의 개수

α

시작 주소

원소의 길이

 

 

 

 

 

우선 순서 방법(Column Major Order)

3차원 배열의 마지막 인덱스인 번호를 기준으로 사용하는 방법입니다.

sale[0][0][0]= 74, sale[1][0][0]= 63, sale[0][1][0]=175, sale[1][1][0]=169,

sale[0][0][1]= 86, sale[1][0][1]= 80, sale[0][1][1]=209, sale[1][1][1]=178,

sale[0][0][2]=147, sale[1][0][2]=131, sale[0][1][2]=251, sale[1][1][2]=239,

sale[0][0][3]=132, sale[1][0][3]=144, sale[0][1][3]=312, sale[1][1][3]=320,


 

A[i][j][k] 위치 = α + {(knjni) + (jni) + i}

 

ni

면의 개수

nj

행의 개수

nk

열의 개수

α

시작 주소

원소의 길이

 

 

 

메모리 주소 출력결과 확인하기

 

메모리 주소 출력결과

C 컴파일러가 우선 순서 방법으로 3차원 배열을 저장함을 확인할 있습니다.

sale[0][0][0]= 74

sale[0][0][1]= 86

sale[0][0][2]=147

sale[0][0][3]=132

sale[0][1][0]=175

sale[0][1][1]=209

sale[0][1][2]=251

sale[0][1][3]=312

sale[1][0][0]= 63

sale[1][0][1]= 80

sale[1][0][2]=131

sale[1][0][3]=144

sale[1][1][0]=169

sale[1][1][1]=178

sale[1][1][2]=239

sale[1][1][3]=320

address:6422236, sale  0 =  74

address:6422240, sale  1 =  86

address:6422244, sale  2 = 147

address:6422248, sale  3 = 132

address:6422252, sale  4 = 175

address:6422256, sale  5 = 209

address:6422260, sale  6 = 251

address:6422264, sale  7 = 312

address:6422268, sale  8 =  63

address:6422272, sale  9 =  80

address:6422276, sale 10 = 131

address:6422280, sale 11 = 144

address:6422284, sale 12 = 169

address:6422288, sale 13 = 178

address:6422292, sale 14 = 239

address:6422296, sale 15 = 320

 

 

배열의 시작 주소 α=6422236, ni=2, nj=2, nk=4, i=1, j=1, k=2, =4

sale[1][1][2]=239 위치 = α+{(injnk)+(jnk)+k}

= 6422236+ {(124)+(14)+2}4

= 6422236+ 56 =

= 6422292

 

 


'Development > Algorithm, DataStructure' 카테고리의 다른 글

알고지즘을 표현하는 기본 스텝  (0) 2018.10.03
Selection Sort(선택정렬)  (0) 2018.09.11
3차원 배열을 이용한 선형 리스트의 구현  (0) 2018.09.05
Queue 활용 사례  (0) 2018.08.28
리스트(list)  (0) 2018.08.21
연결 리스트(Linked List)  (0) 2018.08.16
Posted by codedragon codedragon

댓글을 달아 주세요


  

Queue 활용 사례

·       OS CPU 연산 처리시 작업 대기

·       프린터가 출력하는 문서 대기 목록

·       동영상 스트리밍 서비스에서 컨텐츠 버퍼링시 활용

·       최근 열어본 문서 목록

·       매표소에서 사람들이 차례로 줄을 있고, 줄의 제일 앞에 있는 사람부터 표를 있습니다.

 


Posted by codedragon codedragon

댓글을 달아 주세요


 

 

리스트(list)

·       리스트(list) 데이터를 순차적으로 나열해 놓은 집합을 가리키는 자료구조의 추상적인 개념으로 비슷한 성질의 데이터를 순서를 고려하여 그룹화 시키고자 주로 사용하는 자료구조입니다.

·       자료를 나열한 목록이나 도표처럼 여러 데이터를 관리할 있는 자료형을 추상화한 것입니다.

·       데이터 삽입, 삭제, 검색 필요 작업을 수행할 있습니다.

·       스택과 큐는 리스트의 특수한 형태에 해당합니다.

 


Posted by codedragon codedragon

댓글을 달아 주세요



 

연결 리스트(Linked List)

·       재귀적 자료구조입니다.

·       메모리에 불연속적으로 동적할당되어집니다.

·       연결 리스트는 저장된 요소가 비순차적으로 분포되며, 이러한 요소들 사이를 링크(link) 연결하여 구성합니다.

·       연결 리스트는 노드가 데이터와 포인터(참조값) 가지고 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조를 말합니다.

·       연결 리스트는 이름에서 있듯이 데이터를 담고 있는 노드(node)들이 서로 연결(link)되어 있으며, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됩니다.

 



 

 

Linked List 요소(node)들은 데이터 연결된 다음 요소에 대한 참조값(주소값)으로 구성되어 있습니다.(데이터 + 참조값)

 


 


'Development > Algorithm, DataStructure' 카테고리의 다른 글

Queue 활용 사례  (0) 2018.08.28
리스트(list)  (0) 2018.08.21
연결 리스트(Linked List)  (0) 2018.08.16
Think Data Structures: Algorithms and Information Retrieval in Java  (0) 2018.08.14
배열(array) vs 리스트(list)  (0) 2018.08.13
알고리즘 조건  (0) 2018.08.12
Posted by codedragon codedragon

댓글을 달아 주세요


 

 

Think Data Structures: Algorithms and Information Retrieval in Java

http://greenteapress.com/thinkdast/html/index.html


 



 

https://amzn.to/2P6A2tj

http://bit.ly/2P2YYSu

 

 

 

 

직접 다운로드

thinkdast.pdf

thinkdast.z01

thinkdast.zip

 

or

http://greenteapress.com/thinkdast/thinkdast.pdf

https://github.com/yudong80/ThinkDataStructures

 



Posted by codedragon codedragon

댓글을 달아 주세요


 

배열(array) vs 리스트(list)

·       리스트는 배열과 같은 다중 자료형 형태이나, 다른 속성을 지닙니다.

·       배열은 이미 정해진 크기의 메모리 공간이 필요하지만, 리스트는 필요 없습니다. 데이터를 하나씩  집어 넣을 때마다 메모리 공간을 생성합니다.

·       배열은 데이터의 위치에 대해서 직접적인 엑세스가 가능하지만, 리스트는 불가능하며 가장 처음위치부터 몇 번째인지 하나씩 세어가면서 위치를 찾아갑니다.

·       배열은 데이터의 추가나 삭제가 상당히 불편하지만, 리스트는 매우 쉽게 추가하거나 삭제할 수 있습니다.

 

배열

·       미리 정해진 크기의 메모리 공간 사용

·       데이터의 위치에 대해서 직접적인 접근 가능

·       데이터의 삽입이나 삭제가 상당히 불편

리스트

·       메모리 공간이 가변

·       데이터의 위치에 대해서 직접적인 접근 불가능

·       데이터의 삽입이나 삭제가 용이

·       데이터를 순차적으로 나열해 놓은 집합을 서로 연결한 구조

 

 



 



Posted by codedragon codedragon

댓글을 달아 주세요


 

 

알고리즘 조건

알고리즘이 되기 위해서는 아래의 조건을 만족해야 합니다.

구분

설명

입력

0 이상의 입력이 존재해야 합니다.

출력

1 이상의 출력이 존재해야 합니다.

명백성

명령어의 의미는 모호하지 않고, 명확해야 합니다.

유한성

한정된 수의 단계 후에는 반드시 종료되어야 합니다.

유효성

명령어들은 실행 가능한 연산이어야 합니다.

 

 



Posted by codedragon codedragon

댓글을 달아 주세요


 

Raft: The Understandable Distributed Consensus Protoco

 

https://speakerdeck.com/benbjohnson/raft-the-understandable-distributed-consensus-protocol


 


Posted by codedragon codedragon

댓글을 달아 주세요



 

 

The Raft Consensus Algorithm

 

https://raft.github.io/


 

 


Posted by codedragon codedragon

댓글을 달아 주세요