목록자료구조책 (3)

Run with coding

누구나 자료 구조와 알고리즘 | 긍정적인 시나리오 최적화 | 삽입 정렬 알고리즘

✔️ 삽입 정렬 1. 인덱스 1의 값을 변수에 담아둔다. 2. 왼쪽의 값과 변수에 담아둔 값을 비교한다. 3. 왼쪽 값이 더 크다면 오른쪽으로 쉬프트, 작다면 해당 패스스루 끝내기 4. 쉬프트하여 빈 자리에 변수로 담아둔 값을 넣는다. 5. 마지막 인덱스까지 반복 ✔️ 삽입 정렬 코드 구현 ✔️ 삽입 정렬의 효율성 원소가 N개인 배열 비교 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교 시프트 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교 삭제 : N-1번 삽입 : N-1번 총 단계 수 : N^2 + 2N - 2단계 원소가 5개인 배열 비교 : 1 + 2 + 3 + 4 = 10번 시프트 : 1 + 2 + 3 + 4 = 10번 삭제 : 4번 삽입 ..
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 14. 14:45
누구나 자료 구조와 알고리즘 | 빅 오 표기법 | 빅 오로 코드 속도 올리기

✔️버블 정렬 : 매우 기본적인 정렬 알고리즘 버블 정렬 방법 배열의 첫 번째 원소부터 다음 원소와 비교하며 오른쪽 값이 더 크면 두 항목을 교환 교환이 일어나지 않는 패스스루가 생길 때까지 반복 버블 : 각 패스스루마다 정렬되지 않는 값 중 가장 큰 값 버블 정렬 실제로 해보기 버블 정렬의 효율성 버블 정렬 알고리즘 = 비교 + 교환 ex) 원소가 5개라면.. ⇒ 총 20단계 비교 : 4 + 3 + 2 + 1 = 10번 교환 : 4 + 3 + 2 + 1 = 10번 ex) 원소가 10개라면.. ⇒ 총 90단계 비교 : 9 + 8 + 7 + … + 1 = 45번 교환 : 9 + 8 + 7 + … + 1 = 45번 ex) 원소가 20개라면.. ⇒ 총 380단계 비교 : 20 + 19 + 18 + … + 1 ..
코딩테스트 | 자료구조 | 알고리즘 2023. 5. 19. 09:00
누구나 자료 구조와 알고리즘 | 빅 오 표기법

✔️빅 오가 무엇인가? 빅 오 = 원소가 N개일 때 몇 단계가 필요할까? 빅 오의 본질 빅 오는 데이터가 늘어날 때 단계가 어떻게 증가하는 지를 설명한다. 즉, 데이터가 늘어날 때 알고리즘 성능이 어떻게 바뀌는지 O(N) = 알고리즘에 N단계가 필요하다. N은 항상 상수 O(1) = 가장 빠른 알고리즘 단계 배열 읽기에는 딱 한 단계만 필요 O(1) VS O(N) 데이터가 증가할수록 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 됨 선형 검색의 효율성을 빅 오로 표기해보자! 찾고자 하는 항목이 첫 번째 있다면 : 최선의 시나리오 O(1) 찾고자 하는 항목이 마지막에 있다면 원소N개를 모두 검색해야 하기 때문에 : 최악의 시나리오 O(N) 별도로 명시하지 않는 한 빅 오 표기법은 최악의 ..
코딩테스트 | 자료구조 | 알고리즘 2023. 5. 18. 14:14
이전 Prev 1 Next 다음