반응형 코딩테스트 준비220 탐색 알고리즘 총 정리(선형,이진탐색,해시탐색) 탐색 알고리즘이란탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법 01 선형 탐색(Linear Search)처음부터 끝까지 하나씩 비교하면서 찾는 방식int LinearSearch(int[] arr, int target){ for (int i = 0; i 시간복잡도최악 : O(N)최선 : O(1)02 이진 탐색(Bineary Search)정렬된 배열에서 중간값과 빅하며 절반씩 범위 줄이기조건 : 오름차순 or 내린차순으로 정렬된 데이터여야 한다.int BinarySearch(int[] arr, int target){ int left = 0, right = arr.Length - 1; while (left 시간복잡도 O(logn)03 해시 탐색(Hashing)키(key)를 해시.. 2025. 4. 16. 백준 C# - 1699 +) 풀이 문제정수 n이 주어졌을때 n을 제곱수들의 합으로 표현하는 방법 중에서 항의 개수가 최소인 경우의 수를 구해야한다.예시12 = 4 + 4 + 413 = 9 + 4 점화식 생각01 dp[] 배열에 어떤 값을 넣을까?i를 만들기 위한 최소 제곱수들의 합으로 표현할 때 필요한 항의 수02 i를 만들기 위해 바로 전 단계는 뭘까?이미 dp[i-j*j]값을 알고있음 그래서 이번 값에서 + 1그래서 나온 점화식dp[i] = min(dp[i-j²]+1) (단 j²예시) n = 5- dp[1]가능한 j: 1 (1²)dp[1] = min(dp[1], dp[1 - 1] + 1) = min(∞, dp[0] + 1) = 1dp[1] = 1- dp[2]가능한 j: 1 (1²)j=1: dp[2] = min(dp[2], dp[1] .. 2025. 4. 16. 백준 C# - 14002 +) 풀이 문제를 읽어보면입력이 1000이니까 1000*1000 = 1000000(백만)이므로 O(N²) 알고리즘으로도 이 문제는 충분히 통과 가능하다. 알고리즘01 문제 분석가장 긴 증가하는 부분수열 거의 동일하지만 한 가지 추가된 조건이 있다.단순히 수열의 길이만 구하는 것이 아니라 그 실제 수열의 내용도 출력해야한다. 02 경로 복원(Path Reconstruction)그 값을 만들기 위해 어떤 선택을 했는지를 저장해서 실제해를 구성할 수 있게 하는 방법이다. 경로 복원에 대한 정보 저장 - prev 배열prev[i] = dp[i]를 만들기 위해 선택된 이전 인덱스, 즉 dp[i]가 dp[j]+1로 갱신되었으면 prev[i] = j를 저장하는 것이다.10 20 10 30 20 50ilist[i] dp[i]pr.. 2025. 4. 11. 백준 C# - 15990 +) 풀이 문제 설명정수 N을 1,2,3 합으로 표현하는 방법의 수 조건 : 같은 수를 연속으로 두 번 이상 사용하면 안된다."1 + 1 + 2" ❌"1 + 2 + 1" ✅조건이 없는 경우 (연속된 숫자가 올 수 있는 경우) 백준 C# - 9095 +)풀이DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작code-piggy.tistory.com점화식dp[n] = dp[n-1] + dp[n-2] + dp[n-3]조건이 있는 경우(연속된 숫자가 올 수 없는 경우)마지막 숫자만 확인하여 겹치게만 안하면 된다는 것이다. 다른말로 마지막 숫자만 체크하면 된다. dp[n][1] .. 2025. 4. 10. 백준 C# - 11053+) 풀이 문제풀이에 앞서 문제에서 제시된 시간복잡도를 분석해보자 제한 시간이 1초 → 일반적으로 연산량 1억 이내 가능하므로 입력에서 N의 크기가 1000이므로 O(N²)까지 허용된다.이 문제를 풀기 앞서 LIS 개념을 알고 풀이를 진행하자LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)란?수열에서 일부 원소를 "순서를 유지한 채"골라서 값이 점점 증가하도록 만든 부분 수열 중 가장 긴 길이의 구하는 문제이다.단 연손된 값일 필요는 없고, 앞에 선택된 값보다 커지기만 하면 된다. 예시[10, 20, 10, 30, 20, 50]→ 가장 긴 증가하는 부분 수열: 10 20 30 50 (길이 4) LIS은 전형적인 DP 문제이다.dp의 배열안에는 dp[i] : i번째 원소를.. 2025. 4. 9. 시간복잡도(빅오표기법)을 왜 알아야할까? 시간복잡도(빅오표기법)을 왜 알아야할까?개발을 할 때마다 매번 작성한 함수나 메서드의 시간 복잡도를 정확하게 계산하진 않는다. 실제 코드를 적을때는 함수 하나가 여러 파라미터를 받고 내부에서 또 다른 메서드를 호출하고 그 메서드가 또 다른 함수를 부르는 식으로 구조가 복잡해지는 경우가 많다. 이런 상황에서 일일이 모든 시간 복잡도를 구하는건 비효율적이고 현실적이지 않다. 그럼 시간복잡도는 신경 안 써도 될까?시간복잡도에 대한 개념을 잘 알고 있다면 코드를 짤때 동작하는 코드를 넘어서 더 나은 코드를 고민할 수 있는 능력이 생긴다.예를 들어 지금 작성하고 있는 코드에서 동작이 되긴하지만 더 최적화된 코드가 없을까?라는 질문을 스스로 할 수 있게 된다. 이는 꼭 O(n)과 O(n²)인지 계산하는게 중요한게 .. 2025. 4. 9. 이전 1 2 3 4 5 ··· 37 다음 반응형
