Coding Test/이것이 코딩 테스트다 with 파이썬9 [이코테] chapter08 다이나믹 프로그래밍 오랜만에 백준 하나 풀려고 했더니 다이나믹 프로그래밍 문제이길래..! 돌아왔답니당 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 다이나믹 프로그래밍 : 효큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘. (1) 다이나믹 프로그래밍 문제? 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션(Memoization): 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 그대로 가져오는 기법. 시간 복잡도: O(N) (2) 다이나믹 프로그래밍 풀이 방식 ▶️ Top-Down 방식 : 큰 문제를 해결하기 위해 작은 문제를 .. 2024. 2. 5. [이코테] chapter07 이진 탐색 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 이진 탐색 : 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 (1) 순차 탐색 순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 시간 복잡도는 O(N)이다. (2) 이진 탐색: 반으로 쪼개면서 탐색하기 이진 탐색은 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터를 찾는 방법이다. 그래서 내부의 데이터가 이미 정렬디되어 있어야만 사용할수 있는 알고리즘이다. 시간 복잡도는 O(logN)이다. 이진 탐색을 구현하는 방법에는 재귀함수를 사용하는 방법과 반복문을 사용하는 방법이 있다. 1️⃣ 재귀함수로 구현 def binary_sear.. 2023. 9. 6. [이코테] chapter06 정렬 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 정렬 : 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘 (1) 배경 지식 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 정렬은 다음 챕터에서 배울 이진 탐색의 전처리 과정이니 잘 알고 넘어가는 것이 중요하다. 정렬에는 종류가 매우 다양한데 이 장에서는 선택, 삽입, 퀵, 계수 정렬에 대해서만 다루겠다. 아래는 모두 무작위의 데이터를 오름차순으로 정렬하는 예제를 다룬다. (2) 선택 정렬(Selection Sort) : 가장 작은 것을 선택해, 정렬되지 않은 부분의 맨 앞에 두는 알고리즘 1️⃣예제 (1) 7 5 9 0 3 1 6 2 4 8 (2) 0 5 9 7 3 1 6 2 4 8 (3) 0 1.. 2023. 8. 17. [이코테] chapter05 DFS/BFS 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. DFS/BFS : 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 앞서 배운 chapter03 그리디, chapter04 구현 알고리즘과 달리 이번 챕터는 이론 공부가 중요하다. (1) 배경 지식 ● 탐색(search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 ● 자료 구조(data structure): 데이터를 표현하고 관리하고 처리하기 위한 구조 탐색 알고리즘에서 자주 사용하는 자료구조인 스택과 큐에 대해 알아보도록 하겠다. 두 자료구조는 모두 삽입(push), 삭제(pop) 두 핵심 함수로 구성된다. ● 스택(stack): #박스_쌓기 #First_In_Last_Out 파이썬에서는 스택을 이용할 떄에는.. 2023. 7. 24. [이코테] chapter12 구현 문제 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 구현 알고리즘 : 머릿속에 잇는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 ✨구현 알고리즘은 피지컬 싸움이다! (1) 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법 (2) 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 - 고려해야하는 메모리 제약 사항 - 파이썬은 자료형의 표현 범위 제한은 고려 안해도 됨! 리스트는 보통 128MB ~ 512MB 데이터의 개수(리스트 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4KB 10,000,000 약 40MB 12-1.py 럭키 스트레이트 - ⭐1/3 (⭕) N = input() n = len(N) // 2 rig.. 2023. 7. 24. [이코테] chapter04 구현 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 구현 알고리즘 : 머릿속에 잇는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 ✨구현 알고리즘은 피지컬 싸움이다! (1) 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법 (2) 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 - 고려해야하는 메모리 제약 사항 - 파이썬은 자료형의 표현 범위 제한은 고려 안해도 됨! 리스트는 보통 128MB ~ 512MB 데이터의 개수(리스트 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4KB 10,000,000 약 40MB 4-1.py 상하좌우 - ⭐1/3 (⭕) 파이썬에는 switch-case문이 없다..!! 교재 풀이에서는 .. 2023. 7. 18. [이코테] chapter11 그리디 문제 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 그리디(greedy) 알고리즘 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디는 최적의 해를 보장할 수 없을 때가 많음 but, 코딩 테스트에서의 대부분의 그리디문제는 탐욕법으로 얻은 해가 최적의 해! 정당성 분석 필수! 11-1.py 모험가 길드 - ⭐1/3 (❌) 기준도 못잡고, 정당성 분석도 못해서 20분동안 고민하다가 포기한 문제! ㅠㅠ [교재 풀이] 근데 풀이를 보니까 넘 단순했다.. 오름차순으로 공포도 정렬 후 앞에서부터 공포도를 하나씩 확인하며 ''현재 그룹에 포함된 모험가의 수" >= "현재 확인하고 있는 공포도" 위의 조건을 만족하면 그룹 설정! 문제를 풀다가 'int' object i.. 2023. 7. 10. [이코테] chapter03 그리디 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 그리디(greedy) 알고리즘 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디는 최적의 해를 보장할 수 없을 때가 많음 but, 코딩 테스트에서의 대부분의 그리디문제는 탐욕법으로 얻은 해가 최적의 해! 정당성 분석 필수! 3-1.py 동전 문제 - ⭐1/3 (❌) N = int(input()) cnt = 0 coinType = [500, 100, 50, 10] for i in coinType: cnt += N // i N %= i print(cnt) 정당성: 큰 수의 화폐가 모두 작은 수의 화폐의 배수임. 동전을 타입별로 리스트에 넣어 사용 3-2.py 큰 수의 법칙 - ⭐1/3 (⭕15m 30s) N.. 2023. 7. 10. [이코테] 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 책 소개 이것이 코딩 테스트다 with 파이썬 나동빈 한빛미디어 Part 02 주요 알고리즘 이론과 실전 문제 ch03 그리디 ch04 구현 ch05 DFS/BFS ch06 정렬 ch07 이진 탐색 ch08 다이나믹 프로그래밍 ch09 최단 경로 ch10 그래프 이론 Part 03 알고리즘 유형별 기출 문제 ch11 그리디 문제 ch12 구현 문제 ch13 DFS/BFS 문제 ch14 정렬 문제 ch15 이진 탐색 문제 ch16 다이나믹 프로그래밍 문제 ch17 최단 경로 문제 ch18 그래프 이론 문제 ch19 2020년 상반기 삼성전자 기출 문제 2023. 7. 10. 이전 1 다음
