본문 바로가기

CS/Algorithm

 (52)
패스트캠퍼스 챌린지 35일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 백준 10282번 문제 : 해킹 문제 해석 1. 시간 제한은 2초, Python3 기준 약 4,000만번 연산이 가능하다. 2. 입력되는 데이터의 최대 개수는 컴퓨터(vertex) 10,000개, 의존성(edge) 100,000개 그리고 해킹 당한 컴퓨터 100,000개가 주어진다. 3. 컴퓨터와 의존성에 따라 감염될 컴퓨터의 수 그리고 그에 걸리는 시간을 구한다. 문제 풀이 1. 기본적인 다익스트라 최단 경로 알고리즘 문제이다. 2. 우선순위 큐를 사용하여 시간 복잡도 O(NlogD)로 해결할 수 있다. 복기 1. 정점과 간선 그리고 가중치 형태의 그래프를 그릴 수 있을 경우, 다익스트라 알..
패스트캠퍼스 챌린지 34일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 백준 2606번 문제 : 바이러스 문제 해석 2. 데이터의 크기는 정점 = 100, 간선 = 100개이다. O(N^3)의 시간 복잡도 내에 풀이 가능하다. 문제 풀이 1. 전형적인 그래프 문제로 DFS, BFS 알고리즘을 통해 네트워크 연결 상태를 확인한다. 2. 인접 정점 리스트와 방문 리스트를 생성한다. 3. 재귀 또는 반복문을 통해 연결되어 있는 모든 정점을 방문한다. 복기 1. BFS와 DFS를 구현하였다. 모두 반복문을 활용하였고 BFS는 큐 자료구조를, DFS 스택 자료구조를 이용했다. 2. 성능은 DFS가 높게 나왔는데 코드 길이에서는 큰 차이가 없다. deque와 list에서 성..
패스트캠퍼스 챌린지 33일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 백준 1260번 문제 문제 해석 1. 시간 제한은 2초, Python3 기준 약 4,000만번 연산 가능하다. 2. 입력될 데이터는 N = 1,000, M = 10,000개로 O(N + M)의 시간 복잡도 내에 문제를 풀이해야한다 3. DFS와 BFS를 각각 수행한 결과를 출력한다. 문제 풀이 1. 기본적인 형태의 그래프를 DFS, BFS로 탐색한다. 2. 정점 번호가 작은 것부터 먼저 방문한다. 3. 큐 구현을 위해 collections 라이브러리의 deque를 사용한다. 복기 1. DFS와 BFS는 인접 정점 리스트와 방문 여부 리스트를 생성해주어 이를 확인 및 갱신하며 정점을 이동 및 출..
패스트캠퍼스 챌린지 32일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 백준 9251번 문제 문제 해석 1. 시간 제한은 1초이고, Python3 기준 약 2천만번 연산 가능하다. 2. 주어진 데이터로 1,000개의 글자를 두번 입력받으므로 O(W1*W2) 내에 문제를 풀 수 있다. 3. 부분 수열이 되는 것 중 가장 긴 것을 찾는다. 문제 풀이 1. 가장 긴 공통 부분 수열(LCS) 문제는 전형적인 동적 프로그래밍 문제이다. 2. 두 문자열의 길이를 조금씩 늘려가며 확인한다. LCS 알고리즘은 부분 문자열의 길이를 늘려가면서 길이 값을 갱신하는 알고리즘이다. 만약 같은 문자가 나왔을 경우엔 그 이전 문자열 길이에 1을 더해준다. 예를 들어, ABC, GBC일 경..
패스트캠퍼스 챌린지 31일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 백준 1904번 문제 문제 해석 1. 시간 제한은 0.75초로 Python3로 약 1,500만번 연산 가능함을 알 수 있다. 2. 입력 데이터는 N = 1,000,000로, O(N)으로 문제를 풀어야한다. 3. N의 가짓수에는 N-1의 가짓수가 포함되어 있으므로 DP를 통해 상향식으로 접근한다. 4. 그렇지 않으면 모든 연산을 다 해야하기 때문에 시간 초과가 발생한다. 문제 풀이 1. 동적 프로그램 문제를 풀기 위해서는 점화식을 세워야한다. 2. D[i] = 수열의 길이가 i일 때 경우의수라면 D[3] = 3, D[4] = 5이다. 3. 따라서, 점화식은 D[n]은 D[n-1] + D[n-2]..
패스트캠퍼스 챌린지 30일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 1. 백준 1927번 문제 최소 힙을 구현하는 문제이다. 시간 제한은 1초이고 입력 데이터는 N = 100,000, X = 약 2,000,000,000이다. 시간 제한에 따라 구현하기 위해서는 O(N log X)이며 이는 3,100,000번 내 연산으로 해결 가능하다. 이를 위해 다음과 같이 힙 정렬을 구현해보았다. 힙 정렬을 구현할 수 있긴 하지만 삭제할 때마다 모든 원소를 확인해서 최악의 경우 시간 복잡도는 O(N) 시간이 소요될 수 있다. 어떤 방법을 쓰더라도 시간 초과가 나와서 이건 무슨 경우지? 하고 있다가 위와 같은 내용을 확인하게 되었다.(참고) 일반적으로 O(log N)의 효율을..
패스트캠퍼스 챌린지 29일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 이진트리 오늘은 고급 탐색 알고리즘으로 이진 트리와 관련된 문제를 풀었다. 어느 순간부터 문제가 풀리지 않아 최근에 계속 강의에 의존하고 있다. 문제를 풀어보긴 하지만 막히는 부분이 많아 일단 강의를 듣고 문제를 다시한번 복기하고 있는 중이다. 그럼에도 알고리즘을 복습할 수 있어 좋았고 특히, 문제 풀이에 이렇게 적용될 수 있구나라는 걸 배워서 정말 좋았다. 백준 1991번 문제 이 문제는 이진 트리를 구현하고 구현된 이진트리를 바탕으로 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder) 알고리즘을 적용시켜 값을 출력하면 되는 문제다. 함수형 프로그래밍은 ..
패스트캠퍼스 챌린지 28일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 기본 탐색 알고리즘 오늘은 기본 탐색 알고리즘에서 핵심 유형 문제 풀이를 진행했다. 백준 2110번 문제와 1939번 문제였는데 난이도가 꽤 높았다. 코드를 작성하다가 도저히 풀리지가 않아 일단 인강으로 마무리했다🤔 그래도 피와 살이 되는 것이니 복기를 해보자! 문제 풀이 핵심 내용 1. 집의 개수는 N개로 최대 200,000개의 데이터가 있다. 2. 집의 좌표는 X개로 최대 1,000,000,000개의 데이터가 있다. 3. 제한 시간은 2초, 파이썬 연산은 약 4,000만번으로 O(N log X)의 시간 복잡도 내에 풀이가 가능하다. 이를 계산하면 200,000 * 30으로 최악의 경우 60..

티스토리툴바