일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 완전탐색
- algorithm
- 스택
- 가중치없는그래프
- 집합
- 정렬
- Recursion
- dfs
- 해시맵
- 알고리즘
- domain model
- 이분탐색
- MySQL
- 재귀
- 멘딕스
- 자바
- Bruteforce
- 프로그래머스
- 백트래킹
- 트리
- Mendix
- 매개변수 탐색
- lcap
- microflow
- git
- 그래프
- SQL
- 반효경교수님
- 자료구조
- Sort
- Today
- Total
mondegreen
[240214] 알고리즘 리부트 6일차 - 백준 1236, 10431 자바 본문
[240214] 알고리즘 리부트 6일차 - 백준 1236, 10431 자바
앙갱 2024. 2. 14. 15:54[Part1-Chapter03-Clip01]
각 연산의 시간 복잡도는 다음과 같다.
1) 원소 반환: 배열의 주소를 알고 각 인덱스가 정수 배열의 경우 4byte씩 차지하기 때문에 주소 계산이 바로 가능하다. 따라서 시간 복잡도는 O(1)이다.
2) 원소 변경: 1)과 마찬가지로 동일하게 접근해 변경하기 때문에 시간 복잡도는 O(1) 이다.
3) 맨 뒤 원소 삽입: 마찬가지로 인덱스를 지정해 삽입하는 것이기 때문에 시간복잡도는 O(1)이다.
4) 원소 삽입: idx 원소 앞에 원소 삽입하는데 원하는 인덱스부터 마지막 원소까지 한 칸씩 뒤로 이동시켜야 하기 때문에 반복문을 수행하게 되고 이 때문에 시간 복잡도는 O(n)이다.
5) 원소 삭제: 1)~3) 연산과 마찬가지로 특정 인덱스에 접근해 값을 지우는 것이라고 생각할 수 있지만 그게 아니라 4) 연산과 유사하게 특정 인덱스의 값을 삭제하고 그 뒤의 연속적인 원소를 한 칸 씩 앞으로 당겨야 하기 때문에 반복문을 수행하게 된다. 따라서 시간복잡도는 O(n)이다.
정리하자면 다음과 같다.
[Part1-Chapter03-Clip02]
- 백준 1236 성 지키기
경비병을 세우는 위치라든지 경비병 간의 거리를 최대가 되게 하는 걸 고르라든지와 같은 문제였다면 BFS로 풀어야했겠지만 단순히 세워야 하는 경비병의 수를 구하는 문제였기 때문에 간단하게 풀 수 있었다. 강의에서도 내 풀이 유사하게 풀었기에 다른 방식은 생략한다.
[Part1-Chapter03-Clip03]
- 백준 10431 줄 세우기
이 문제는 배열 내 원소 삽입을 메서드가 아닌 직접 구현하는 것이었다. 처음 풀었을 때 누가 서 있는 않은 자리도 옮기는 것으로 구현해 잘못된 답이 나왔는데 빈 자리가 아닌 경우에 옮기는 횟수를 세서 문제를 해결할 수 있었다. 왼쪽 아래는 나의 풀이이다. 푸는 방식은 문제에서 규칙으로 제공함에 따라 구현하는데 도움이 되었다. 그리고 이는 삽입 정렬을 구현한 것이다. 시간 복잡도는 O(T*P^2)이다.
강의를 듣고 나니 물러난 배열을 직접 구현하지 않아도^^;; 옮겨주지 않아도 문제의 답을 구할 수 있었다. 오른쪽 아래는 직접 옮기지 않고 답을 구하는 코드이다. 매번 배열을 오름차순으로 정렬해놓기 때문에 나의 인덱스 전에 나보다 큰 수가 있다면 그 큰 애들의 수를 세는 것만으로 문제를 해결할 수 있다.
'알고리즘 풀이 및 리뷰 > [패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰' 카테고리의 다른 글
[240216] 알고리즘 리부트 8일차 - 백준 10448, 11005, 11068 자바 (0) | 2024.02.16 |
---|---|
[240215] 알고리즘 리부트 7일차 - 백준 10989, 3273 자바 (0) | 2024.02.15 |
[240213] 알고리즘 리부트 5일차 - 백준 10158 자바 (0) | 2024.02.13 |
[240212] 알고리즘 리부트 4일차 - 백준 13223 자바 (0) | 2024.02.12 |
[240211] 알고리즘 리부트 3일차 - 백준 1543 자바 (0) | 2024.02.11 |