🏄♀️ 코딩테스트/🐍 Python
[ 이코테 강의 ] 다이나믹 프로그래밍
다이나믹 프로그래빙 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운 / 보텀업) 으로 구성된다 (하향식 / 상향식) 동적 계획법이라고도 부름 자료구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용됨 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 중복되는 부분 문제(Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다 피보나치 수열..
[ 백준 2309 ] ( python ) 일곱 난쟁이
📚 일곱 난쟁이 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 출력 일곱 난쟁이의 키를 오름차순으로 출력한다. 일..
[ 이코테 강의 ] 이진 탐색
이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log(작은2)N에 비례한다. 시간 복잡도는 O(logN)을 보장 소스코드 (재귀적 구현) def binary_search(array, target, start, end): if start > end: return None mid = (start + end )// 2 if array[mid] ==target: return mid elif array[mid] >..
[ 이코테 강의 ] 정렬 알고리즘
정렬 알고리즘 정렬(sorting) : 데이터를 특정 기준에 따라 순서대로 나열하는 것 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸는 것을 반복 처리되지 않은 데이터 중 가장 작은 0 을 선택해 가장 앞의 5와 바꾸고.. 이를 반복 탐색 범위는 한번 확인할 때마다 줄어들게됨. 매번 선형탐색을 하는것과 같음 => 이중탐색을 활용할 수 있다 선택 정렬의 시간 복잡도 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다 N + (N-1) + (N-2)+ ... + 2 빅오 표기법으로는O(N^2) 삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 선택 정렬에 비해 구현하기는 힘들지만 효율적이다. 삽입 정렬 소스코드 for i in ragn..
[ 이코테 강의 ] 그리디 & 구현 / DFS & BFS
👓 그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 바로 떠올릴 수 있는 능력을 요구한다 정당성 분석이 중요 단순히 가장 좋아 보이는 것만 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 문제 단순히 매 상황에서 가장 큰 값만 고를 때 최적의 답을 고를 수 없을 때가 있다. 일반적인 알고리즘에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다 하지만 코테에서는 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다 == 탐욕법으로 풀릴수 있게 출제함 O(NlogN)의 시간복잡도를 가지는 방법 while True: target = (n // k) * k ..
[ Python ] 코딩 테스트에 꼭 필요한 파이썬 문법
🙇♀️🙇♀️🙇♀️🙇♀️🙇♀️ (이코테 2021 강의 몰아보기) 1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기 감사합니다...감사합니다..!!! 가뭄의 단비같은 강의를 보고 메모한 내용 온라인 코테 - 타인과 문제풀이를 공유하지 않는 선에서 인터넷 검색 허용 오프라인 코테 - 시험장에 방문하여 치르는 시험 - 인터넷 검색 안됨. 팁 1 알고리즘 코드나 노트를 만들면 좋다 팀 노트같은것을 만드는걸 추천(대회나갈때) 👓 출제경향 2~5시간 가량의 시간 - 그리디 - 구현 - DFS / BFS ✨ 알고리즘 성능평가 복잡도(complexity) 알고리즘의 성능을 나타내는 척도 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대해서 알..
[ 백준 1920] ( python ) 수 찾기
📚 수 찾기 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 예제 입력 1 5 4 1 5 2 3 5 1 3 7 9 5 예제 출력 1 1 1 0 0 1 ✍ 접근 가능한 숫자가 너무 커서 이분..
[ 백준 1373] ( python ) 2진수 8진수
📚 2진수 8진수 문제 2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오. 입력 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 주어진 수를 8진수로 변환하여 출력한다. 예제 입력 1 11001100 예제 출력 1 314 ✍ 접근 2진수 -> 8진수 변환 방법을 잘 몰랐기 때문에 먼저 그 방법을 알고 풀려고 했다 그런데 생각처럼 2진수 -> 8진수로 직접 신수 변환을 계산해야 하는 일은 없었다 파이썬의 내장 함수들을 적절하게 활용하자 정답 코드 print(oct(int(input(),2))[2:]) 10진수 👉 2, 8, 16진수 2진수 : print(bin(10)) => 0b1010 8진수 : print(oct(10)) => 0o12 1..