전체 글 (2341) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 802. Find Eventual Safe States https://leetcode.com/problems/find-eventual-safe-statesdfs 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 node별로 state를 저장할 배열을 선언합니다.📔 풀이과정📑 terminal node인지 검사하는 dfs를 구현합니다.기저 반환값을 지정합니다: cycle이 발생한다면 말단이 아니므로 False를 아니라면 말단이므로 True를 반환합니다.중간 계산값을 반환합니다: 현재 node의 state를 1로 만들어주고 이웃이 말단인지 검사해 그 중 하나라도 말단이 아니라면 False를 반환합니다.이웃들이 모두 말단이므로 현 node도 말단이기 때문에 True를 반환합니다.📑 시간 복잡도각 node별로 한 번 씩 검사하므로 O(N.. (Python3) - LeetCode (Medium) : 1267. Count Servers that Communicate https://leetcode.com/problems/count-servers-that-communicate구현 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 행 길이 rows, 열 길이 cols, 정답 변수 can_communicate, 방문여부 배열 ck를 선언 후 적절히 초기화합니다.📔 풀이과정📑 grid의 원소를 순회현재 행에 대해 수평으로, 현재 열에 대해 수직으로 server개수를 세줍니다.📑 방문하지 않았고 통신 가능한 server 개수 세기세준 서버의 개수가 1개를 초과한다면 통신이 가능합니다.해당 조건을 만족한다면 다시 현재 행에 대해 수평으로, 현재 열에 대해 수직으로 방문하지 않은 server개수를 세주며 방문해줍니다.방문하지 않은 server 개수를.. (Python3) - LeetCode (Medium) : 1765. Map of Highest Peak https://leetcode.com/problems/map-of-highest-peakbfs로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 행 길이 rowLength📑 열 길이 colLength📑 인접 방향을 탐색할 배열 dr, dc 및 deque dq📑 순회를 마쳤을 때 배열 정답 변수 grid, 방문여부 ck📔 풀이과정📑 water인 지점에서 얼만큼 떨어져 있는지의 거리가 높이와 같으므로 bfs로 해결가능합니다. bfs함수를 구현합니다.📑 isWater를 이차원으로 순회하며 물인 지점을 먼저 방문하며 각 행,열을 먼저 순회하기 위해 dq에 append합니다.📑 dq에 대해 순회하며 인접한 좌표를 확인하며 범위를 넘지 않으며 방문하지 않았다면 이전 거.. (Python3) - LeetCode (Medium) : 2017. Grid Game https://leetcode.com/problems/grid-game누적합을 이용한 문제였습니다.📕 풀이방법📔 입력 및 초기화열 개수 colLength, 첫 번째와 두 번째 행의 누적합을 구할 prefix_row0, prefix_row1, 정답 변수 result를 선언 후 적절히 초기화합니다.📔 풀이과정📑 robot1의 역할:robot1은 게임에서 최대한 많은 점수를 가져가는 것이 목표입니다.하지만 단순히 점수를 많이 가져가는 것만이 아니라, robot2가 가져갈 점수를 최소화해야 합니다.따라서 robot1은 경로를 선택할 때 robot2가 가져갈 수 있는 점수의 최댓값을 최소화하는 방식으로 움직입니다.📑 robot2의 역할:robot2는 robot1이 지나간 후 남은 점수 중에서 최대한 많.. (Python3) - LeetCode (Medium) : 2683. Neighboring Bitwise XOR https://leetcode.com/problems/neighboring-bitwise-xorxor의 특성을 이용한 문제였습니다.📕 풀이방법📔 입력 및 초기화📑 derived의 xor한 결과를 저장할 xor_sum를 선언 후 0으로 초기화합니다.📔 풀이과정📑 derived 배열의 xor 특성`derived` 배열은 인접한 `original` 배열의 xor 결과로 정의됩니다:$$ derived[i] = original[i] \oplus original[(i+1) \mod n] $$derived 배열의 모든 값을 \(\oplus\)하면:$$ derived[0] \oplus derived[1] \oplus \dots \oplus derived[n-1] $$이를 original 배열로 치환하면: .. (Python3) - LeetCode (Medium) : 2425. Bitwise XOR of All Pairings https://leetcode.com/problems/bitwise-xor-of-all-pairingsxor의 특성에 대해 파악해 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 nums1의 xor을 저장할 xors1와 num2의 xor한 결과를 저장할 xors2를 선언해 각 배열들을 xor한 값을 각각 저장합니다.📑 nums1, nums2의 길이 len1, len2를 선언 후 저장합니다.📔 풀이과정📑 10만이 배열 최대 길이이므로 O(n^2)로 풀 수 없습니다. xor의 특성을 이용해야 합니다. 예제로 살펴보겠습니다. 숫자들을 알파뱃으로 바꿔 표현하면 여러 경우에 대해 다음과 같이 표현할 수 있습니다.1. nums1 = [a,b], nums2 = [c]인 경우 .. (Python3) - LeetCode (Medium) : 2429. Minimize XOR https://leetcode.com/problems/minimize-xor📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 num1, num2를 이진수로 변환하는 bin_num1, bin_num2📑 target_bit_count를 선언 해 필요한 1의 개수를 세줍니다.📑 num1와 xor를 했을 때 문자열 x를 선언합니다.📑 x의 bit 수 bit_count를 선언 후 0으로 초기화합니다.📔 풀이과정1. x XOR num1에서 x가 최소가 되려면 target_bit_count만큼 있으면서 num1와 최대한 같은 자리에 '1'이 존재해야 됩니다. 따라서 target_bit_count를 넘지 않게 bin_num1을 순회하면서 x를 생성해줍니다. 2. 부족한 x를 다듬어줍니다. 2-1.. (Python3) - LeetCode (Medium) : 2657. Find the Prefix Common Array of Two Arrays https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays전수조사 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 B의 원소를 key, index를 value로 defaultdict b_map을 선언합니다. 이후 B의 원소를 순회하며 값에 맞게 저장합니다.📑 A의 길이 length를 선언 후 길이를 저장합니다.📑 정답 변수 ans를 선언 후 빈 배열로 초기화합니다.📔 풀이과정📑 2중 for loop를 수행하며 다음을 진행합니다.1. length - 1까지 for loop를 수행하며 변수 i를 iterator로 증가시키며 현재 확인하려는 index값을 제한합니다.2. 내부에 for loop를 수행해 0.. 이전 1 2 3 4 ··· 293 다음