크래프톤 정글

1. 1197 최소 스패닝 트리 import sys input = sys.stdin.readline # 크루스칼 알고리즘을 이용한 풀이 v, e = map(int, input().split()) edges = [[int(x) for x in input().split()] for _ in range(e)] edges.sort(key=lambda x: x[2]) # weight 기준으로 정렬 # 부모를 저장할 테이블 parent = [0] * (v + 1) for i in range(1, v+1): parent[i] = i result = 0 # 재귀적으로 탐색하며 부모를 return def find_parent(parent, n): if n != parent[n]: parent[n] = find_paren..

자료구조 B-Tree B트리란? B트리는 디스크나 다른 직접 접근 보조 기억장치에서 잘 동작하도록 설계된 균형잡힌 트리이다. B트리의 특징 이진트리와 다르게 하나의 노드에 여러개의 값을 가질 수 있다. 최대 M(B트리의 차수)개의 자식노드를 가질 수 있다. 3차 B트리라면 3개의 자식을 가질 수 있다.(leaf 노드 제외) 각 노드는 ⌈M/2⌉개의 key를 저장한다. 데이터 삽입 추가는 항상 leaf에 삽입한다. 노드가 넘치면 가운데 key를 기준으로 좌우 key들을 분리하고 다운데 key는 승진한다. 노드가 넘친다? 각 노드가 가질 수 있는 최대 M-1개의key를 초과한 경우를 뜻함 데이터 삭제 데이터의 삭제는 리프 노드에서만 이루어진다. 여기서 리프 노드가 아닌 노드에서 삭제를 시도할 경우, 가장 좌..

CS:APP 1.7.3 쓰레드 쓰레드란? 프로세스는 여러개로 나뉘어서 작동하는데, 여기서 나뉜 프로세스들은 쓰레드라고 한다. 단일코어 환경 단일 코어 환경에서 쓰레드들을 병렬적으로 처리하는 방법은 시분할 방식으로 실행되는데, 이는 사실 완전히 병렬적으로 데이터를 처리하는 것이 아닌, CPU가 매우 빠르게 각 쓰레드를 번갈아가며 작업한다. 다중코어 환경 다중코어 환경에서는 병렬적으로 작업이 가능하며, 각 코어가 독립적으로 쓰레드를 실행할 수 있다. 1.7.3 가상 메모리 가상 메모리란? 하나의 프로세서가 전체 메모리만큼, 혹은 그 이상의 주소까지 접근할 수 있게 가상의 메모리 주소를 제공하는 기술. 여기서 가상의 메모리 주소는 MMU에 의해 물리적 주소로 변환된다. 가상 메모리는 프로그램이 필요로 하는 메..

알고리즘 시험 1. 1110 더하기 사이클 저번에 풀이한 방법은 while문을 사용해서 풀었길레 이번엔 재귀를 사용해서 풀이했음. 2. 1182 부분수열의 합 파이썬 내장 모듈 사용 안하고 풀려다가 시간 엄청 까먹었다... 그냥 모듈 사용하고 3번으로 갈걸 3. 1992 쿼드트리 import sys input = sys.stdin.readline def solve(x, y, total_length): global res if total_length

백준 문제풀이 1. 2740 행렬곱샙 혼자 2중for문으로 풀려다가 시간 다날리고 결국 풀이를 확인했다. 좀만 더 생각해보면 간단히 해결할 수 있는데 너무나도 아쉬운 문제. 2. 2468 안전 영역 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline # 1 = 강수량 1 ~ n+1 # 전체 탐색 시작 result = 0 def search_safe(result, max_value): for i in range(0, max_value + 1): visited = set() safe = 0 for y in range(n): for x in range(n): safe += dfs(i, x, y, visited) result = max(resu..

