본문 바로가기

Algorithm202

LeetCode 35 - Search Insert Position (Easy) 💡 문제 LeetCode -35번 🎯 풀이 과정 target 이 배열에 존재할 경우 해당 요소의 index를, 만약 존재하지 않을 경우 target 이 위치해야할 index 를 반환하는 함수를 구현하는 문제입니다. 문제 조건에서 따라 정렬된 배열에서 이분 탐색 을 사용하면 O(logn) 에 해결할 수 있습니다. 👨‍💻 코드 /** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function(nums, target) { let answer = null function findItem(head, tail) { if (head >= tail) { if (nums[head] === target).. 2023. 2. 20.
LeetCode 169 - Majority Element (Easy) 최근 몇달동안 LeetCode 문제풀이를 못했는데, 올해에는 재미와 성취감을 위해 시간 날때마다 짬내서 간단한 문제를 하나씩 다시 풀어보려고합니다. 😄 💡 문제 LeetCode - 169번 🎯 풀이 과정 n 크기의 배열이 주어질 때, 과반수 이상의 요소를 찾는 문제입니다. 해시맵을 이용해서 구현할수도 있지만 좀 더 최적화된 방법으로 해결할 수도 있습니다. 요구조건에 의해 과반수를 차지하는 요소가 반드시 존재한다는 것이 보장되기 때문에 보이어-무어 과반수 투표 알고리즘 을 활용하면 O(n) 의 시간복잡도와 O(1) 의 공간 복잡도를 가지는 풀이를 만들 수 있습니다. 이 알고리즘을 간단히 풀어보자면, 길이 n 을 가지는 배열 A 에서 과반수를 차지하는 요소 a가 [n/2 + 1] 개 있을 경우에 나머지 요소.. 2023. 2. 5.
LeetCode 733 - Flood Fill (Easy) 💡 문제 LeetCode - 733번 🎯 풀이 과정 BFS 를 이용해서 도달 가능한 모든 지점을 확인하는 문제입니다. 여기서 visit 이라는 2차원 배열을 유지하며 중복 방문을 검사함과 동시에 도달 가능한 위치를 기록합니다. 👨‍💻 코드 /** * @param {number[][]} image * @param {number} sr * @param {number} sc * @param {number} newColor * @return {number[][]} */ var floodFill = function (image, sr, sc, newColor) { const dr = [0, 0, 1, -1] const dc = [1, -1, 0, 0] const [ROW, COL] = [image.length, .. 2022. 3. 7.
LeetCode 229 - Majority Element II (Medium) 💡 문제 LeetCode - 229번 🎯 풀이 과정 배열에 담긴 숫자들 중에서 일정 기준값 이상의 숫자들을 찾아서 반환하는 문제입니다. 배열에 담길 수 있는 숫자의 범위가 크기 때문에 해싱을 이용해서 숫자들의 개수를 세어줍니다. 여기서는 객체 대신에 읽고 쓰는 성능이 더 뛰어난 Map 을 사용했습니다. 👨‍💻 코드 var majorityElement = function (nums) { const numCount = new Map(); const pivot = nums.length / 3; for (const num of nums) { if (numCount.has(num)) { const oldVal = numCount.get(num); numCount.set(num, oldVal + 1); } else.. 2022. 2. 22.
BOJ 9094 - 수학적 호기심 문제 백준 온라인 저지 - 9094번 풀이 과정 가능한 모든 조합을 만들어본 다음 주어진 조건을 만족하는 조합의 개수를 구하는 문제입니다. 처음에 a 와 b 의 조합의 개수가 10000개를 넘지 않기 때문에 단순 조합개수를 만들어서 시도했는데 테스트 케이스의 개수 T 를 고려하지 못해서 시간 초과가 발생했습니다. 이를 위해 a, b, m 을 상태변수로 하는 메모이제이션을 적용해서 중복된 계산을 줄이는 방식으로 해결할 수 있습니다. 코드 import sys def solution(): ret = 0 for a in range(1, n): for b in range(a + 1, n): if memo[a][b][m] != -1: ret += memo[a][b][m] continue numerator, deno.. 2021. 9. 12.
BOJ 5076 - Web Pages 문제 백준 온라인 저지 - 5076번 풀이 과정 HTML 문자열을 입력으로 받아서 해당 문자열이 유효한지 판단하는 문제입니다. 열린 태그와 닫힌 태그는 서로 쌍을 이루어야 하기 때문에 (self-closing 태그 제외) 스택 을 이용해서 유효성을 판단하면 됩니다. 이때 주어진 문자열에서 태그를 추출하기 위해 파싱하는 함수를 구현합니다. 태그 정보는 태그 이름, 태그 타입 으로 구성됩니다. 코드 import sys def parse_tag(html): parsed_tags = [] start_parsing = False tag_name = '' tag_type = '' for idx in range(len(html)): if html[idx] == '': tag.. 2021. 7. 19.

티스토리툴바