왕구아니다

"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚🔎 그리디 알고리즘현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘[수행 과정]1) 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택2) 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사3) 해 검사 : 현재까지 선택한 해 집합이 문제를 해결할 수 있는지 검사 → 전체 문제를 해결하지 못한다면 1)로 돌아가 다시 수행# 백준 11047번 : 동전 개수의 최솟값 구하기# 가장 기본적인 그리디 문제N,K = map(int,input().split())A = [0] * N# 데이터 삽입for i in range(N..

"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚❗️탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘입니다. 주어진 데이터의 성질(정렬 or 비정렬)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요합니다. 탐색 알고리즘과 함께 탐색 영역에서 그래프를 자주 이용합니다. 1️⃣ 깊이 우선 탐색(DFS)그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘[특징]1) 재귀 함수로 구현 (스택 오버플로우 유의)2) 스택 자료구조 이용3) 응용하여 풀 수 있는 문제 : 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등[시간 복잡도(V:노드 ..

"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚1️⃣ 버블 정렬데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식- 시간 복잡도 : O(n^2)[수행 과정]1) 비교 연산이 필요한 루프 범위 설정2) 인접한 데이터 값 비교3) swap 조건에 부합하면 swap 연산 수행4) 루프 범위가 끝날 때까지 2)~3) 반복 - 안쪽 for 문 전체를 돌 때(1~n-i까지) swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬됐다는 의미 - If Question : 안쪽 for 문이 몇 번 수행됐는지 구하는 문제? - 이를 다르게 생각하면, 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는..

"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚1️⃣ 배열과 리스트배열- 메모리의 연속 공간에 채워져 있는 형태의 자료구조- 인덱스를 사용하여 값으로 바로 접근 - 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음리스트- 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야함- 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도 빠름- 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절‼️ 파이썬파이썬의 리스트(lis..

"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚1️⃣ 시간 초과 원인 찾기‼️ 대량의 입출력 데이터를 다룰 때는 input()과 print() 대신 sys.stdin.readline()과 sys.stdout.write() 사용하기- input() 함수는 입력을 받을 때마다 내부적으로 버퍼(Buffer)를 비우고, 사용자가 입력한 값을 가공(엔터 제거 등)하는 과정을 거칩니다. 반면 sys.stdin.readline()은 버퍼에 쌓인 데이터를 한 번에 읽어오기 때문에 오버헤드가 훨씬 적습니다.- print() 와 달리 sys.stdout.write()는 자동으로 줄을 바꿔주지 않으며, 오직 문자열만 인자로 받습니다.# 일반적인 입출력 방식a = ..

안녕하시렵니까! 드디어 미루고 미루던 코테 준비를...해볼까 합니다...!!!앞으로 차근차근 정리하는 개념들은 'Do it! 알고리즘 코딩 테스트 파이썬' 교재를 기반으로 작성할 예정입니다.후! 시작이 반이다...❓시간 복잡도 정의알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 시간 복잡도를 정의하는 유형에는 3가지가 있습니다.1. 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법2. 빅-세타 : 보통일 때의 연산 횟수를 나타낸 표기법3. 빅-오(O(n)) : 최악일 때의 연산 횟수를 나타낸 표기법 코딩 테스트에서는 빅-오(O(n))를 기준으로 수행시간을 계산하는 것이 좋습니다. 그 이유는 코테는 다양한 테스트 케이스를 통과해야만 합격하기 때문에 시간 복잡도를 최악일 때..