잡담연구소

3주차 이번 주 주제는 이었다. 1) 삽입정렬이란? 갓키백과에 따르면 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 그냥 자신의 이전부분과 비교해가며 자신의 자리를 찾아 삽입하는 정렬 알고리즘이다. 2) 삽입정렬 원리 엄청 간단하다. 정렬되어있는 자기 인덱스 이전부분(왼쪽)만 바라보며 자기의 자리를 찾아가면 된다. 1. 설정한 피봇을 temp등으로 저장해놓고 자신보다 인덱스가 작은 쪽으로 (왼쪽) 내려간다. - 그렇기 때문에 1번 인덱스부터 pivot이 될 수 있다. 2. 자신의 값보다 큰 값이 나왔다면 오른쪽으로 한칸씩 민다. ex) 1 4 5 3 에서 피..

class를 이용해서 트리랑 트리순회를 구현을 하던데 도저히 혼자 못할 거 같아서 참고했다,,,ㅜㅜ www.fun-coding.org/Chapter10-tree.html 완전 잘 정리해놓으셨다. 그래도 삭제할때 양쪽 다 자식노드가 존재하는 경우가 너무 어렵고, 이해가 안돼서 직접 그려서 이해했다... 1) delete #4 : 양쪽 자식이 다 존재하는 경우 , 최솟값 노드의 오른쪽 자식이 존재하는 경우 2) delete #4 : 양쪽 자식이 다 존재하는 경우 , 최솟값 노드의 자식이 존재하지 않는 경우 # 전체 코드 구현 class Node: def __init__(self,data): self.data = data self.left = None self.right = None def __str__(se..

알고리즘 따라가기가 너무 벅차서 다른 스터디원과 자료구조? 기본기에 대해서 따로 공부를 한다. 이번에는 스택과 큐를 라이브러리 없이 직접 구현해보고, 스택, 큐를 이용한 문제풀이를 했당. 1 - 스택 2 - 괄호 3 - 스택 수열 4 - 큐 5 - 요세푸스 문제 6 - 프린터 큐 이번 주 숙제는 이렇게 6문제! 완전 기본문제라서 호다닥 끝낼 수 있을 지 알았는데 생각보다 어려워서 당황했다. 1-3번 세문제 푸는 데 8시에 시작한 거 같은데 지금 벌써 새벽 1시 30분이다. 1 - 스택 python ver import sys input = sys.stdin.readline c_list = [] def push(num) : c_list.append(int(num)) def pop(): if len(c_lis..

요새 넘나 소홀했던 거 ㅇㅈ 그래서 반성하는 마음으로 알고리즘 스터디 한 당일 날 배운 알고리즘을 정리한당,,,흑,,, 앗 스터디장님이 새로 바뀌셨다. 기존 상규님이 갓카오에 합격하는 바람에 녹형님이 새로운 스터디장이 되셨다. 상규님이 하시는 모든 일 다 잘됐으면 좋겠다 ㅎㅣㅎ ' 배낭 알고리즘은 다이나믹프로그래밍 dp 유형 중 하나다. 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 가방의 최대 용량은 10kg 이고 현재 보석은 이렇게 6개가 있다고하자. 그러면 6개 중 10kg를 넘지 않게 잘 골라서 가장 비싼 것들..

크루스칼 알고리즘 (Kruskal algorithm) 스터디장님 설명듣고 동빈나 블로그 보고 크루스칼 알고리즘 복습함 (m.blog.naver.com/ndb796/221230994142) 갓동빈님 1. 간선의 크기만큼 그래프를 생성한다. 2. 각 간선에는 연결된 노드들이 적혀있다. 3. 간선들을 오름차순으로 정리한다. 4. 간선 값이 가장 작은 녀석부터 이어간다. 여기서 유니온파인드를 이용한다. 5. 만약 간선의 두 노드가 이미 연결되어있다면 SKIP 해버린다. → 왜? 오름차순으로 정렬된 상태에서 진행되기때문에 만약 연결되어있었다면 이전의 간선 값이 더 작을 것이기 때문이다. 6. 모든 부모노드가 1이 되면 (꼭 1일 필요없음 그냥 연결만 되면 됨) 끝내버린다. 이걸 코드로 구현을 해보자 백준 1197..

유니온 파인드 (union-find) 동빈나 유튜브로 예습하고 스터디장님 설명 듣고 문제풀려는데?! 기억이 안남 그래서 다시 동빈나 블로그로 예습함. ( m.blog.naver.com/ndb796/221230967614 ) 1. 맨처음 부모노드를 자기 자신으로 초기화한다. 1 2 3 4 1 2 3 4 2. 주어진 두 인덱스에 대해서 부모노드가 다르다면 부모노드를 같게 만들어준다. → unionparents 인덱스번호가 더 작은 쪽으로 부모노드를 바꾸는 게 국룰인거 같습니다. 큰 쪽이어도 상관은 없음 EX) 1,3 번을 합하라 1 2 3 4 1 2 1 4 EX) 2,4 번을 합하라 1 2 3 4 1 2 1 2 EX) 2,3번을 합하라 1 2 3 4 1 1 1 2 원래 2번이랑 4번은 부모노드가 2로 같았는..