일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 알고리즘
- JDBC
- Thymeleaf
- transaction
- QueryDSL
- kotlin
- Proxy
- 그리디
- 김영한
- jpa
- 스프링 핵심 기능
- 인프런
- Android
- http
- JPQL
- spring
- Exception
- 스프링 핵심 원리
- springdatajpa
- Greedy
- AOP
- pointcut
- java
- db
- 자바
- SpringBoot
- Servlet
- 스프링
- Spring Boot
- 백준
- Today
- Total
목록알고리즘문제 (2)
개발자되기 프로젝트
일반적으로 정렬 알고리즘은 O(n^2)의 수행시간을 가짐. 1. Selection Sort 50 10 60 80 90 100 20 위와같이 숫자 배열이 있을 때, 오름차순으로 정렬해보자 앞에서부터 쭉 스캔해서 제일 작은 값 찾고, 가장 앞에 위치시킴. 다름 위치에는 누굴 데려올까, 쭉 스캔하다가 가장 작은 값 선택(selection) 즉, n개의 값을 n번 씩 봐야 하기 때문에 O(n^2)이다. 2. Bubble Sort 아래와 같이 숫자 배열이 있다고 하자. 50 10 60 90 80 20 100 1) 50 & 10 비교한다. 10이 더 작다. -->50 ↔ 10 위치 바꾼다. 10 50 60 90 80 20 100 3) 50 & 60 비교 --> 그대로 10 50 60 90 80 20 100 5) 6..
여러 개의 수가 정렬 되었을 경우 특정 수를 찾는 방법 단순 반복문을 사용하면 앞에서 부터 차례로 찾아가기 때문에, 입력된 값에 따라 비교 횟수가 증가한다. 즉 O(n)의 수행이 이루어진다. 정렬된 상태에서 수행 횟수를 줄이기 위해서는 binary Search가 효율적이다. 왜냐? 아래와 같은 상황이라고 가정하자. 10개의 수의 배열이 주어진다. [12, 25, 31, 43, 53, 64, 78, 82, 95, 103] 95의 위치를 찾아보자. 1) 단순 반복문을 사용해서 하나씩 비교하면, 12부터 차례대로 비교해서 95와 같은지 확인해야 한다. 2) binary search를 사용하면, 중간에 있는 값이 95보다 큰지 작은지 판단한다. 3) 중간에 있는 값은 53이다. 따라서 이제 53이전의 숫자는 고..