ps (12) 썸네일형 리스트형 [알고리즘] 이분탐색 이분탐색은 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 리스트의 모든 값을 비교하는 완전 탐색의 경우에는 O(n)의 시간 복잡도를 가지는 반면에 이분탐색은 O(logn)의 시간 복잡도를 가져 빠른 탐색이 가능하다. 이분탑색을 사용하기 위해서 필요조건이 있다. 1. 리스트의 데이터가 정렬되어야 한다. -> 정렬이 되어있지 않으면 원하는 데이터가 어느 범위에 있는 특정 짓을 수가 없기 때문이다. 2. 무작위 접근이 가능해야한다.(Random Access) -> 원하는 인덱스의 값을 얻기위해서 O(1) 접근이 불가능한 연결 리스트의 경우에는 이분탐색의 의의가 퇴색되기 때문이다. 기본적인 이분탐색의 알고리즘은 아래의 그림과 같다. 값이 포함된 범위 [left, right]에서 그 중간 값이니 mid.. LIS 최장 증가 수열 입력한 수열에서 순차적으로 증가하는 수열을 추출하여 그 수열의 길이를 출력하는 알고리즘 문제이다. 1. 단순한 방법 해당 문제에서 단순한 방법은 모든 경우의 수열을 도출하여 그 수열의 길이를 비교하여 최대 길이의 수열을 알아내는 것이다. 이 방법은 입력하는 수열의 길이에 따라서 부분 수열이 기하급수적으로 증가하기 때문에 해당 문제에서 통과하기 어려운 방법이다. 2. DP를 활용한 방법 n번째 수열의 숫자가 n+1번째 수열의 숫자보다 크다면 n+1번째까지의 수열에서의 최장 증가 수열은 n번째 수열의 최장 증가 수열에서 1을 더한 값을 길이로 가진다. n번째 수열의 숫자가 n+1번째 수열의 숫자보다 작다면 n+1번째까지의 수열에서의 최장 증가 수열은 n-1에서 1위치의 숫자가 마지막인 수열이고 n번째 수를 .. 소수 만들기 #include #include #include using namespace std; bool isPrior(int num){ if(num == 1) return false; for(int i = 2; i 해쉬-완주하지 못한 선수 @ 실패한 코드 다음의 코드는 실패한 경우이다. 동명이인의 경우에는 해쉬에 저장하면 hashset의 특성상 중복을 저장하지 않기 때문에 동명이인이 후보자와 완주자에 동일하게 있음에도 완주자로 확인을 하지 못한다. 실패 테스트 케이스 participant ["mislav", "stanko", "mislav", "ana", "ana"] completion ["stanko", "ana", "mislav", "mislav"] answer "ana" import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { HashSet hash = new HashSet(); if(participant.. 이전 1 2 다음