뇌가 녹아내릴것같다. 그동안 비교적 쉬운 초급 - 중급 문제를 풀다가 상급 문제에 비벼보려고 하니 정신이 나가버릴것같다. 백준 문제풀이 1. 1655 가운데를 말해요 처음엔 단순 힙을 구성하고, 중간에 위치한 노드의 자식을 탐색하는 식으로 도전했다가 도저히 안돼서 결국 답지를 봤다. 해당 풀이는 평균보다 높은 값을 저장하는 최대힙과 최소힙을 생성하고, 총 숫자의 수가 홀수일땐 최대힙에, 짝수일땐 최대힙에 값을 집어넣고, 서로의 루트를 비교한 뒤 더 작은 수를 left의 루트로 설정하는 방식으로 풀이했다. 2. 2805 나무자르기 간단하다. (답지봄) 목표값에 해당되는 값이 나올때까지 범위를 조정해가며 반복한다. 3. 9663 N-Queen 이것도 좌표 압축까지는 성공했는데 결국 조건 설정을 못해서 답지를..

백준 문제풀이 1629 곱셉 귀납법 써서 풀었음 하노이의 탑 생각하면서 푸니깐 실마리가 보였다. 2493 탑 탑의 갯수만큼 배열을 선언하고, 스텍에 탑을 쌓은 뒤, 조건에 부합하면 해당 인덱스에 탑의 위치를 넣어주는 방식으로 해결했다. 골드치고는 쉬운편 2504 괄호의 값 이건 디버깅을 하며 보면 이해가 편한데 괄호가 닫히기 전까지의 해당 괄호의 값을 곱해준다고 생각하면 편하다. 현재 값의 상태를 저장해두는 tmp와 그렇게 괄호가 닫히면 현재 값을 저장해주는 result를 선언해서 풀었다. 2630 색종이 전형적인 분할정복 문제. 3일 연속으로 재귀만 지긋지긋하게 봤더니 어렵지 않게 풀었다. 3190 뱀 from collections import deque # 방향 : 우 상 좌 하 direction =..

1. 1181 단어정렬 문자열을 나눠서 정렬해보고 싶었지만 풀어야 할 문제가 많이 남아, 좀 더 활용하기 좋은 문제에서 사용해보기로 했다. 2. 1920 수찾기 # 일곱난쟁이 온몸비틀기 import sys input = sys.stdin.readline def binary_search(start, end, target): if start > end: print(0) return mid = (start+end) // 2 if arr[mid] == target: print(1) return elif arr[mid] target: binary_search(start, mid - 1, target) #..

매일매일 딱딱한 말투로 TIL만 작성하려다 이렇게 내 이야기를 써 내려가는 시간이 어색하게만 느껴지는건 어쩔 수 없는것같다. 내 인생을 돌아보면 뚜렷한 목표 없이 항상 앞만 보며 달려왔던 것 같다. 마이스터 고등학교 졸업부터 조금 이르게 시작한 사회생활, 계속해서 반복되는 생활이 싫어 도피성으로 시작했던 사업들, 사업을 정리하고 발생한 손실을 만회해야겠다는 일념 하나로 시작했던 방역 업무, 마지막으로 지금 책상앞에 앉아서 에세이를 작성하고 있는 지금의 나까지. 이렇게 나열해놓고 보니 내 삶은 정말 부산스러웠다는 것 하나는 확실하게 알 수 있네. 부산스럽게 살아 온 만큼 내가 지금까지 이뤄왔던 결과물 또한 부산스러운 것 같다. 하나에 집중하지 못하고 이곳저곳 찔러봤던 지난 나날들을 보면 단순 '좋은 경험 ..

오늘 발표를 마무리 하고 이제 본격적으로 알고리즘 학습주차에 접어들었다. 본격적으로 알고리즘 학습주차에 들어가기 전 백승현 코치님께서 기본적으로 알고 가야 할 개념들에 대해 한번씩 집어주셨다. 알고리즘을 시작하기 전 정확히 알고있어야 하는 개념들 1. 링크드 리스트, 배열 링크드 리스트와 배열은 비슷한 개념으로 이해하면 된다. 링크드 리스트는 각 메모리가 연속되어 나열되는 배열의 개념과는 다르게 현재 값과 다음 순서의 자료가 있는 주소를 가르키는 데이터를 하나의 노드로 묶어 배열을 구성한다. 링크드 리스트와 단순 배열의 가장 큰 차이는 저장된 값의 배열이 메모리 상에 연속되는지 아닌지 차이다. 장점 단점 배열 배열의 경우 정적 자료구조에 해당하며, 최초 할당 시 미리 크기를 정해놓게 되어 연속된 메모리 ..