algorithm [리메이크 중입니다]
1.[leetcode] Recover Binary Search Tree
문제 조건 파악 실패 : 문제에 2개의 노드가 잘못 배치되어있다고 써있다올바른 이진 트리의 의미이진트리가 맞는지 아닌지 확인할때, 루트의 왼쪽 자식 , 오른쪽 자식만 고려하면 안된다.예를 들어 10 6 20 NULL NULL 5 23 의 경우에는 루트의 왼쪽 자식 오른
2.[leetcode] Validate Binary Search Tree
이진 검색 트리는 루트의 값이 왼쪽 값보다 크다. (같거나 크다가 아님.)마찬가지로 루트의 값이 오른쪽 값보다 작다.트리 문제는 재귀로 해결한다. 하지만 이진 검색 트리에서 왼쪽 오른쪽 크기만을 체크했다가는 틀릴수있다. 예를 들어 5 3 6 1 7 의 경우. 3의 오른
3.[leetcode] Minimum Value to Get Positive Step by Step Sum
O(N)으로 푸는 법 보기 .
4.[백준] 오일러 회로
간선이 여러개 있을 수있다.무향 그래프 == 양방향 그래프adj → 그래프를 표현하는 변수로 사용오일러 회로의 함정 : 간선이 없다면 정점이 서로 떨어져있어도 오일러 회로가 존재한다.check 함수 : 모든 정점에 인접한 간선의 수가 짝수인지 확인한다. 이때 두 정점사
5.[leetcode] Sort List [21-03-25 수정완료]
arr에 해당 linkedlist를 받고 arr를 정렬하여, 다시 linkedlist의 value값을 arr에 있는 값으로 순차적으로 바꾼다.leet code가 마음에 드는 이유 중 하나는 follow up 문제때문이다. 많은 생각을 하게 해준다. 꼭 생각해보자foll
6.[leetcode] Convert BST to Greater Tree
right가 먼저인 중위 순회어려운 문제 아님. 큰 수는 오른쪽 서브트리에 있으니 오른쪽 서브트리를 순회해서 얻은 누적합을 루트에 더하면 된다는 생각으로 풀었다.오른쪽서브트리→루트→왼쪽서브트리 순회이다.순회하면서 루트에 있는 값을 누적한다. 누적합과 루트의 값을 더한값
7.[leetcode] Minimum Window Substring
최적화 가능함. 생각해볼것.s가 t를 포함해야한다. t의 char값을 key로 하고 개수를 값으로 하는 map을 만든다.그리고 map을 reqAlphabet이라고 하자. 투포인터를 사용할것이다. startPointer와 endPointer 두개의 포인터를 사용할것이며,
8.[leetcode] Merge Two Sorted Lists
마지막 삼항 연산자 부분은 l1이 null 이거나 l2가 null이기 때문에 가능하다.Recursion 부분 참고Sort List의 일부
9.[백준] 스도쿠
유의할점 풀이 코드 C++
10.[leetcode] Backspace String Compare
분리된 투포인터 ? 투포인터로 풀어볼것stack을 이용해서 풀었다. time : O(N) space : O(N)투포인터를 이용, space를 O(N)으로 만들수있다. 시도해보자
11.[백준] 별찍기-10
기본 유형별을 만드는 함수와 별을 출력하는 함수 두개로 이루어진다.별을 바로 출력하게 되면 안된다. → 형식이 이상해짐. 따라서 백터로 별을 담고, 해당 백터를 출력한다.별을 만드는 함수는 y,x 를 기준으로 별을 담는다. 만약에 size 가 1인 경우. 바로 담으면
12.[백준] 골드바흐의 추측
X에라스토테네스의 체를 이용, 소수를 구하고 완전탐색을 이용하여 푼다. N의 제한이 1만이기 때문.
13.[백준] 직사각형에서 탈출
점에서 선까지의 최소거리는 수선을 이루는 거리이다.
14.[백준] 네 번째 점
X정렬후 중복을 판단
15.[백준] 직각삼각형
직각삼각형 기본 공식
16.[백준] 택시 기하학
유클리드 기하학 / 택시 기하학 택시 기하학에서의 원의 넓이는 2 R R이된다.
17.[백준] 제로
0일때 pop / 0아니면 push → 결과 : stack의 모든값 더한값
18.[백준] 균형잡힌 세상
전형적인 스택유형균형이 안잡히는 경우 (가 많은 경우 → 처음에 검증)가 많은 경우 → 나중에 검증그냥 문자는 무시. 전형적인 스택유형으로 푼다.
19.[백준] 배수와 약수
일반 행렬 곱셈
20.[leetcode] Same Tree
p와 q 둘중하나 null인 경우 처리하는 부분
21.[leetcode] Flatten Binary Tree to Linked List
O(1) ?flatten(TreeNode\* root) 함수 : Flatten Binary Tree를 만드는 함수.따라서 root의 왼쪽 / 오른쪽을 넣어서 root의 왼쪽과 오른쪽을 Flatten Binary Tree를 만든후 , root의 왼쪽을 root의 오른쪽에
22.[알고스팟] 단어 제한 끝말잇기
오일러 회로와 오일러 트레일의 기본 구현이 문제에서는 오일러 경로일지라도 모든 '정점'이 연결되있어야한다.브루트 포스로 풀수없다. = 100!오일러 경로를 이용해서 푼다. 많은 반복이 필요할것같다. 한번에 유형파악하기는 쉽지 않을것같다.오일러 회로와 오일러 트레일의
23.[leetcode] N-Queens
대각선일때 경우를 잘생각방문처리를 해줘야하는 부분은 Q이 위치한 column / 왼쪽 대각선 / 오른쪽 대각선이 존재한다.대각선을 계산할때는 다음과 같이 계산한다.n=4왼쪽대각선인경우 y+x0 1 2 31 2 3 42 3 4 53 4 5 6오른쪽대각선인경우 n-1-y+
24.[leetcode] N-Queens II
N-Queens와 같다.
25.[leetcode] Combinations
기본 조합 문제
26.[leetcode] Combination Sum
유의할점 풀이 코드 C++
27.Combination Sum II
중복된 원소가 포함된 수열에서 유일한 조합을 뽑는법중복된 원소로 시작해서는 안된다.하지만 중복된 원소를 뽑을수는 있어야한다.조합은 이전에 선택했던 원소를 뽑지 않으면 이루어진다.하지만 중복된 원소가 존재할경우 중복된 조합을 뽑게된다.예를 들면1, 1, 2, 5, 6,
28.[leetcode] Combination Sum III
문제 제대로 읽기sum이 n보다 큰경우 . temp에 저장된 갯수가 원하는 갯수 k 보다 큰경우 → backtracking크기가 k에 도달했을때, sum과 같을때 → 정답크기가 k에 도달했을때, sum과 다름 → backtracking
29.Combination Sum IV
다이나믹 프로그래밍이 언제 필요한가remain에 해당하는 수를 메모한다.remain에 메모되는 수는 remain - numsi의 경우의수의 합이다.음수가 포함될 경우 -1로 초기화하면 안된다. → 최소값 or 최대값음수가 포함될 경우 remain이 0일때 backtra
30.[leetcode] Permutations
유의할점 풀이 코드 C++
31.[leetcode] Next Permutation
순열의 끝순열의 끝은 모든 수가 역순일 때이다. 예를 들면1 2 5 4 3 에서 2 5 4 3은 2로 시작되는 순열의 끝이라고 할수있다.2는 교체되어야 할것이다. 2보다 작은 수로 교체될수는없다. → 이전 permutation즉 2의 바로 직후의 큰수를 구한뒤 교체한다
32.Permutations II
if(i>0 &&numsi-1==numsi && !usedi-1) continue; // 이해하기이미 뽑았던것은 당연히 뽑지 않는다. 안뽑은 나머지 수들 중 중복되는수을 뽑지 않으면서 조합을 만든다.
33.[leetcode] Symmetric Tree
null값의 경우도 넣어주어야한다.루트 - 왼쪽 순회 - 오른쪽 순회는 루트 - 오른쪽순회 - 왼쪽순회랑 거울처럼 행동한다.
34.[leetcode] Maximum Depth of Binary Tree
dfs 탐색하면서 최대값을 찾는다.
35.[leetcode] Balanced Binary Tree
bottom up 보기정의대로 풀었다. 균형잡힌 트리란 , 왼쪽 자식 트리 높이와 오른쪽 자식 트리 높이 차이가 1을 넘지 않는것이다. 또한 왼쪽 자식 트리와 오른쪽 자식 또한 균형잡힌 트리여야한다. 내 코드는 모든 노드들에 대해 균형잡힌 트리인지 판단한다. O(N)각
36.[leetcode] Minimum Depth of Binary Tree
루트가 리프인경우
37.[leetcode] Maximum Depth of N-ary Tree
size = 0 인경우
38.[백준] 좌표 압축
시간 복잡도 계산N = 백만정렬후 중복을 포함하지 않는 배열로 만든 배열의 인덱스가 몇개의 수보다 큰지 알려준다.
39.[leetcode] Convert Sorted Array to Binary Search Tree
정렬된 배열로 균형 잡힌 이진 탐색 트리를 만드려면root의 값이 배열의 중앙값이여야한다.예를 들어 정렬된 배열의 크기가 10이면, 중앙 인덱스값은 5이다. 중앙값을 선정했으므로, 인덱스 1~4 노드는 왼쪽 자식에 들어갈것이고, 6~10는 오른쪽 자식에 들어갈것이다.
40.[leetcode] Construct Binary Tree from Preorder and Inorder Traversal
범위값계산preorder의 index / inorder의 범위가 필요하다.preorder index는 루트를 나타낸다. 해당 인덱스값을 inorder에 대입하면 왼쪽 서브트리와 오른쪽 서브트리로 나눌수있다. 각각의 범위 계산을 잘해야한다.preorder의 index는
41.[백준] 링
유의할점 풀이 코드 C++
42.[백준] 약수
유의할점 풀이 코드 C++
43.[백준] 배수와 약수
유의할점 풀이 코드 C++
44.[백준] 패션왕 신해빈
옷의 종류 / 각 종류에 해당하는 개수가 중요하다.예를 들어 옷의 종류가 2가지이고 각각 2개 1개를 가지고 있다면, 만들수있는 조합의 수는 아무것도 안입는 수를 각각 포함해서 (2+1) \* (1+1) = 6 이된다. 여기서 아무것도 안입는 경우의 수 1을 뺀다.즉
45.[백준] 다리 놓기
최대 400번 만에 조합의 수를 구할수있다.
46.[백준] 검문
M : 같은 나머지를 가지게 하는 수N개의 수들은 다음과 같이 표현가능하다.v0 = q$\_0$ \* M + rv1 = q$\_1$ \* M + rv2 = q$\_2$ \* M + r...vn-2 = q$\_1$ \* M + rvn-1 = q$\_1$ \* M + r위
47.[leetcode]Construct Binary Tree from Inorder and Postorder Traversal
좌표와 개수의 분리저번에 풀었던것(Construct Binary Tree from Preorder and Inorder Traversal)과 유사하다.좌표와 개수의 분리
48.[백준]이항 계수2
메모이항계수1과 같음.
49.[leetcode]Grid Illumination
리턴값lampGriddy.erase(dx)lampGridy.insert(x).second해쉬테이블N-Queens 문제와 같다. 다만 hash table을 이용해야한다. 안그러면 TLE를 먹는다.
50.[leetcode]Convert Sorted List to Binary Search Tree
Linked list 에서 중간 구하기.Linked list에서 중간을 구한다. (fast , slow를 이용한다)중간을 구해서 왼쪽서브트리 / 오른쪽서브트리를 만든다.
51.[leetcode]Path Sum
유의할점 풀이 코드 C++
52.[leetcode]Path Sum II
유의할점 풀이 코드 C++
53.[leetcode]Leaf-Similar Trees
유의할점 풀이 코드 C++ : 내가 짠 코드 C++ : String
54.[leetcode]Binary Tree Paths
유의할점 풀이 코드 C++
55.[leetcode] Number of Closed Islands
내 풀이 : 현재 섬이 엣지를 포함하는지 여부 판단솔루션 : 엣지를 포함하는 섬을 밀어 버린다.시간복잡도 : O(N)
56.[백준] 큐 2
원형큐 구현. 용량을 크게 잡았기 때문에 원형큐로 기능하지는 않는다.
57.[백준] 카드 2
큐 사용
58.[백준]요세푸스 문제 0
큐 구현 / 시간 복잡도 O(N^2)
59.[백준]프린터 큐
우선 순위 큐우선 순위 큐를 활용해서 푼다. 우선순위큐에 있는 순위와 큐에 있는 순위가 동일한지 확인한다.
60.[백준]회전하는 큐
덱을 이용하면 reverse하지 않아도 원소를 빼낼수있다.원소를 빼는 과정은 2번을 사용하거나 3번을 사용해야한다. 둘이 섞어서 사용하는 경우는 무조건 최적이 아니다.
61.[백준]AC
파싱회전하는 큐에 파싱과정이 추가됨.
62.[백준]수 찾기
시간 복잡도일반적으로 하나하나 찾게 되면 O(NM)이므로 1억을 넘는다.정렬후 이분 탐색으로 찾으면 MlogN이므로 시간안에 풀수있다.
63.[백준]숫자 카드2
이분탐색으로 범위를 찾는다. 일반 탐색은 시간초과.
64.[백준]랜선 자르기
이분 탐색으로 적절한 크기를 찾는다.
65.[백준]나무 자르기
랜선 자르기와 동일
66.[백준]공유기 설치
이분 탐색을 두번한다.
67.[leetcode]Count Negative Numbers in a Sorted Matrix
r.begin(), rend() 사용.
68.[leetcode]The K Weakest Rows in a Matrix
compare 함수에 static이 들어가야함
69.[leetcode]Peak Index in a Mountain Array
인덱스-1로 하면 안됨.
70.[leetcode]Intersection of Two Arrays
sort하고 erasenums1와 nums2를 unique하게 만들고 교집합을 찾는다. 투포인터를 이용 두개의 포인터가 가르키는 값이 같을 경우에 정답에 포함한다.
71.[leetcode]Two Sum II - Input array is sorted
유의할점 해쉬 테이블 풀이 투포인터 : O(N) 해쉬테이블 : O(N) 코드 C++ : 투포인터 C++ : 해쉬 테이블
72.[leetcode]Stone Game II
두개의 관점을 하나의 관점으로 생각하는법python에서 memoization을 활용하는 방법 선언만해도 그냥 memo가 된다...presum을 이용함수의 정의 : dp(vector& presum, int p , int m) : 현재 index가 p이고 , 뽑을수있는
73.[leetcode]Filter Restaurants by Vegan-Friendly, Price and Distance
restaurants.sort(key=lambda r:(-r1,-r0)) 두가지 풀이가 있다.소팅 → 필터 적용하면서 ID값만 추출필터 적용 → 소팅 → ID값 접근1번의 경우는 소팅에 O(nlogn)의 시간복잡도를 가진다. 필터 적용하면서 ID값 추출에는 O(n)의