본문 바로가기

Star43

[Leetcode] 785. Is Graph Bipartite? 문제 : https://leetcode.com/problems/is-graph-bipartite/ 인접한 노드의 색을 현재 노드의 색과 다른 색으로 칠해가면서 너비우선탐색을 진행한다. 칠할 수 있는 색은 두가지이다. 인접한 노드에 색이 칠해져 있지 않다면 현재 노드의 색과 다른 색으로 노드를 칠하고 칠한 노드를 탐색한다. 인접한 노드에 이미 색이 칠해져 있다면 현재 노드의 색과 비교한다 현재 노드의 색과 다른 색이면 유효한경우이다. 현재 노드의 색과 같은 색이면 유효하지 않으므로 false를 반환한다. 시작노드를 첫번째 노드만으로 잡고 너비우선탐색을 한 번만 진행한다면 [그림 1]과 같이 3~6번 노드의 유효성은 체크할 수 없다. 모든 노드를 시작지점으로 잡고 위 방법으로 노드들을 탐색하되 노드의 색 배.. 2022. 4. 29.
[Leetcode] 31. Next Permutation 문제 : https://leetcode.com/problems/next-permutation/ 정수 배열이 있을 때 해당 배열의 요소들의 순서를 바꿔서 사전순 다음 시퀀스로 만들어라. 만일 불가능하다면 사전순 가장 작은 순서로 재배열해야한다. 예를 들어, arr = [2, 1, 3]이라면 사전순 다음 순서인 [2, 3, 1]로 재배열 시켜야한다. 전부 내림차순으로 정렬된 순열의 다음 사전순 배열은 이들을 역순한 것과 같다. 예를 들어, arr = [3, 2, 1]의 경우 다음 사전순 배열은 [1, 2, 3]이다. 내림차순된 배열의 다음 사전순 배열을 구하는 방법을 알았으니 내림차순 배열의 가장 앞에 있는 숫자를 해당 숫자보다 큰 수들보다 가장 작은 수로 바꾸면 다음 사전순 배열을 구할 수 있다. 말이 좀.. 2022. 4. 3.
[Leetcode] 287. Find the Duplicate Number 문제 : https://leetcode.com/problems/find-the-duplicate-number/ [1, n] 범위의 정수들로 이루어진 n+1 크기의 배열 nums가 주어진다. 이 배열엔 중복된 숫자가 하나만 존재파는데 중복된 숫자를 구해라. 단, nums 배열은 수정하지 않아야 하고 상수 크기의 추가 공간만 사용해야 한다. Floyd's cycle detection 으로 풀었다. nums 배열은 [1, n] 범위의 정수들로 이루어지고 중복된 숫자는 하나 밖에 없다는 조건을 이용해보자. index -> nums[index] 로 방향이 있는 간선을 연결하면 중복된 숫자가 하나가 존재하므로 순환이 발생하게 된다. 이 순환의 시작점이 중복된 숫자가 될 것이다. 순환의 시작점이 되는 지점(let, .. 2022. 4. 1.
[Leetcode] 316. Remove Duplicate Letters 문제 : https://leetcode.com/problems/remove-duplicate-letters/ 문자열 s가 주어지면 모든 문자가 한 번만 나타나도록 중복되는 문자를 제거하라. 가능한 결과 문자열들 중 사전순으로 가장 작은 문자열을 구하라. 사전순으로 가장 작은 문자열을 구해야 하므로 앞에 있을수록 작은 문자열이 앞에 가야한다. 즉, 현재 만든 문자열에서 탐색 중인 문자를 추가하고자 할 때 정답 문자열에 있는 문자보다 탐색 중인 문자가 작다면 정답에 추가해주어야 한다. 이를 판단하기 위해 스택을 추가한다. 문자열 s를 앞에서부터 탐색하면서 스택에 정답 문자열을 만들 수 있는 문자들을 넣는다. 사전순으로 앞에 있는 문자열을 만들기 위해서는 앞으로 추가될 문자가 현재 정답문자열에 있는 문자보다 .. 2022. 3. 18.
[Leetcode] 847. Shortest Path Visiting All Nodes 문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다. 구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다. 기본 알고리즘은 다음과 같다. 여기서 상태란 node들이 포함된 상태를 의미한다. (참고) 즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다. 중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다. 조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는 중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고, 중간상태에 종료.. 2022. 2. 26.
[Leetcode] 902. Numbers At Most N Given Digit Set 문제 : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/ 내림차순으로 정렬된 숫자 배열 digits와 정수 n이 주어진다. digits 배열의 숫자는 원하는 만큼 재사용 가능하다. digits 수들을 이용하여 숫자를 만들 때, 정수 n보다 작거나 같은 정수들의 갯수를 구하라. 예시를 직접 풀면서 알아보자. digits = ["1", "3", "5"], n = "355" 입력 값이 위와 같을 때, 일의 자리(x), 십의 자리(xx) 수들은 모두 정답에 포함된다. 따라서 이들 개수는 정답에 미리 더해둔다. x 에 digits 들 중 어느 숫자가 와도 상관없으므로 조합을 생각하면 각 자리에 3개의 수가 올 수 있으므로 일의 자리의 경우의 수는.. 2021. 12. 19.

티스토리툴바