Study Log Study Log

Ch5. DFS/BFS 1. 꼭 필요한 자료구조 기초 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념 삽입(push) : 데이터 삽입 삭제(pop) : 데이터 삭제 오버플로 : 데이터가 꽉 찬 상태에서 삽입 연산 수행할 시 나타남 언더플로 : 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 나타남 1.1 스택 박스 쌓기와 유사 선입후출 구조 또는 후입선출 구조 가장 마지막에 들어온 데이터쪽부터 삭제되거나 추가 1.2 큐 대기 줄과 유사 먼저 온 사람이 먼저 들어갈 수 있으므로 ‘공정한’ 자료구조 선입선출 구조 가장 먼저 들어온 데이터쪽부터 삭제되거나 추가 1.3 재귀함수 DFS와 BFS를..

Ch4. 구현 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 변수 파이썬에서는 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원 리스트 크기 💡 코딩 테스트의 메모리 제한을 고려해야 한다. 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다. 채점 환경 알고리즘 문제를 풀 떄는 시간 제한과 데이터의 개수를 먼저 확인한 뒤 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 지 예측할 수 있어야 한다. 대부분의 코딩 테스트 환경 시간 제한 : 1초 메모리 제한 : 128MB 일반적으로 시간 복잡도 O($NlogN$) 이내의 알고리즘 이용해서 문제풀기 구현 문제에 ..

Ch3. 당장 좋은 것만 선택하는 그리디 단순하지만 강력한 문제 해결 방법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법 보통 코딩 테스트에서 출제되는 그리디 알고리즘의 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘의 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됨. 그리디 알고리즘으로 문제의 해법을 찾았을 때에는 그 해법이 정당한지 검토해야 한다. 실제 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아니면,..

💡학교 동아리에서 주최하는 알고리즘 챌린지에 참여하다가 몰랐던 부분에 대해 작성한 글입니다.백준 2164번2164번: 카드2N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.https://www.acmicpc.net/problem/2164 시간 초과가 발생했던 코드n = int(input()) card = [] for i in range(1, n + 1): card.append(i) def card2(a):..