Jamie's CodeSprout

개인적으로 공부하면서 지속적으로 정보를 추가, 수정, 삭제합니다. 정확하지 않은 부분은 피드백 주시면 감사합니다. 2022-11-14 파이썬 TypeError: unhashable type 참고: https://daewonyoon.tistory.com/363 무엇? list1 = [1, 2, 3] set1 = set([1, 2, 3]) d = {} d[list1] = "리스트를 딕셔너리 키로 지정 불가능" d[set1] = "집합을 딕셔너리 키로 지정 불가능" >>> TypeError: unhashable type 파이썬에서 딕셔너리의 키를 지정할 때 리스트 자료형을 지정할 때 발생하는 에러 왜? unhashable이란 해쉬화를 할 수 없다는 뜻으로, 해쉬화란 value에 고유한 라벨을 붙여 주는 것과 ..

2022-11-13 백준 파이썬 1197번 최소 스패닝 트리 출처: 무엇? 최소 신장 트리 (minimum spanning tree)를 구현하는 문제 왜? 일반 리스트를 사용해서 여러번 도전해봤는데 시간 초과. 처음에 엣지들이 양방향이라는 조건도 놓치기 쉬웠다. 어떻게? ▽ 솔루션을 참고하여 주석을 달아 본 정답 코드 import sys import heapq V, E = map(int, sys.stdin.readline().split()) # 노드 개수, 엣지 개수 covered = [0] * (V+1) # 방문한 노드들 리스트 edges = [[] for _ in range(V+1)] # 엣지를 담을 리스트 sum_min_w = 0 # 최소 가중치의 합 for e in range(E): src, ds..

2022-11-12 백준 5639번 파이썬 이진 검색 트리 출처: https://velog.io/@yujng/백준-5639번이진-검색-트리-파이썬Python 무엇? 이진 검색 트리의 전위 순회 한 값을 후위 순회로 출력하는 문제. 왜? 입력부터 어떻게 받아야 할 지 난감했던 문제… (지금까지의 문제는 몇 번 입력 받겠다는 조건이 있었는데…😮) 비슷한 로직으로 for + append를 열심히 해보다가 이렇게 복잡하게 안 해도 될거 같은데… 싶어서 솔루션 참고. 재귀의 신기한 점은 이렇게만 해가지고 이게 된다고? 싶은데 진짜 된다는 점. (오히려 거기서 더 복잡하게 들어가서 내가 뭔갈 해보려고 하면 에러 나는 거 같다.) 어떻게? 코치님이 이진 검색 트리를 재귀로 해결할 수 있다고 했는데, 이게 그 케이스 ..

2022-11-11 그래프란, 트리와 그래프의 차이 출처: https://bigsong.tistory.com/33 https://nulls.co.kr/graph/112 무엇? 자료구조 노트에 정리함 왜? 이번 주 키워드는 트리와 그래프! 어떻게? 자료 구조의 분류 출처: https://ko.wikipedia.org/wiki/자료_구조 https://bigsong.tistory.com/30?category=965745 무엇? 자료구조 노트에 정리함 왜? 자료구조의 종류와 개념을 전체적인 관점에서 서로 어떻게 연관되어 있고 분류되는지 알 필요가 있다. (지금 어디쯤 공부하고 있는 건지 되짚어보기) 어떻게?

파이썬에서 heapq 모듈로 최소 힙, 최대 힙 구현하기 출처:https://velog.io/@yyj8771/Python-heapq를-이용한-최소-힙-최대-힙 무엇? heapq 최소 힙, 최대 힙을 만들 때 주의할 점은 디폴트에 최소 힙 구현에 맞춰져 있어서, 최대 힙을 만드려면 push할 때 -1을 곱한 값으로 넣어주고, pop할 때도 -1을 곱한 채로 빼야 정상 작동함! pop할 때 배열이 비어있으면 인덱스 에러 뜸 heap = [] 힙으로 사용할 배열 선언 메소드 heapq.heappush(배열, 값) : 최소 힙에 push heapq.heappop(배열) : 최소 힙에서 가장 최솟값 pop heapq.heappush(배열, -값) : 최대 힙에 값 push -heapq.heappop(배열) : 최..

