반응형 코딩테스트 및 개인공부/알고리즘4 [강의정리] [연결리스트] 실전 알고리즘 0x04 정리 바킹독의 실전 알고리즘 0x04 강의 정리. 연결리스트는 어떤 문제에 쓰일까? - 연결 리스트가 쓰이는 문제는 크게 응용해서 낼만한게 없고 원소들을 돌아다니면서 이동하다가 삭제나 삽입이 필요한 문제들 - 연습문제들 https://jjpearl.tistory.com/52 [백준 - 1406번] 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 jjpearl.tistory.com - 손코딩 문제 1 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법? -> 효율적 = 생각한 풀이의 공간복잡도와 시간복잡도.. 2022. 4. 26. [강의정리] [배열] 실전 알고리즘 0x03 정리 바킹독의 [실전 알고리즘] 0x03강 - 배열 정리. -배열의 성질 O(1)에 k번째 원소를 확인/변경 가능 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없다. Cache hit rate가 높음 메모리 상에데이터들이 붙어 있으니까. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 -시간 복잡도 임의의 위치에 있는 원소를 확인/변경 = O(1) 원소를 끝에 추가 = O(1) 마지막 원소를 제거 = O(1) 임의의 위치에 원소를 추가/임의 위치의 원소 제거 = O(N) -배열 전체를 특정값으로 초기화 for문으로 값을 하나하나 다 바꾸는 방식 : 무난 algori.. 2022. 4. 22. [알고리즘] 그리디(탐욕법) 알고리즘 (Greedy Algorithm) 프로그래머스 코딩 테스트 고득점 Kit의 탐욕법 카테고리를 풀기 시작하면서 그리디 알고리즘에 대해서 정리해본다. -그리디(탐욕법) 알고리즘이란? 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다고 한다. 그리디 알고리즘이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘이다. 즉, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에서 현재 당장 최적이라고 생각되는 것을 선택해 나가는 식으로 진행하여 최종적인 해답에 도달한다. 백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다. 그리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택해나가는 방식이지만 이 가장 좋은.. 2021. 11. 23. [알고리즘] 완전탐색 (Exhaustive Search) - 완전탐색 알고리즘이란? 모든 가능한 경우를 일일이 다 탐색해보는 방법. 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 하지만 당연히 시간은 최대로 들어간다. *문제 해결 알고리즘을 사용할 때의 2가지 규칙 1. 사용된 알고리즘이 적절한가? (문제를 해결할 수 있는가) 2. 효율적으로 동작하는가? 완전탐색 알고리즘으로 문제를 해결한다면 1번은 만족할 수 있는 가장 확실한 방법이지만 대부분의 경우에 2번을 만족하지 못하기 때문에 이 방법을 사용하는데 제한이 따른다. 따라서 완전탐색 기법을 사용할 때는 그 문제에 대한 파악이 중요. - 완전탐색의 종류 1.브루트 포스(Brute force) : 반복(for)/조건문을 활용해 처음부터 끝까지 탐색하는 방법.. 2021. 7. 6. 이전 1 다음 반응형
