손가든 개발일지

오늘은 쪽지 시험이 있는 날이다. 쪽지 시험에 관한 주요한 내용들과 오늘 공부한 내용을 정리하겠다. 강한 결합 요소 ( 강연결성분 : Strongly Connected Component ) 강한 결합 요소란? 그래프의 특정 부분 집합 내의 모든 정점 V 이 집합 내 다른 정점 U로 도달할 수 있으며 반대로 U도 V로 도달할 수 있는 집합 또한 기본적으로 싸이클이 발생하는 경우 무조건 SCC에 해당한다는 특징이 있음. 쪽지 시험 대비 팀원 코어 타임 서로 2주차 내 어떤 키워드가 중요할 지 생각해보고 서로 문제를 출제했다. 화이트보드에 문제를 풀어보며 토론했는데, 다익스트라에 대해 조금 이해가 부족하다고 생각되서 다시 자세히 정리해보자. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 다이나믹 ..

위상정렬이 정말 쉽지가 않은 알고리즘인 것은 확실하다.. 진입 / 진출 차수를 checking하면서 -1하며 queue 혹은 우선순위 큐인 힙에 저장하는 방식을 주로 활용하는 것 같다. 그보다 더 어려운 것은 위상정렬은 문제를 보고 위상정렬 문제인지 파악하기도 쉽지 않고, 파악하더라도 똑같은 방식이 아닌 유동적인 문제 풀이가 필요하므로 매우 고수준의 이해를 요한다. 어려운 문제를 리뷰하며 조금 더 확실하게 이해해 보자 BaekJun - # 1432 : 그래프 수정 (위상정렬) 방향 그래프의 연결성분을 행렬로 나타낸 행렬 그래프를 제시 한 뒤 더 높은 수의 정점이 더 높은 위상을 가지도록 변경하고 그 변경점을 출력하도록 하는 문제였다. 장장 5시간을 고민하며 코드를 구현해 나갔지만, 내 머리로는 도저히 멍..

오늘은 DFS를 마치고 위상정렬에 대해 공부하기 시작했다. 위상 정렬 위상 정렬이란? 방향이 있는 그래프에서 방향을 거스르지 않고 모든 정점을 잇는 경로를 선형순서로 나열하는 것 이때 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다. 이때 든 생각은, 알고리즘 문제에서 일단 사이클이 있는지를 판단하고 사이클이 있다면 위상 정렬을 하도록 하는 문제가 있을 거라 생각했다. 사이클이 있는지 판단하는 함수는 Kruskal에서의 노드의 부모를 고정하여 판단하는 방식이 사용될 것 같다. [정방향] 위상 정렬의 동작 예시(경로를 나열하기 위한 진행 순서)는 다음과 같다. 1. 진입차수가 0인 모든 노드를 큐에 삽입한다. 2. 큐에서 POP을 하고 POP한 노드에서 나가는 간선을 제거한다. 3. 제거한 후 진입차..

오늘은 BFS 문제 풀이를 팀원과 서로 공유하고 DFS 문제 풀이를 시작했다. BaekJun - # 21606 : 아침산책 (DFS) 완전히 하나로 연결된 N개의 노드의 서로 다른 경로의 수를 세는 문제인데, 노드가 실내거나 실외이다. 경로는 반드시 실내에서 시작해서 서로 다른 실내로 끝나며 1 -> 3 과 3 -> 1은 다른 경로로 보는 것이다. 이 문제의 특이한 점은 서브 테스크로 문제 배점을 나눈다는 점이었다. 주목할 점은 N의 최대 제한이 10의 5승이라는 점. (대충 NlogN 보다 높은 시간 복잡도를 가진다면 앙 시간초과 띠~ 라는 뜻) 나는 2번과 5번 테스크에서 시간 초과가 발생했다. 시간 초과가 발생한 로직은 다음과 같다. 코드를 보기 전 말로 설명한다면, 1. 실내인 노드를 하나씩 DF..

오늘 팀원들과 아침에 그래프에 대해 발표했다. 상우형은 개괄적인 이론과 종류, 용어들을 설명했고, 의훈님은 성능과 관련하여 접근했다. 나는 그래프를 이해하기 위해 트리에 대해 설명했는데 서로 그래프에 대해 분석하고 잘못된 설명이 있으면 바로 잡으면서 개념을 조금 더 단단히 잡을 수 있게 됬다. 이런식으로 매일 발표를 진행할 텐데 앞으로도 좀 더 적극적으로 발표 내용을 만들어 가야겠다고 생각했다. 오늘은 BFS를 공부하겠다. BaekJun - #2178 : 미로 탐색 (BFS) 미로의 최단 거리가 몇인지 확인하는 문제였다. DFS로 많은 사람들이 푼 것 같은데 BFS가 가장 좋은 방법이라고 난 생각한다. 실제로 정글 커리큘럼 내 BFS 문제로 분류 되었기도 한다. 미로의 시작으로부터 방문을 시작하여 동서남..

