[240214] 알고리즘 리부트 6일차 - 백준 1236, 10431 자바

[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)이다.

 

강의를 듣고 나니 물러난 배열을 직접 구현하지 않아도^^;; 옮겨주지 않아도 문제의 답을 구할 수 있었다. 오른쪽 아래는 직접 옮기지 않고 답을 구하는 코드이다. 매번 배열을 오름차순으로 정렬해놓기 때문에 나의 인덱스 전에 나보다 큰 수가 있다면 그 큰 애들의 수를 세는 것만으로 문제를 해결할 수 있다.