programmers. 구명보트 남들은 다 쉽게 푸는것 같은데 저는 왜 이렇게 그리디 문제가 감이 안올까요.. 처음엔 우선순위큐를 사용하여 가장 작은 몸무게를 찾은 다음 남은 사람들 중 무게제한을 초과하지 않는 사람들 중 가장 무거운 사람을 골랐습니다. 아무래도 남은 사람들 중 가장 무거운 사람을 찾는 과정에서 복잡도가 증가하였고 여러 테스트케이스에서 통과하지 못하였습니다. 이렇게 제일 큰 것 찾고 가장 작은 것도 동시에 찾기 위해선 우선순위큐 대신 리스트를 사용하고 포인터를 2개를 사용하면 됩니다(다 풀고나서 다른 사람들의 풀이를 보니 Deque도 많이 사용했더라구요. 어차피 똑같은 맥락이죠). 리스트를 오름차순 정렬하고 가장 작은(왼쪽) 수의 인덱스를 왼쪽(left), 가장 큰(오른쪽) 수의 인덱스를..
programmers. 큰 수 만들기 그리디(탐욕법) 문제라 그랬을까요. 무조건 큰 수를 먼저 골라내거나, 가장 작은 수를 빼내려고만 생각했던 것 같습니다. 탐욕법이 가장 유리해보이는 것을 가장 먼저 고려하는거잖아요. 그렇게 여러 가설을 세우고 이렇게 하면 모든 경우에 대해 적용이 될 수 있는지 탐험해보았습니다. 첫번째 가정 가장 작은수부터 지워나갑니다. 지울 수 있는 대상이 여러 개이고, 지울 수 있는 대상이 그 보다 작다면 앞의 수부터 지웁니다. 문제점 : "4177252841"와 같은 케이스를 걸러내지 못합니다. 두번째 가정 제일 큰 수부터 순서는 지키면서 앞의 순서대로 가져옵니다. 문제점 : 여전히 "4177252841"와 같은 케이스에서 문제이며 이때는 마지막 수 1이 문제입니다. 큰 수부터 가..
오늘은 알고리즘 문제를 따로 풀지는 않고 스터디를 통해 지난 푼 문제에서 틀렸던 부분에 대해 수정하고 기록해두었습니다. 다음 일주일 동안은 프로그래머스에서 그리디 문제 2개, 동적계획 문제 3개를 목표로 풀어보려고 합니다! 화팅!! :)
오늘도 별 문제 안 풀고 알고리즘 스터디를 진행만 했네요.알고리즘 스터디에서 제가 풀었던 문제 중에서 오류를 우연히 발견할 수 있었습니다.그 부분의 글을 수정 반영해야겠습니다.
오늘은 알고리즘은 제대로 푼 게 없네요(반성).. leetcode 10번 문제가 어려워 해답을 학원 오는길에 조금 봤는데 아직 잘 이해가 안가네요. 좀 더 이해가 되면 조만간 올리도록 하겠습니다.
n(log(n)) 정렬 불안정 정렬, 안정 정렬은 뭘까요? 정렬 후에 정렬 기준 값이 같은 원소의 상대적인 위치가 바뀌는 것의 유무를 말합니다. 출처 : 제타위키 불안정 정렬의 종류 : Selection, Heap, Quick 안정 정렬의 종류 : Bubble, Insert, Merge, Counting, Radix Quick sort 피봇을 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 한다는 왼쪽, 오른쪽에서 재귀적으로 다시 실행합니다. 불안정 정렬입니다. 가장 빠릅니다. 다른 n(log(n)) 정렬 중 quick sort가 왜 제일 빠를까요? 데이터의 locality(지역성)가 높기 때문에 그렇습니다. 그럼 locality는 뭘까요? 모든 데이터는 시간 지역성, 공간 지역성이 있습니다. 데이터는 자주 ..
