오늘도 더 나은 코드를 작성하였습니까?

이진 검색 알고리즘(binary search algorithm) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다 단순히 위의 예제와 구현 코드만 본다면 어렵지 않다. fun main() { arr = intArrayOf(1, 4, 7, 9, 11, 13, 16, 17, 21, 22, 25, 28) val k..

배열/리스트에 쌍을 검색하는 데 있어 이중 반복문을 사용하는 것 대신에 2개의 index를 저장하는 변수(두개의 포인터를)이용하여 효율적으로 검색을 하는 것. 이때, 배열이 정렬 및 특정한 규칙을 가진 경우가 많다. 즉, 연산이 이중 반복문으로 너무 오래걸리면서 특정한 조건의 쌍의 원소를 찾는 문제라면 투 포인터를 사용하는것을 고민해 봐야 한다. 가장 중요한건 두 쌍이 만족하는 조건을 잘 이해하고 언제 각각의 포인터를 움직여 줄것인가를 파악해야된다. 연속된 수열의 부분합 https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 ..

원형 이중 연결 리스트의 구조는 이중 연결 리스트의 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리키는 양방향 참조 노드를 이용하며, 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다. 여기에 연산및 구현의 편의성을 위해 데이터가 없으며 원형의 시작부분을 표시 하기 위한 Dummy Node를 추가 해준다. 더미 노드 기준으로 이중 연결 리스트 기반으로 순환하여 만든 리스트이기에 데이터를 앞뒤로 삽입/삭제 연산이 매우 빠르다. pushFront() O(1) pushBack() O(1) popFront() O(1) popBack() O(1) 특정 데이터를 가진 노드를 찾는 연산은 더미 노드를 시작으로 1바퀴 모든 노드를 돌아야 되기 때문에 리스트에 들어있는 개수만큼 시간 ..

탐욕 알고리즘(Greedy algorithm) 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 최종적(전역적)으로 최적인 문제들이다. 탐욕법으로 문제를 해결하기 위한조건 1. 탐욕스런 선택 성질(greedy choice property) - 앞선 선택이 이후의 선택에 영향을 주지 않는다. - 각 지역적 최적의 선택이 모두 전체에 포함됨 2...