""" N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 단, 이 문제의 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 입력 예시 7 2 1 1 2 2 2 2 3 출력 예시 4 """ import bisect """ 해당 문제를 푸는데 기억해야할 것은 '정렬'된 배열이라는 것이다. 즉, target의 숫자의 가장 왼쪽과 오른쪽 idx를 구한 후 해당 idx의 차이를 반환하면 된다. """ def solution(lst, target): left_idx = bisect.bisect_left(lst, target) if not (0
https://leetcode.com/problems/search-in-rotated-sorted-array/ Search in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly r..
이진탐색 정렬된 배열을 절반씩 줄여나가면서 탐색하는 기법 https://leetcode.com/problems/binary-search/ Binary Search - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 구현 def bs1(lst, target): def bs(start_index, end_index): # start_index 와 end_index가 == 경우 해당 값을 찾은 경우 이므로 -1을 리턴하면 안된다. if start_index > end_..
Given an m*n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. (동서남북(o) / 대각선 (x)) You may assume all four edges of the grid are all surrounded by water. Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0..
DFS (GRAPH)
DFS - Depth First Search 깊이 우선 검색 위와 같이 DFS는 움직인다. DFS 표현 2 - 3 ⎜ 0 - 1 **1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!** 0 1 2 3 0 X O X X 1 O X O X 2 X O X O 3 X X O X 이걸 배열로 표현하면 다음과 같습니다! graph = [ [False, True, False, False], [True, False, True, False], [False, True, False, True], [False, False, True, False] ] **2. 이번에는 인접 리스트로 표현해보겠습니다!** 인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장합니다. 0 -> 1 1 -> ..
스택구현하기 (LIFO) Queue 큐 구현해보기 테스트코드 def test_node(): # 노드가 제대로 되는 것인지 확인을 하기 위한 코드 # Node 객체에 item 1을 넣고 다음을 가리키는 것은 없다. # 해당 값의 item이 넣은 것과 같냐 라고 test한다. assert Node(1, None).item == 1, "아이템 값을 바꾸면 ERROR!" def test_queue(): queue = Queue() queue.push(1) queue.push(2) queue.push(3) queue.pop() == 1 queue.pop() == 2 queue.pop() == 3 queue.is_empty() 큐의 공간을 왔다갔다 하는 Node가 있어야 한다. Node는 value와 다음을 가리키..
연결리스트 만들기 class ListNode: def __init__(self, val): self.val = val self.next = None head_node = ListNode(1) head_node.next = ListNode(2) head_node.next.next = ListNode(3) head_node.next.next.next = ListNode(4) def printNoded(node:ListNode): crnt_node = node while crnt_node is not None: print(crnt_node.val, end=' ') crnt_node = crnt_node.next def printNodeRecur(node:ListNode): print(node.val, end=..
한 번의 거래로 낼 수 있는 최대 이익을 산출하라. input : [7,1,5,3,6,4] output : 5 >> 1 일 때 사서 6일 때 팔면 5의 이익을 얻는다. 해당 문제는 가장 저점일 때 구매하여 고점일 때 판매하면 되는 것이다. 그렇다면 우리는 가장 간단하게도 이중 for문을 돌려 비교하여 사고팔고를 반복하여 결과를 산출 할 수 있다. 하지만 그럴경우 O(n^2) 의 많은 실행시간을 허비한다. def max_profit(prices): profit = 0 for i, price in enumerate(prices): for j in range(i, len(prices)): max_price = max(prices[j] - price, max_price) return profit 좀 더 효율적인..