분류 전체보기

https://www.acmicpc.net/problem/5639✔ 유형 : 재귀✔ 문제 풀이: 이진 검색 트리의 특징과 전위 순회를 했을 때의 배열의 규칙을 찾아 범위를 줄여나가 탐색하며 오른쪽 서브트리와 왼쪽 서브트리를 구분해서 문제를 푼다.  해당 노드보다 큰 원소가 나올 때까지 탐색한다.큰 원소가 나오면 오른쪽 서브트리를 의미하고 큰 원소의 인덱스부터 오른쪽 서브트리.해당 노드 인덱스 + 1 부터 큰 원소의 인덱스 -1 까지는 왼쪽 서브트리임을 알 수 있다.  이제부터 위의 규칙을 이용해 재귀를 돌린다. 재귀를 계속 돌리면 결국 리프 노드까지 탐색이 완료되고, 같은 방법으로 왼,오 노드를 구분하여후위 순회의 순서대로 print를 해주면 된다.  ⬇️ 코드import sysinput=sys.stdi..

다익스트라다익스트라 알고리즘: 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘* 음수인 가중치를 가진 간선이 있다면 사용할 수 없다. 구현1. 자기 자신과의 거리는 0이므로 ① 번 인덱스의 값은 0으로 둔다.2. ①번 정점에서는 ②, ③ ,④ 번 정점으로만 갈 수 있는데, 최단거리 테이블에 3,2,5를 일단 써놓는다. (확정은 아님!)최단 거리 테이블을 d라고 했을 때, d[2]~d[6] 까지 최솟값을 찾아서 최단거리를 확정한다. 3. ③ 번 정점의 거리를 확정한 후 , 최단거리 테이블을 갱신한다.① 번 정점에서의 간선은 이미 확인 했기 때문에 ③ 번 정점에서 뻗어나가는 간선만 본다.①②③ 4. 가장 가까운 정점을 찾기 위해 d[2],d[4],~d[6] 확인. 5. 확정된 ④에서의 ..

신장 트리1. 모든 정점을 포함한 서브 그래프2. 트리의 성질 : 무방향이면서 사이틀이 없는 그래프3. 주어진 그래프의 정점이 V개일 때, 신장 트리는 V-1개4. 주어진 그래프가 연결 그래프일때만 신장 트리가 존재 최소 신장 트리주어진 방향성이 없는 그래프의 부분 그래프(Subgraph) 들 중에서 모든 정점을 포함하는 트리 부분 그래프 : 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프① 가운데 정점이 연결 되지 않음②,③ 사이클 존재 → 신장 트리가 아님④ 원래 그래프에 없던 간선 증가 → 부분 그래프 X 크루스칼 알고리즘1. 간선을 크기의 오름차순으로 정렬. 제일 낮은 비용의 간선을 선택한다.2. 현재 선택한 간선이 정점 u,v 를 연결하는 간선이라 할 때 만약 u와 v가 같은..

위상 정렬Topological Sort 정의 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬✨ 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다.           DAG(Directed Acyclic Graph) 구현 1. 제일 앞에 오려면 자신보다 앞에 있는 정점이 하나도 없어야 한다.= 자신에게 들어오는 정점이 없어야 한다.( indegree = 0 )  2. A를 위상정렬에 추가한 이후로는 A에서 다른 정점으로 나가는 간선이 의미가 없다.→ A와 A에서 뻗어 나가는 간선을 모두 지운다.  3. 그래프에서 제일 앞에 위치 할 수 있는 정점. → 자신에게 들어오는 간선이 없는 정점 = C, G 4. 정점 C에서 뻗어나가는 간선 삭제. 제일 앞에 위치할 수 있는 ..

드디어!!! 1주차가 끝났다아아~먼가 빨리 지나간 것 같은데, 1주일동안 한 공부양을 보면 빨리 지나간건 또 아닌듯.아침에 시험봐서 그런가 걍 개개ㅐㄱ 오늘 개개개 무기력했음. 집이었다면 게임하다 잤겟지..하지만??여기서는 그럴수가 없다~ 해야지 뭐 어떡해~해시 정의와 성질해시 자료구조 : 키에 대응되는 값을 저장하는 자료구조insert, erase, find, update → O(N) 해시 함수: 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수* 이상적인 상황 → O(1), 충돌이 빈번한 경우 성능 저하, 최악의 상황 → O(N)각 키의 해시 값이 최대한 균등하게 퍼져야 성능이 좋아지기 때문에 좋은 해시 함수를 정해야 함! 충돌서로 다른 키가 같은 해시 값을 가진 경우 충돌이 일어난다. 충..

https://www.acmicpc.net/problem/2630✔ 유형 : 이분 탐색✔ 문제 풀이: 큰 문제를 작은 문제로 분할하여 작은 문제부터 순차적으로 해결한 뒤 결과를 합한다.  탐색할 영역의 제일 왼쪽 위의 색을 저장해두고, 이중 for문으로 다른 색이 포함되어 있는지 확인한다.만약 다른 색이 포함되어있다면 각 면을 N/2로 나눠서 총 4 부분으로 나눈다.계속 나누다가 언젠간 한면이 1이되면 해당 색을 배열에 저장한다. 만약 한 구역을 검사했는데 모두 같은 색이라면 해당 색을 배열에 저장한 후 함수를 리턴한다. 위의 방법을 아래의 코드로 나타내었다. import sysinput=sys.stdin.readline # input함수 바꾸기import copy#inputN = int(input())..

