∠( ᐛ 」∠)＿

🔍 위상 정렬 대학교 전공 시간에 교수님이 전공 선수과목 구조를 예로 들어주셨던 것이 어렴풋이 기억난다.. 핵심 이론과 구현 방법을 간단히 정리해 보려 한다. Do it! 알고리즘 코딩테스트 도서를 참고하였다. 📃 개념 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 항상 유일한 값으로 정렬되지는 않음! 진입 차수 = 자기 자신을 가리키는 에지의 개수 진입 차수 리스트를 업데이트한다. 진입 차수 리스트 중 진입 차수가 0인 노드를 선택하여 정렬 리스트에 저장한다. 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. 모든 노드가 정렬될 때까지 2 ~ 3 과정을 반복한다. 항상 유일한 값으로 정렬되지 않는 이유 => 2번 과정에서 진입 차수가 0인 노드가 여러 개 존재할 수 있기 때문에 🐍 코..

🔍 유니온 파인드(Union-Find) 해당 알고리즘이 있는 것은 알았는데 어떤 식으로 구현해서 사용하는지는 모르고 있었다. 유니온 파인드와 관련된 코테 문제들을 풀게 되었고, 이참에 유니온 파인드 알고리즘에 대해 아주 간략하게만 정리해보려 한다. Do it! 알고리즘 코딩테스트 도서를 참고하였다. 📃 개념 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산 1차원 리스트를 사용한다. 처음엔 아무것도 연결되어 있지 않은 상태이므로 각 노드가 모두 대표 노드이다. 따라서, 자신의 인덱스값으로 초기화 해준다. parent = [0 for _ in range(n + 1)] for i in range(n + 1): pa..

백준 1167 트리의 지름 특정 원소가 리스트의 몇 번째 인덱스에서 등장하는지 찾아야 했다. indexOf()가 안되길래 검색해보니 indexOf()는 자바스크립트 문법이었다.. 이참에 잘 정리해두자. 위치(인덱스) 찾는 함수 2가지 find() a = 'abcdab' print(a.find('a')) # 0 print(a.find('c')) # 2 print(a.find('bcd')) # 1 => 문자열의 위치를 찾을 수도 있음 print(a.find('a', 2)) # 4 => 시작점만 지정한 경우 print(a.find('a', 2, 5)) # 4 => 시작점과 끝점을 지정한 경우 print(a.find('..

/와 //가 헷갈려 정리해본다. "/": 기본적인 나눗셈, 결과는 항상 float 형 a = 10, b = 3 => a / b 결과는 3.3333333333333335 a = 10, b = 2.5 => a / b 결과는 4.0 "//": 나눗셈의 몫 a = 10, b = 3 => a // b 결과는 3 (int) a = 10, b = 2.5 => a // b 결과는 4.0 (float) "%": 나눗셈의 나머지 a = 10, b = 3 => a % b 결과는 1 (int) a = 10, b = 2.5 => a % b 결과는 0.0 (float) "divmod(a, b)": 나눗셈의 몫과 나머지, 나눗셈 연산을 수행할 변수 2개가 필요하며 결과는 항상 튜플 형식! a = 10, b = 3 => divmod..

🔍 우선순위 큐와 힙(PriorityQueue & heapq) 우선순위 큐(힙 큐) 문제들을 분명 풀었던 기억이 있는데, 그때도 얼렁뚱땅 풀었던 기억이 난다. 오늘 절댓값 힙(백준 11286번) 문제를 푸는데, 우선순위 큐는 기억이 나지 않아 deque로 풀어보니 역시나 시간초과가 났다. 이참에 우선순위 큐에 대해 정리해놓아야겠다 생각이 들어 작성해 본다. 대략적인 개념과 파이썬에서의 사용 방법을 정리해보려 한다. 공식 문서와 이것이 코딩 테스트다, 기타 블로그 등을 참고하였다. 📃 우선순위 큐(Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 데이터를 우선순위에 따라 처리하고 싶을 때 사용함 구현 방법 2가지 리스트를 이용하여 구현 (삽입: O(1),..

프로그래머스 레벨2 이진 변환 반복하기 10진수에서 2, 8, 16진수 변환 bin(), oct(), hex() 함수 사용, 결과는 문자열 타입 format() 함수 사용, 두 번째 인자에서 # 제거 시 접두어가 빠진 결과 얻을 수 있음 value = 30 b = bin(value) # 0b11110 o = oct(value) # 0o36 h = hex(value) # 0x1e b1 = format(value, '#b') # 0b11110 b2 = format(value, 'b') # 11110

프로그래머스 레벨2 JadenCase 문자열 만들기 string.upper() => 모든 문자열이 대문자로 바뀐 문자열을 반환함 (기존의 문자열이 변경되는 것이 아님) string.lower() => 모든 문자열이 소문자로 바뀐 문자열을 반환함 ( 〃 ) string.isupper() => 모든 문자가 대문자인지 검사하는 함수, 모두 대문자인 경우에만 True 반환 string.islower() => 모든 문자가 소문자인지 검사하는 함수, 모두 소문자인 경우에만 True 반환

🔍 에러와 예외(try, except, raise..) 그동안 알고리즘 문제를 풀 때 인덱스를 벗어나는 등의 오류가 발생했을 때 범위를 제한하거나 다른 풀이를 모색해왔는데, 친구가 "try except문 쓰면 되는 거 아니야?"라고 말해준 뒤로, 정말 많이 애용하고 있다.(그동안 왜 생각을 못 했지..) 파스칼의 삼각형 문제(SWEA 2005번)를 풀면서 try-except를 사용하여 인덱스가 음수인 경우 예외 처리를 해주었는데, 파이썬에서는 인덱스가 음수여도 배열 끝을 기준으로 요소에 접근할 수 있다는 것이 문제였다. '인덱스가 음수인 경우 아예 의도적으로 예외를 발생시킬 순 없을까?' 하고 찾아본 결과 raise문을 사용하면 해결이 가능함을 알게 되었고, 이참에 정리를 해놓아야겠다 생각..