- [ 공부/알고리즘 ][알고리즘] 퀵 정렬2023-12-25 09:58:03퀵 정렬 기준값 pivot을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘 기준값이 어떻게 선정되는지가 시간복잡도에 많은 영향을 미치고 평균 시간복잡도는 O(nlogn)이며 최악의 경우 O(n^2) 퀵 정렬 과정 기준값을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 핵심 쿽 정렬의 시간 복잡도는 비교적 준수한 편 데이터를 분할하는 pivot을 설정 pivot을 기준으로 데이터를 2개의 집합으로 분리 start가 pivot보다 작으면 start를 오른쪽으로 1칸 이동 end가 pivot보다 크면 end를 왼쪽으로 1칸 이동 start가 pivot보다 크고, end가 pivot보다 작으면 start, end 데이터를 swap하고 start는 오른쪽, ..
- [ 기록/백준 ][백준 / 자바] 10845번 큐2023-12-24 16:58:52https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아..
- [ 공부/Spring ]Spring Boot JWT Tutorial 1) 프로젝트 생성2023-12-24 09:03:26Spring boot JWT Tutorial Session 1 프로젝트 생성 1. 프로젝트 생성 1) 프로젝트 생성 https://start.spring.io/ 2) IDE 설정 롬복 사용하기 때문에 Enble annotation pocessing 체크 2. rest API 테스트 1) hello API @RestController @RequestMapping("/api") public class HelloController { @GetMapping("/hello") public ResponseEntity hello() { return ResponseEntity.ok("hello"); } } RestController : json을 반환하는 컨트롤러 RequestMapping : 들어온 요청을 매핑 Ge..
- [ 자격증/리눅스 마스터 ][리눅스마스터 2급] 기출 문제 모음(2020~2023)2023-12-23 12:31:13리눅스 마스터 2급 2차 20년~23년도 기출문제 모음
- [ 공부/알고리즘 ][알고리즘] 삽입 정렬2023-12-23 11:08:51삽입 정렬 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 O(N^2)로 느린 편이지만 구현하기 쉽다. 삽입 정렬 과정 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심 ① 현재 인덱스에 있는 데이터 값을 선택 ② 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색 ▶ 탐색 부분에서 이진트리 등 탐색 알고리즘 사용 시 시간복잡도를 줄일 수 있다 → O(logN) ③ 삽입 위치부터 인덱스까지 shift 연산 수행 ④ 삽입 위치에 현대 선택한 데이터를 삽입하고 인덱스++ ⑤ 전체 데이터의 크기만큼 인덱스가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복
- [ 공부/알고리즘 ][알고리즘] 선택정렬2023-12-23 10:02:57선택 정렬 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 구현 방법이 복잡하고 시간복잡도가 O(N^2)로 효율적이지 않음 선택 정렬 과정 최솟값, 최댓값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 swap ① 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다 ② 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap ③ 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소 ④ 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복 선택 정렬 시간복잡도 구하기 선택정렬을 하기 위한 데이터가 n개일 때 n개 탐색 n-1개 탐색 n-2개 탐색 n-3개 탐색 ... n-n개 탐색 ▶ 총 n^2만큼 탐색 관련..
- [ 공부/알고리즘 ][알고리즘] 버블정렬2023-12-23 09:09:36정렬 버블 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬 선택 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬 삽입 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬 쿽 pivot값을 선정해 해당 값을 기준으로 정렬 병합 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬 기수 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬 버블 정렬 두 인접한 데이터의 크기를 비교해 정렬하는 방법 시간 복잡도는 O(n^2) 다른 정렬 알고리즘보다 느린 편 버블 정렬 과정 ① 비교 연산이 필요한 루프 범위를 설정 ② 인접한 데이터 값을 비교 ③ swap 조건에 부합하면 swap ④ 루프 범위가 끝날 때까지 2~3 반복 ⑤ 정렬 영역 설정, 다음 루프..
- [ 기록/백준 ][백준 / 자바] 1940번 주몽 - 투포인터2023-12-22 12:48:051940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어지게 된다. 야철대장은 자신이 만들고 있는 재료를..