2️⃣ Study/⚙ 알고리즘7 [자료구조] 이진탐색 1️⃣ 순차탐색 • 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 • 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용된다. • 자주 사용되는 탐색 알고리즘으로, 리스트에 특정 값의 원소가 있는지 체크할 때에도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소 개수를 세는 count 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. • 가장 앞에있는 원소부터 차례로 확인해야 하기 때문에 시간 복잡도는 O(N) 이다. def sequential_search (n, target, array) : for i in range(n) : # 현재 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target : .. 2024. 4. 4. [자료구조] 정렬 1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고있는지 물어보는 문제 2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 함 3. 더 빠른 정렬이 필요한 문제 : 계수 정렬 등 다른 알고리즘을 이용하거나 구조적인 개선을 거쳐야 풀 수 있는 문제 1️⃣ 정렬 • 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 • 데이터를 정렬하면 이진탐색이 가능해진다. • 선택정렬, 삽입 정렬, 퀵정렬, 계수정렬 • 알고리즘 효율성과 관련되어 있음 ※ 책에서는 모두 오름차순 정렬을 기준으로 설명한다. 내림차순은 오름차순 결과에서 인덱스 Reverse 해서 출력하면 된다. 2️⃣ 선택정렬 • 원시적인 방법으로 매번 가장 작은 것을 선택하는 .. 2024. 2. 25. [자료구조] DFS/BFS 1️⃣ 자료구조 기초 🐾 탐색 Search | 많은 양의 데이터 중 원하는 데이터를 찾는 과정 | 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 주로 다룬다. | 대표적인 탐색 알고리즘 : DFS, BFS | 탐색 알고리즘 원리를 이해하기 위해 스택, 큐, 재귀함수에 대한 이해가 필요하다. 🐾 자료구조 Data Structure | 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. | 스택과 큐는 자료구조의 기초 개념으로 다음의 두 함수와 두가지 고려 사항으로 구성된다. • 삽입 Push : 데이터를 삽입한다. • 삭제 Pop : 데이터를 삭제한다. • 오버플로 : 자료구조가 수용할 수 있는 데이터의 크기를 초과한 상태에서 삽입 연산을 수용할 때 발생 • 언더플로 : 자료구조에 데이터가.. 2022. 9. 2. [자료구조] 구현 🚩 구현 | 머리속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 | 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 🐾 완전 탐색 | 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 🐾 시뮬레이션 | 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형 🐾 구현시 고려해야 할 메모리 제약 사항 | 변수 유형 • 파이썬에서 실수형 변수는 유효 숫자에 따라 연산 결과가 원하는 값이 나올 수 있지 않다는 점을 기억하자 | 리스트 크기 - 메모리 제한 • 일반적인 코딩테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점만 기억하도록 하자 1️⃣ 실전 유형 문제 : 상하좌우 | 일련의 명령에 따라 개체를 차례대로 이동 시킴 → 시뮬레.. 2022. 9. 2. [자료구조] 그리디 🚩 그리디 | 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘 | 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 알고리즘 🐾 그리디 알고리즘 문제는 주로 정렬 알고리즘과 짝을 이루어 출제된다. 🐾 기초 파이썬 연산자 기억하기 / : 나누기 % : 나머지 // : 몫 ** : 거듭제곱 | 그리디 알고리즘이 모든 알고리즘 문제에 적용 가능한 것은 아니다. 그리디 알고리즘은 '최적의 해' 를 찾을 수 없을 가능성이 높지만, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있다면 매우 효과적이고 직관적으로 적용할 수 있는 방법이다. | 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 생각하고, 그의 정당성을 검토해야 답을 도출할 수 있다. 1️⃣ 실전 유형 문제.. 2022. 9. 2. [자료구조] 필수 파이썬 문법 - 조건문, 반복문, 함수, 입출력, 라이브러리 1️⃣ 조건문 | if ~ elif ~ else 문 🐾 논리 연산자 • X and Y : X 와 Y 가 모두 참일때 참 • X or Y : X 와 Y 중 하나만 참이어도 참 • not X : X 가 거짓일 때 참이다. 🐾 기타 연산자 • 리스트, 튜플, 문자열, 사전과 같은 자료형에 값이 존재하는지 확인하는 연산 : in, not in • X in 리스트 : 리스트 안에 X가 들어있을 때 참 • X not in 문자열 : 문자열 안에 X 가 들어가 있지 않을 때 참 • pass : 조건문의 값이 참이라고 해도 아무것도 처리하고 싶지 않을 때 사용 • 조건부 표현식 : if ~ else 문을 한줄에 작성 score = 85 result = "성공" if score>=80 else "실패" print(res.. 2022. 9. 2. [자료구조] 필수 파이썬 문법 - 자료형 * 알고있는 내용은 필기 패스했음 1️⃣ 수 자료형 | 코딩 테스트에서 대부분 정수형을 다루는 문제가 주로 출제된다. 🐾 정수형 : 양의 정수, 음의 정수, 0 🐾 실수형 : 소수점 아래를 포함하는 수 자료형으로 소수부가 0이면 0을 생략해 작성할 수 있다. a = 5. print(a) # 5.0 b = -.7 print(b) # -0.7 🐾 지수표현방식 : e 나 E 를 이용한 지수표현 방식을 이용할 수 있다. EX. 1e9 = 1,000,000,000 a = 1e9 # 10억의 지수표현방식 print(a) # 1000000000 a = 75.25e1 print(a) # 752.5 a = 3954e-3 print(a) # 3.954 🐾 부동 소수점 : 컴퓨터는 2진수 방식으로 수를 처리하기 때문에 실수.. 2022. 9. 1. 이전 1 다음 728x90
