🎨 문제 peak은 산의 정상을 의미한다. 배열이 주어지는데 값이 증가하다가 감소하는 포인트가 있다. 이를 peak라 부르며 해당 위치를 찾는 문제이다. peak은 여러 개 존재할 수 있으며 이 중 아무 위치나 리턴하면 된다. 양 끝 값의 경우 0번 째 이전(-1번째)와 마지막 다음 번째(n번째)의 값을 -∞로 하여 0번째와 n-1 번째도 peak이 될 수 있다. 그림으로 보면 이해하기 쉬울 것이다. L과 R도 peak이 될 수 있다. Find Peak Element - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for yo..
🎨 문제 오름차순으로 정렬된 배열을 회전시킨 배열이 주어진다. 해당 배열의 최소값을 찾는 문제이다. 단, 시간복잡도는 O(logN) Find Minimum in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 📘 풀이 [LeetCode] 33. Search in Rotated Sorted Array 🎨 문제 중복이 없는 정렬된 배열이 있다. 이 중 하나의 값을 피벗으로 배열을 회전시킨다. 그리고 회전된 배열에서 target..
🎨 문제 중복이 없는 정렬된 배열이 있다. 이 중 하나의 값을 피벗으로 배열을 회전시킨다. 그리고 회전된 배열에서 target 값의 인덱스를 반환하는 문제이다. (단, 시간복잡도는 O(logN)) Search in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 📘 풀이 O(logN)의 시간복잡도를 갖는 알고리즘은 보통 이진 탐색을 말한다. 이진 탐색의 경우의 경우 정렬된 배열에서 사용할 수 있다. 하지만 배열이 문제의 배..
다익스트라 알고리즘은 최단경로를 구하는 알고리즘이다. 💡 최단경로 ➡ 정점 i에서 정점 j를 연결하는 경로 중 가중치의 합이 최소인 경로 정의 하나의 시작정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 동적 프로그래밍 활용 ➡ 최단 거리는 여러 개의 최단거리로 이루어져 있다. 간선의 가중치가 음수일 경우 사용 불가 접근 특정 위치에서 특정 위치까지의 최단거리를 구하는 문제에 사용 구현 변수 인접행렬, 인접리스트 ➡ 그래프 정보 표현 distance[] ➡ 시작 정점에서 특정 정점까지의 경로의 최소를 저장하는 배열 visited[] ➡ 배열 방문 체크 알고리즘 distance[]의 값을 무한대로 초기화 시작 정점의 거리 0 ➡ distance[시작 정점] = 0 시작 정점과 인접한 노드에 대해..
leet코드 문제를 풀다가 신기한 풀이가 있어서 공유합니다. 🎨 문제 이진수 숫자가 주어지면 1의 개수를 세는 문제이다. Number of 1 Bits - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 📘 풀이 풀이 방식은 다양하지만 새롭게 알게된 풀이가 있었다. 바로 비트 연산을 활용하는 것이다. 💡 입력값 n에 n - 1한 값을 AND 연산하면 1이 하나 빠진다. 위의 방법을 이용하면 n이 0이 될 때까지 해당 연산을 반복하고 반복 횟수를 리턴하면 1의 개수..
정의 그래프 알고리즘의 일종 상호 배타적 집합, Disjoint-set을 표현하기 위해 사용 서로 중복되지 않는 부분 집합들 포함 관계 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘 두 가지 연산 Find 노드 X가 속해있는 집합 반환 Union (합집합) 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 합치는 연산 접근 Union → 그래프의 노드연결 연결 정보가 주어질 경우 집합을 합쳐야 하는 경우 Find → 어느 그래프에 속해있는지 연결 정보를 가지고 어떤 집합에 속해있는지 찾을 때(반대로 속해있지 않은 경우도) 구현 트리 형태 사용 “부모 포인터 표현” 사용 각 노드에 대해 그 노드의 부모에 대한 포인터만 저장 ..
