YunaNote

삽입 정렬(Insertion Sort)이란? 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입해 정렬하는 방식 시간 복잡도는 O(n^2)로 느린 편 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입 삽입 정렬 수행과정 🔹현재 Index에 있는 데이터 값을 선택 🔹현재 선택한 데이터가 정렬된 데이터 범위에 삽입된 위치를 탐색 🔹삽입 위치부터 index에 있는 위치까지 shift 연산 수행 🔹삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행 🔹전체 데이터의 크기만큼 index가 커질 때까지 수행 ( 선택할 데이터가 없을 때까지 반복 수행 ) 탐색하는 부분에서 이진 탐색과 같은 탐색 알고리즘을 통해 시간 복잡도를 줄일 수 있다. 관련 문제 [ 백준 ]..

슬라이딩 윈도우(Sliding Window) : 투 포인터와 유사하게 2개의 포인터로 범위를 지정, 범위(Window)를 유지한 채로 이동하며 문제를 해결하는게 특징 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법 슬라이딩 윈도우와 투 포인터 차이 투 포인터 슬라이딩 윈도우 구간의 넓이가 조건에 따라 유동적으로 변경 항상 구간의 넓이가 고정 관련 문제

해당 포스팅은 " Do it! 알고리즘 코딩 테스트 " 기반으로 정리 하였습니다 💡디버깅(Debugging) : 오류를 찾아 바로잡는 과정 디버깅은 개발자로써 많이 사용하고 중요한 기술이고, 코딩 테스트 문제를 풀면서도 잘 활용해야한다. 💡디버깅을 하는 법 🔶 디버깅 방법 🔸 디버깅 하고 싶은 줄에 중단점을 설정, 중단점의 경우 여러 개를 설정 할 수 있다. 🔸 디버깅을 실행하면 중담점부터 1줄씩 실행하거나 다음 중단점까지 실행할 수 있어 값이 의도대로 바뀌는지 확인 가능하다. 🔸 원하는 수식을 입력해 논리 오류를 파악 할 수 있다. 🔹디버깅을 하고자 하는 줄에 중단점(Break Poing)을 설정 🔹디버그창 확인, 로컬, 자동, 조사식 창 활용 🔹단축키를 이용하여 디버그 실행 한 단계씩 코드 실행 : ..

동적 계획법 ( Dynamic Programming ) : 하나의 복잡한 문제를 한번에 해결하는 것이 아닌 여러 개의 작은 문제로 나눠 큰 문제를 점차적으로 해결할 때 사용한다 -> 점화식을 이용해 문제를 풀어나간다고 생각하면 된다. 동적 계산법 사용 조건 1. Overlapping Subproblems (중복되는 부분 문제) DP는 기본적으로 큰 문제를 나누고 여러 부분 문제로 나눠지며 부분 문제들이 중복해서 나타난다. 하지만 DP는 부분 문제의 결과를 저장하여 계산이 되어야하지만 부분 문제가 중복으로 나타나지 않아 재사용이 불가능한 경우 DP(동적계산법)을 사용할 수 없다. 2. Optimal Substructure(최적 부분 구조) 부분 문제의 최적의 값을 이용해 큰 문제에 영향을 받지 않고 항상 ..

브루트포스(Brute Force) Brute(난폭한) + Force(힘) = 완전 탐색 알고리즘이라 불리며 모든 경우의 수를 탐색하며 요구조건에 충족한 결과만 가져온다. 모든 영역 전체를 탐색 BFS(너비 우선), DFS(깊이 우선) , 순차 탐색 등을 사용 특징 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식 암호학에서 가장 확실한 방법으로 통용되고 있으며 100% 정확도를 보장 완벽한 병렬 작업이 가능 But, 시간적인 측면에서 비효율적인 알고리즘 대표 문제 [ 백준 ] 브루트포스 - 블랙잭 브루트포스란? brute [짐승, 짐승같은, 난폭한 ] + force [ 힘, 무력, 폭력 ] 의 합성어로 짐승같은 힘, 난폭한 힘, 완전 탐색 알고리즘이라고 말할 수 있다. 완전 탐색?? 모든 경우의 수를 ..