2022-11-07 힙 & 힙 정렬 & 우선순위 큐의 개념 출처:https://www.boostcourse.org/cs113/lecture/540275 https://www.edwith.org/intro-data-and-algo-2-2018/lecture/21489?isDesc=false https://www.edwith.org/intro-data-and-algo-2-2018/lecture/21491/?isDesc=false https://jackpot53.tistory.com/6 무엇? heap 구조는 배열이면서 완전 이진 트리(complete binary tree)로 시각화가 가능하고, 왼쪽부터 다음 인덱스의 노드를 채워 간다. 이러한 힙 구조를 유지하면서 부모 노드가 자식 노드보다 항상 큰 값을 가..

2022-11-05 곱셈 백준 1629번 파이썬 출처: https://velog.io/@grace0st/곱셈-백준-1629번-파이썬 왜? (AxB)%C = (A%C) * (B%C) % C을 이용했으나 (AxA^B-1)%C = (A%C) * (A^B-1%C) % C 처럼 공식을 세웠고, A^B-1 = A * A^B-2 라고 생각해서 B자리에 B-1을 넣는 재귀 함수를 만들었다. 메모리 초과로 실패. 어떻게? 분할정복으로 해결하는데, 나머지 분배 법칙 (AxB)%C = (A%C) *(B%C) % C 지수법칙 A^m+n = A^m x A^n 을 이용한다! 지수법칙을 따를 때, 참고 블로그처럼 A^11 = A^5 * A^5 * A 이렇게 사용해야하지, 내가 한 것처럼 A^11 = A * A^11-1 이렇게 해버..

2022-11-03, 2022-11-04 이진탐색 강의 출처: https://www.edwith.org/knu-algorithm/lecture/170169?isDesc=false 무엇? binary search. 리스트의 범위를 반씩 줄여나가며 탐색하는 방법. 분할정복 알고리즘 설계법을 이용한 방법 中 하나. 왜? 어떤 값을 탐색하기 위함. 완전탐색보다 시간이 덜 든다 (빅O가 logN) 길이가 80인 리스트를 완전 탐색하면 80번 뒤져야 하지만, 이진 탐색은 log80 (계속 이등분 하기 땜에) 어떻게? 값이 정렬되어 있음을 전제함 low, mid, high 값을 지정하고, mid와 low, high의 값을 비교한 뒤, 오른쪽으로 갈 지 왼쪽으로 갈 지 정함. 그러면서 서서히 리스트의 탐색 범위를 줄여..

2022-11-02 순열조합 itertools & 순열과 조합의 차이 출처: https://seu11ee.tistory.com/5 https://jwdeveloper.tistory.com/270 https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations 무엇? 순열은 'order’가 중요하여, 순서가 다르면 다른 경우의 수에 해당하지만, 조합은 순서가 상관없다! ex) 순열은 1,2,3,4와 4,3,2,1이 다른 경우의 수이지만, 조합에서 둘은 하나의 경우의 수 파이썬에서 순열, 조합을 도와주는 모듈은 itertools 왜? 완전탐색 할 때 필요 (무턱대고 이론 공부 안하고 시작해서 문제 잘 안 풀렸다. 괜히 이론 공부부터 ..

2022-10-30 0!는 1이다 😮 출처: https://johnleeedu.tistory.com/23 왜? 문제에서 팩토리얼 개념을 만나서 아리송해서 찾아 봄 어떻게? 2! = 2 * 1! 3! = 3 * 2! 처럼 n! = n * (n-1)! 이 성립하려면, 1! = 1 * 0! 일때 0!이 1이어야 함! 재귀 깊이 설정하기 출처: https://help.acmicpc.net/judge/rte/RecursionError 왜? 백준 문제 풀다가 가끔 재귀 에러가 뜰 때, 재귀 깊이를 더 높게 설정해주어야 함 어떻게? import sys sys.setrecursionlimit(10**6) set는 sort가 없음! 어떻게 정렬하나? 출처: https://programmer-ririhan.tistory...