새로운 2주차를 맞이하고 조원이 변경됐다. 2주차는 조원들과 매일 1개의 키워드를 정해 공부한 뒤 익일 오전에 발표하는 형식으로 공부하기로 정했다. 그래프 자료 구조 그래프 알고리즘은 코딩 테스트에서 주로 사용되는 풀이 방식의 알고리즘으로, 매우 중요한 만큼 어렵기도 하다. 팀 코어타임 발표를 위해서라도 열심히 준비해보자 구현 방법 그래프 G = (V,E)를 표현하는 두가지의 표준 방법이 있다. 1. 인접 리스트의 집합 2. 인접 행렬 먼저 인접 리스트(Adjacency List)의 집합으로 그래프를 표현하는 방식 이 방식은 낮은 밀도의 그래프에 선호된다. 메모리 양이 세타(V+E) 여서 데이터 사용량측에서 매우 바람직한 특성을 가진다. 인접 행렬(Adjacency Matrix) : 2차원의 배열을 사용..

2주차가 시작 되기 전 아침. 밤에 자면서 아무리 생각해도 방법이 떠오르지 않던 문제를 풀었다. Baekjun - #2504 괄호의 값 (스택 : 상) 처음엔 재귀함수를 써야하나 했다. 괄호의 특성 상 안의 연산들을 전부 기억 한 후 곱연산을 수행해야 했기 때문에 재귀방식이 먼저 떠올랐지만 어떻게 재귀로 풀어내야 할지 도무지 답이 안나왔다. 이 문제는 괄호에 숫자는 없지만 괄호의 종류 별로 값을 부여해 제일 서로 옆끼리 붙어있는 애들은 더하고, 속해있는 애들은 겉에 애가 곱해주는 문제를 수행해야 했다. 각 케이스 별로 따로 처리하려고 했으나 그 방법으론 처리되지 않는 케이스가 너무 많아서 구글링을 하니까 '분배법칙'을 사용하라는 얘기를 듣고 방법을 자세히 들여다 봤다. 2 x ( 2+ 3x(3)) = (..

내일이면 2주차가 시작되서 오늘 안에 알고리즘 문제를 전부 다 풀어내야 한다. BaekJun - #1629 solving (분할 정복 : 중) a를 b만큼 거듭제곱 한 뒤 c로 나눈 나머지를 출력하는 문제이다. b가 10^8값을 넘기 때문에 for문으로 b만큼 곱하여 풀지 말라는 의도이다. 아래 코드로 해결했다. from collections import deque import sys import heapq a,b,c = map(int,sys.stdin.readline().strip().split()) def div_mup(a,b): if b == 1: return a%c elif b%2 == 1: return div_mup(a, b//2)**2*a%c else: return div_mup(a, b//2..

오늘은 쪽지 시험도 보는 날인데 무슨 알고리즘에 관해 나왔는지도 추가해놓았다. 우선순위 큐(Priority Queue) 우선 순위 별로 dequeue()하는 큐이다. 삽입 후 우선순위 탐색 방식을 사용하면 inqueue()할 때는 O(1)이지만 dequeue()는 우선순위 알고리즘으로 탐색하기에 시간복잡도가 O(N)이 된다. 우선순위 정렬 삽입 후 queue() 방식을 사용하면 inqueue()할 때 O(NlogN)의 시간이 걸리고 dequeue()때는 O(1)이 된다. 이진트리 우선순위 큐 방식을 사용하면 inqueue()할 때는 트리의 높이만큼 교환이 발생하므로 O(logN)의 시간복잡도를 가지고, dequeue()는 트리의 꼭대기를 추출하고 트리의 높이만큼 교환이 발생되므로 O(logN)이다. 따라..

월요일이 돌아왔다. 다시 열심히 공부하자. 정렬 알고리즘 모든 정렬은 일단 파이썬의 리스트 배열에 들어있는 정수들을 오름차순, 혹은 내림차순으로 정렬하는 알고리즘으로 공부했다. 그리고 모든 정렬법의 개념 아이디어는 말로 풀어 적을 것이고 오름차순으로 가정한다. ps. 실제로 정렬 복잡도가 낮아 개선할 필요가 없을 경우 그냥 a = sorted(a)를 사용하면 된다. 버블 정렬 버블 정렬법의 개념은 오른쪽 혹은 왼쪽 끝에서 시작해서 반대쪽끝까지 편도로 순회하며 2개의 요소를 비교, 더 큰 값을 오른쪽으로 옮기는 방법 반대쪽 끝까지 순회를 마치면 제일 왼쪽에 있는 요소는 제일 작은 요소가 되므로 fix - > 다음 정렬시 해당 값을 제외한다. 이런방식으로 체크하는 정렬은 각 편도 순회시 fix되는 요소가 하..