파이썬 썸네일형 리스트형 프로그래머스 - 등굣길 문제 물 웅덩이가 없는 칸만으로 학교에 갈 수 있는 경로의 수를 구하라 입력값 m: 가로 길이 n: 세로 길이 puddles: 물에 젖은 지역들 좌표 제한사항 1 더보기 사이클 감지하기 leetcode 141. Linked List Cycle 문제풀이 문제: 주어진 연결리스트에 사이클이 있다면 true를 없다면 false를 반환하라 Hash Set 1. 각 노드를 set에 추가해가며 순회한다. 2. 다음에 순회할 노드가 이미 set에 들어있다면 true를 반환. 3. 순회를 무사히 마쳤다면 사이클이 없는 것이므로 false를 반환. 모든 노드를 set에 저장하려면 O(N)공간이 필요하다. set에 노드를 저장하는 것 대신, 노드의 val값에 이미 방문했음을 표시한다면 메모리를 아낄 수있다. Two Pointer 투 포인터 테크닉을 활용해서도 공간복잡도를 O(1)으로 제한할 수 있다. 투 포인터 테크닉은 한 포인터는 더 빠르게 또 다른 포인터는 더 느리게 움직이도록하는 테크닉을 말한다. .. 더보기 파이썬 매직 메서드, Python Magic Method Cheatsheet. Magic Method Python Concept Sentence __getitem__(key) 첨자형 객체 Subscriptable Object : 인덱싱이나 슬라이스에서 사용된다. object[key] object[i:j] object[i:j:k] __enter__() __exit__() 컨텍스트 매니저 Context Manager : 주로 리소스관리를 위해 사용된다. 일반적으로 할당된 리소스를 모두 해제할 때 사용한다. with object: __iter__() __next__() 이터러블 객체 Iterable Object : 반복가능한 객체. 예를 들면 for문을 사용해 값을 반복적으로 가져올 수 있는 list, tuple, set, dict이 여기에 해당한다. 내장 반복형 객체만 말하는 것이 아.. 더보기 Sieve of Eratosthenes, 에라토스테네스의 체 에라토스테네스의 체Sieve of Eratosthenes는 2부터 n까지의 숫자 중 모든 소수prime number를 찾기 위한 간단한 알고리즘이다.1. 오름차순으로 2 부터 n까지의 모든 숫자를 set={ 2, 3, ..., n} 집합에 갖고있다.2. 아직 처리하지 않은 숫자 중 가장 작은 숫자를 선택한다.3. 해당 숫자의 배수들을 집합에서 모두 지운다. 4. 2로 돌아간다. 끝. 위의 방법으로 모든 합성수들을 집합에서 지울 수 있다. 하지만 2-4번을 N번 반복하는 코드를 작성한다면 O(n**2)시간이 걸릴 것이다. O(n log log n) 시간 걸리는 코드를 작성하기 위해서는 합성수composite number를 제거하는 동작의 중복을 줄이면된다.- 모든 합성수composite number 는 최.. 더보기 이전 1 다음
