알고리즘 (3) 썸네일형 리스트형 중복 없는 랜덤 정수 최적화 ( O(N) ) 1학년 때 프로그래밍을 처음 배우면 꼭 한번씩 로또 번호 추첨기를 만들어본다. 이 때 보통 이미 뽑은 번호를 추첨하면 다시 추첨하는 식으로 코드를 짜는데 사실 이 코드는 정말 최악의 경우는 무한대이다. 이에 대해 최적화하는 경우를 생각해보았는데 인터넷에는 대부분 O(N^2)이어서 O(N) 알고리즘을 한번 소개해볼까 한다. 파이썬에는 random.sample() 이 이미 있으므로 C 기준으로 설명해보겠다. 알고리즘은 간단하다. 원래 배열이 1 2 3 4 5 6 7 8 9 10 이고, 0 ~ 9 의 정수 중 하나를 랜덤으로 뽑아 4를 얻었다고 가정하자. 그럼 arr[4] = 5 이므로 5를 추출하는 것인데 이 때 배열의 마지막 성분 10을 5 자리에 넣고 다시 랜덤 추출하고 이와 같은 방법을 매번 반복하는 .. 프로그램의 성능 분석 입력 데이터의 크기에 따라 (1) 실행 속도 (2) 메모리 사용량 이 어떻게 변하는지 예측하는 것은 반드시 필요합니다. 원하는 성능에 미치지 못하는 경우 원인을 파악하여 수정해야 하기 때문입니다. 프로그램 성능 분석은 내 프로그램이 실제로 사용되었을 때, 큰 입력 데이터와 다수의 동시 사용자를 잘 감당할 수 있을까에 대한 궁금증을 해결해줍니다. 프로그램의 성능 표현 방법 ~f(N): 입력 데이터 크기가 N일 때, 프로그램의 성능이 대략적으로 f(N)에 비례함을 의미합니다. ex. ~Nlg(N)은 프로그램의 성능이 대략적으로 Nlg(N)에 비례함을 의미합니다. 매우 정확한 성능 계산보다는 대략적으로 서로 다른 알고리즘 간의 차이를 큰 틀에서 파악하는데 초점을 둡니다. 프로그램의 성능 분석 과정 개요 - 프.. Resizing Array 기본적으로 C언어, Java 등에서 배열은 초기화할 때 크기를 지정해주고 그 크기로 고정됩니다. 이 경우, 데이터 크기를 미리 알기 어려운 상황도 많아 미리 크기를 지정하기가 불편합니다. 이에 대해 보완책으로 나온 것이 Resizing Array 입니다. 저장된 데이터 양에 따라 크기를 자동 조정하는 자료구조로 기본 배열처럼 index로 원소 접근이 가능합니다. 파이썬의 List, 자바의 ArrayList가 이에 해당합니다. Resizing Array의 내부적 구현은 두가지가 있습니다. 1. 연결리스트 2. 기본 배열 사용한 구현 이중 1번은 인덱스를 이용한 원소의 접근이 O(N)이라 잘 사용하지 않습니다. 2번의 경우, 더 많은 공간이 필요하면 더 큰 배열을 만들어 기존의 데이터를 복사합니다. 위의 1.. 이전 1 다음