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와 다음을 가리키..
day--;
2022.01.17 알고리즘 공부. 연결리스트 알고리즘 문제를 풀기위해 기본 이론을 공부를 하고 문제를 푼다고 생각을 하였다. 하지만 오늘 알고리즘 수업을 듣고 알고리즘 수업이 무엇인지 다시금 옛날의 생각이 떠올랐다. 결국 알고리즘은 자료구조를 이용한 문제를 원한다. 즉, 알고리즘 문제를 풀기위해서는 자료구조를 완벽하게 이해를 하고 있어야 한다는 것이다. 물론 언어의 문법과 익숙함이 중요하지만 무엇보다 내가 사용하고자 하는 자료구조를 완벽히 알았냐는 것이다. 링크드 리스트를 사용하지만 왜 안되지... 왜 안되지... 보니 링크드리스트는 파이참에서 임포트하여 구성되어 있는 클래스가 아니였다. 내가 직접 해당 클래스를 만들어 해당 클래스 함수들을 구현하여야 하는 것이다. 그래야 문제의 답을 보더라도 빠르게 ..
연결리스트 만들기 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 좀 더 효율적인..
문자열 배열을 받아 애너그램 단위로 그룹핑 def anagramsGroup(words)-> List(List(str): anagrams = collections.defaultdict(list) for word in words: anagrams[''.join(sorted(word))].append(word) return angrams.values() if __name__ == "__main__": words = ["price", "ceipr", "cpire", "criep", "creep", "preec", "low", "wol", "wwws", "swss", "brian"] anagrams(words) 코드가 짧다. 그 만큼 함수를 충분히 이해하고 잘 알고 있어야 한다. 하나씩 천천히 살펴보겠다. ana..
day--;
2020.01.15 하.. 오늘 뭐했지..? 알고리즘 수업이 드디어 시작되었다. 수업(?) 수업이라고 할게 있었나? 그저 혼자 읽고 또 읽고 이론활용을 어떻게 하는지 공부하였다. 우선, 공부를 하면서 힘들었던 점이 있다면 파이썬 문법이 부족하다는 것이다. 해설을 마치 이해한듯이 읽었지만 코드를 이해 못하니 제대로 이해하고 습득한게 아니었다. 본격적으로 알고리즘 수업이 들어간 만큼 이론에 집중하기 보다는 이론을 적용한 코드를 무식하게 외우고 다시금 복습하여 적용해야 겠다는 생각을했다. (사실 무식하게 공부하는 방법이 지식을 쌓는데 가장 pure 한 방식이라고 생각한다.) 이번에는 어떤 누군가에게 피해를 주고 싶지 않고, 내가 뒤쳐져 있다는 느낌을 받고 싶지 않기에 지치더라도 스스로를 꾸짖고 앞으로 나아가야..