{Programing}131 알고리즘 - 투 포인터(two pointer) 이미 정렬이 완료된 배열 or 리스트에서 두 개의 인덱스(포인터)를 이용해 포인터에 담긴 값과 원하는 결과를 비교해 원하는 해를 구하는 알고리즘. 이중 반복문으로도 해결가능한 문제이나 O(N^2) 의 시간이 소요. 정렬이 안된 배열에서도 O(NlogN), 정렬된 배열에선 O(N)의 시간으로 단축됨. ex) 배열 내 합이 S가 되는 순서쌍 찾기. 배열의 앞 뒤에서 포인터로 좁혀오며 순서쌍을 찾찾. 투 포인터(앞 : l 뒤 : r)가 지시하는 두 요소의 합을 S 와 비교 l 2020. 3. 4. 알고리즘 - Greedy(탐욕) 문제 해결 기준으로 조건탐색 시기 기준으로 최적의 요소를 선택해서 해결해가는 알고리즘. 즉, 매우 근시안적 선택을 이용해 문제를 해결하는 방식. 최적화 문제에 자주 사용됨. 주의할 점은 " 최적을 선택하는 조건 " 이다. 조건이 잘못되면 해를 구할 수 없는 경우가 생길 수 있기 때문. 거스름돈 문제와 최소비용 신장 트리에서 많이 사용됨. Greedy 알고리즘은 최선의 해를 구하는 것이 아닌 최적 or 적당히 납득할만한 해를 구하는 것이 목표. 2020. 3. 4. 알고리즘 - 완전 탐색 어떠한 문제에 대해 모든 경우의 수를 찾아 답을 찾아내는 알고리즘. 반복문이나 재귀 함수로 작성. 반복문을 사용한 구현이 더욱 직관적이며 알아보기 쉽다. 재귀함수를 이용할 때에는 꼭 탈출 조건을 명확하게 발생시킬 수 있어야하고 호출 깊이가 너무 깊어지지 않도록 해야한다. 호출 깊이를 제한해야하는 이유는 메모리 때문. 함수는 호출되면 스택에 데이터가 저장되며, 재귀함수로 인해 스택 오버플로우의 발생가능성이 높아지기 때문. 코딩테스트에서 메모리 초과 or 런타임 에러로 오답처리되면 메모리 문제를 체크해보자. 2020. 3. 4. 알고리즘 - 개요 이하 모든 글은 goorm edu의 비타 알고 2를 공부하며 정리하는 내용임. 알고리즘 : 문제를 해결하는 방식, 기법, 순서 시간 복잡도 : 알고리즘을 해결하는 동안 걸리는 시간을 나타내는 방법. 빅 오 표기법을 사용한다. O( n ) 구현 : 알고리즘을 실제 실행 가능한 코드로 나타내는 것. 순서도 : 알고리즘의 순서를 도형으로 나타낸 것. 의사코드 : 실제 코드로 작성하기 이전에 일반적인 언어를 이용해 간이로 작성한 코드. 2020. 3. 4. 이전 1 ··· 15 16 17 18 19 20 21 ··· 33 다음