https://www.acmicpc.net/problem/2805✔ 유형 : 이분 탐색✔ 문제 풀이: 리스트 양쪽에 start와 end 피벗을 두고 범위를 좁혀가며 답을 찾는다.   #2850 나무자르기#이분 탐색import sysinput=sys.stdin.readline # input함수 바꾸기N, M = map(int, input().split())trees = list(map(int, input().split(' ')))st, en = 0, max(trees) # 최소 최대값!while st mid: #톱날보다 긴 나무들만. count += tree - mid # 톱날h만큼 자른다 if count >= M: # 구하려는 나무길이보다 크면 더 잘라야하므로 s..

장마철이라 매일 같이 비오다가 오랜만에 정말 맑은 하늘이 떴다. 오랜만에 광합성이라 매우 좋았다. 그거와 별개로 오늘 Week 1 마지막 날이었는데. 정말 많은 일이 있었던 것 같다. 이렇게 집중해서 많은 양의 코딩 테스트를 한적이 거의 없었는데, 짧은 일주일동안 몰입해서 열심히 공부한 것 같다. 비록 모든 과제를 완료하진 못했지만, 80퍼 이상 한 것에 의의를 두고 있다~이분 탐색정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 주의 사항1. 이분 탐색을 하려고 한다면 주어진 배열이 정렬되어 있어야 한다.2. 무한 루프에 빠지지 않게 mid 값을 정해야 한다.

https://www.acmicpc.net/problem/3190 ✔ 유형 : 큐✔ 문제 풀이: 뱀이 지나가는 맵의 좌표를 큐를 이용한다. ✨Key Point1. 뱀의 이동 좌표 2. 회전 3. 게임 종료 조건   (1) 위치가 index 범위 밖일 떄   (2) 스스로 부딪혔을 때 →  map[][] 2차원 배열에 현재 맵상태를 기록해두고 확인한다.ex ) 0 일경우 빈 맵, 1일경우 뱀이 위치해있음. 2일경우 사과가 있음. 코드import sysimport collections input=sys.stdin.readline # input함수 바꾸기dequeu = collections.deque#inputN = int(input()) # 보드의 크기K = int(input()) # 사과의 개수#사과의 위..

https://www.acmicpc.net/problem/2493 ✔ 유형 : 스택✔ 문제 풀이: 반복문으로 검사하면 최악의 경우 O(N^2)의 시간복잡도가 나온다. 이를 해결하기 위해 stack을 이용한다. 구해야 하는 답: 각 탑에서 발사한 레이저 신호를 수신한 탑의 번호 리스트.  코드import sysinput=sys.stdin.readline # input함수 바꾸기# inputN = int(input())towers = list(map(int,input().split())) #list 자료구조지만 스택 사용 가능stack = list()answer = [0 for i in range(N)]# 2. for i in range(N): # 1. 현재 스택에 값이 존재한다면? while(s..

오늘은 일기를 생략하겠다 너무 졸립다..안뇽Quick Sort 퀵 솔트는 매 단계마다 Pivot이라는 이름이 붙은 원소 하나를 차례로 보내는 정렬법이다.  장점1. 추가적인 공간이 필요하지 않다.2. 배열 안에서의 자리 바꿈으로 처리한다. → Cache Hit 비율이 높다! (속도가 빠르다)In Place Sort원소위치를 잘 바꿔주면 되기 떄문에 추가적인 공간이 필요 없다.  정렬 과정 시간 복잡도 평균 : O(N LgN)최악: O(N^2) Quick Sort VS Merge Sort Merge SortQuick Sort시간복잡도O(NlgN)평균 O(NlogN)최악 O(N^2)평균적으로 Merge Sort 보다 빠르다.추가적으로 필요한 공간(overhead)O(N)O(1)Stable Sort 여부OX

오늘 코치님과 면담을 했다. 슬랙에 커피챗 신청 공지가 올라와서 냅다 해버렸다..예전에는 뭔가 내 자신에 대해 확신이 없어서, 이런 자리들을 항상 피해왔던 것 같다. 하지만, 이전 대외활동을 하면서, 현재 상태의 나를 인정하고 나에게 도움을 줄 수 있는 사람에게 나의 상태를 보여주는게 나를 발전시키는 일이라는 것을 뒤늦게 깨달았다. 질문을 어떻게 해야할지 잘 모르겠었는데, 올려주신 파인만 질문법 영상을 보면서 많은 도움이 됐다.미리 질문을 메모장에 써놨지만, 그 영상대로 질문을 잘하진 못한 것 같아서 아쉽다. 면담을 하면서 내 상황에 대해 스스로 말하다 보니, 지금 어떤 것을 중요하게 여겨야 하는지 알 것 같았다. 집에서 공부를 할 때는 기한도 없고, 누가 강제적으로 주는 과제도 없었다. 그냥 흘러가는 ..