본문 바로가기

분류 전체보기351

[알고리즘] 정렬 - Merge Sort Merge sort 합병정렬 - 재귀를 사용하는데 자꾸 까먹어서 정리한다. - 크게 3부분으로 나뉜다. divide conquer combine Divide: 배열을 mid를 중심으로 두 부분으로 나눈다. 배열 사이즈가 1이 될때까지 반복한다. Conquer: 부분 배열을 정렬한다. 배열 size가 1일떄만 진행한다. Combine: 정렬된 배열을 합병한다. - 머지 소트를 하기 위해선 sorted된 리스트를 저장하기 위한 추가 배열이 필요하다. divide와 conquer: 배열 사이즈가 1일때까지 쪼갠다. merge: 정렬된 배열 2개를 하나의 sorted에 합친다. 시간 복잡도 O(NlogN) #include #define MAX_SIZE 1000000 + 1 int arr[MAX_SIZE]; //.. 2020. 11. 1.
[leetcode 169] Majority Element Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2 문제 풀이: 난이도 easy 처음에 맵을 써서 풀었는데 그것보다 더 쉬운 방법이 있었다...! 소팅한 다음 중간에 위치한 값을 리턴하면 됐다.. class Solution .. 2020. 11. 1.
[백준 13913] 숨바꼭질 4 www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS후에 경로까지 추적하는 문제이다. BFS할때마다 경로를 저장하면 시간초과가 난다. 따라서 마지막 목적지에 도달했을 때 경로를 역추적해야 한다. 경로 역추적을 위해 부모노드를 저장했다. #include #include #include #define MAX 100000 + 1 using namespace std; int path[MAX] = { 0, }; int parent[.. 2020. 11. 1.
[leetcode 236] Lowest Common Ancestor of a Binary Tree Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: .. 2020. 10. 31.

티스토리툴바