본문 바로가기

정보AP10

12-2 (고급 탐색 구조: 해싱) 해싱: 해시 함수에 문자열 입력값을 넣어 특정한 값으로 추출하는 것.해시함수: 해싱에서 킷값으로부터 레코드가 저장될 위치를 계산하는 함수해시 테이블: 해시 함수에 의해 계산된 위치에 레코드를 저장한 테이블 ex) 탐색키가 모두 1~1000사이의 정수라고 가정하면 가장 빠르게 탐색할 수 있는 방법은 1000개의 항목을 가지는 배열을 만드는 것임. 자료의 삽입과 탐색은 탐색키를 인덱스로 생각하고 그 위치에 저장하거나 읽어오면 됨.이 경우의 해쉬 함수는 h(key)=key가 됨. 시간복잡도는 O(1)임. 그러나 만약 탐색키가 문자열이거나 실수, 또는 굉장히 큰 정수면 메모리가 부족해진다. 이 경우 탐색키를 더 이상 직접 배열의 인덱스로 사용할 수 없고, 대신에 탐색키를 작은 정수로 대응시키는 해시 함수가  필.. 2024. 12. 4.
12-1 (탐색 알고리즘) 순차탐색: 정렬되지 않은 테이블에서도 원하는 레코드를 찾을 수 있는 가장 단순하고 직관적인 방법.테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 찾음.탐색함수는 탐색 대상인 리스트 A와 탐색 키, 리스트에서 탐색 범위 low, high를 매개변수로 전달받음.리스트의 low 위치부터 탐색을 시작하여, 탐색이 성곡하면 항목의 위치를 반환함. 만약 high까지도 원하는 레코드가 나타나지 않으면 None을 반환한다.탐색의 성능은 최선의 경우 찾는 항목이 맨 앞에 있는 경우고, 맨 뒤에 있거나 리스트에 없는 키를 찾는 경우 최악이다.그러므로 평균 비교 횟수는 (1+2+3+...+n)/n=(n+1)/2 다. => 시간 복잡도는 O(n) 이진탐색: 테이블의 중앙에 있는 값을 조사하여 찾는 항목.. 2024. 12. 4.
11-2 (탐색과 맵 구조) 자료를 효율적으로 탐색하기 위해 데이터르 잘 정리하는 방법으로 탐색과 맵 구조가 있다. 탐색은 레코드의 집합에서 원하는 레코드를 찾는 작업이다.레코드의 집합을 테이블이라고 칭하고, 레코드들은 서로를 구별하여 인식할 수 있는 키(혹은 탐색키)를 가지고 있다.=> 탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업이다. 맵또는 딕셔너리는 자료를 저장하고 탐색키르 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 탐색을 위한 자료구조를 말한다. 맵은 엔트리라는 키를 가진 레코드(keyed record)의 집합이다.엔트리는 키와 값 두 개의 필드를 가진다. 키(key): 영단어나 인명같은 레코드를 구분할 수 있는 탐색키값(value): 영단어의 의미나 어떤 사람의 주소와 같은 탐색키와 관련된 값 이렇게 .. 2024. 11. 11.
11-1 (정렬 응용: 집합 다시보기) 집합은 원소의 중복을 허용하지 않으며 원소들 사이에 순서가 없다는 면에서 리스트와는 다름.추상자료형을 통해 집합의 비교나 합집합, 차집합, 교집합 등을 더욱 효과적으로 구현할 수 있다. 삽입연산: insert집합에 원소 삽입 시 먼저 중복검사를 진행해야 함.만약 중복 되었다면 삽입하지 않아야 함.중복이 아니라면 삽입하는데, 위치를 찾아서 리스트를 정렬된 상태로 찾아야 한다.리스트의 insert() 연산을 통해 삽입할 수 있고, 리스트의 정렬 유무와 상관 없이 바뀌지 않는다. 비교연산: __eq__두 집합이 동일한 집합인지 비교할 때 사용됨.정렬되지 않은 상태에서는 A의 모든 원소가 B에 있는지, 그 반대의 경우까지 검사해야 함.이 경우 각 집합의 원소의 개수가 모두 n이라고 가정하면, 시간복잡도는 O(n.. 2024. 11. 11.
10-2 (정렬 알고리즘 알아보기) 선택 정렬: 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법. 전체 숫자들은 아직 정렬되지 않은 오른쪽 리스트와 정렬이 완료된 왼쪽 리스트로 나뉨.맨 처음에는 모든 숫자가 오른쪽 리스트에 들어있고 그 중 가장 작은 숫자를 선택하여 왼쪽 리스트의 맨 뒤로 이동하는 작업을 반복하는 것임. ex)왼쪽 리스트 (정렬O)오른쪽 리스트 (정렬X)설명[ ][5,3,8,4,9,1,6,2,7]초기상태[1][5,3,8,4,9,6,2,7]1 선택 및 이동[1,2][5,3,8,4,9,6,7]2 선택 및 이동.........[1,2,3,4,5,6,7,8,9][ ]9 선택 및 이동  삽입정렬: 카드를 정렬하는 방법과 유사함. 손 안에 정렬된 카드가 있고, 카드를 추가로 한 장씩 더 받을 때 마다 그 카드를 순서대로 끼.. 2024. 10. 24.
10-1 정렬의 의미 정렬: 우리가 데이터를 저장하기 위해 복잡한 자료구조를 사용하는 이유는, 대부분의 경우 효율적인 탐색과 정렬을 위함. 탐색은 많은 자료 중 무언가를 찾는 작업, 정렬은 데이터를 순서대로 재배열하는 것을 말함. 정렬을 위해서는 사물을 서로 비교할 수 있어야 함. 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있다.기준의 예시로는 오름차순, 내림차순, 알파벳 순 등이 있다. 정렬시켜야 될 대상은 레코드라 부르고 레코드는 여러 개의 필드로 이뤄진다.ex) 경주마의 경우 번호, 이름 키 등의 다양한 속성이 필드가 됨.이들 중 정렬의 기준이 되는 필드를 key 또는 sort key라 한다. 정렬이란 레코드들을 키의 순서로 재배열하는 것임. 정렬 장소에 따른 분류내부(internal) 정렬: 모든 데이터가 메.. 2024. 10. 24.
[2단원 실습문제 풀이] 파이썬으로 쉽게 풀어 쓴 자료구조 확실히 연습문제보다 어렵다 어려워... 1번은 수학적으로 미리 계산하고 코드에 대입하니 금방 풀렸고... 2번은 rand함수의 사용법을 몰라 잠깐 검색했지만, 양호하게 풀렸다. 3번은 *로 삼각형을 그려본 적은 있지만 이렇게 수로 그려본 적은 처음이라 생소했다. 4번....어렵다 하하하 질문/문의 사항이 있다면 댓글 남겨주세요! #P2.1 a=int(input()) if a 2024. 3. 29.
[1단원 연습문제 풀이] 파이썬으로 쉽게 풀어 쓴 자료구조 AP과제로 직접 열심히 작성해 본 코드 ㅠㅠ 1장은 파이썬 코드보다는 정의를 물어보거나 활용하는 문제가 많았다. 나도 이 학교에 입학 후 초반에 과제를 할 때 Tistory 신인님들 덕을 받았으니 과제를 하며 어려움을 겪고 있는 여러분께 풀이를 공유합니다...! 어렵거나 궁금한 코드가 있다면 댓글로 물어보세요!!! #1.1 (1)스택, (2)큐 #1.2 numOF(item) Bag에 들어있는 item의 숫자를 반환하는 함수 #1.3 Time(h, m, s): 시, 분, 초를 표현하는 추상 자료형 - h: 시간을 나타내는 정수형 변수 - m: 분을 나타내는 정수형 변수 - s: 초를 나타내는 정수형 변수 h(): 현재 시간을 반환하는 함수 - 반환값: 시간을 나타내는 정수형 변수 h m(): 현재 분을 반.. 2024. 3. 28.
[2단원 연습문제 풀이] 파이썬으로 쉽게 풀어 쓴 자료구조 AP과제로 직접 열심히 작성해 본 코드 ㅠㅠ '연습문제'여서 쉬운 문제들이 대부분 이였으나, 뒤로 갈수록 사고력을 요구하는 코드들이 많았다...! 어렵거나 궁금한 코드가 있다면 댓글로 물어보세요!!! #2.1 for n in range (9): print(6*(n+1)) #2.2 n = 1 while n < 9: print(6 * n) n += 1 #2.3 for n in range (9,0,-1): print(6*n) #2.4 a=int(input()) a=32+1.8*a print(a) #2.5 def CtoF(C): F=32+1.8*C return F C_input=int(input()) a=CtoF(C_input) print (a) #2.6 A = [1,2,3,4] A.reverse() print.. 2024. 3. 28.

티스토리툴바