mondegreen

[Part1-Chapter04-Clip09] - 백준 2817 ALPS식 투표 우선순위 큐나 set을 써야하나라는 고민이 들었던 문제였다. 아직 강의 순으로는 해당 자료구조를 배우지 않아서 최대한 배열을 사용하려고 했고 하지만 시간 복잡도를 고려했을 때 가장 높은 점수 순으로 칩을 부여하기 위해서는 적어도 리스트에 담아 정렬할 수밖에 없다는 생각이 들었다. 참가자들의 수가 250만이지만 스태프 수는 10명으로 제한되어 있고 나누는 값도 최대 14까지 적은 수가 반복문을 여러번 돌아도 시간 초과는 나지 않을 것 같았다. 또 칩을 부여하는 과정에서는 내림차순으로 정렬된 수를 각 스태프의 기본 점수로 나누었을 때 나머지가 0.0이면 칩을 부여하는 방식으로 처리했었는데 왜인지 찾을 수 없는 경우가 있어 모든 점..

[Part1-Chapter03-Clip04] -백준 10989 수 정렬하기 3 위 문제는 시간 제한과 메모리 제한이 비교적 있는 편이라 단순히 삽입 정렬을 할 수는 없었다. 최악의 경우 모든 숫자를 배열에넣고 단순히 sort 매서드를 쓰기에는 메모리 제한에 걸리기 때문에 그렇게 풀 수 는 문제는 아니었고. 정수배열의 경우 인덱스 하나당 4바이트 인데 모든 수를 배열에 넣는다면 4천만 바이트로 메모리 제한에 걸리기 때문에 불가. 주어지는 수의 갯수는 천개 이지만 수의 종류가 최대 10000이기 때문에 카운팅 배열을 활용하고자 했다. 입력을 받으며 해당하는 인덱스에 갯수를 늘려주고 입력되는 수의 최대값을 구해 놓으면 반복문을 돌 때 그 수를 줄일 수 있을 거라고 생각했다. 카운팅 배열에 오름차순으로 값을 넣..

[Part1-Chapter03-Clip01] 각 연산의 시간 복잡도는 다음과 같다. 1) 원소 반환: 배열의 주소를 알고 각 인덱스가 정수 배열의 경우 4byte씩 차지하기 때문에 주소 계산이 바로 가능하다. 따라서 시간 복잡도는 O(1)이다. 2) 원소 변경: 1)과 마찬가지로 동일하게 접근해 변경하기 때문에 시간 복잡도는 O(1) 이다. 3) 맨 뒤 원소 삽입: 마찬가지로 인덱스를 지정해 삽입하는 것이기 때문에 시간복잡도는 O(1)이다. 4) 원소 삽입: idx 원소 앞에 원소 삽입하는데 원하는 인덱스부터 마지막 원소까지 한 칸씩 뒤로 이동시켜야 하기 때문에 반복문을 수행하게 되고 이 때문에 시간 복잡도는 O(n)이다. 5) 원소 삭제: 1)~3) 연산과 마찬가지로 특정 인덱스에 접근해 값을 지우는 ..