구현이란? 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 과정이다. 별도의 유형으로 다룬다기 보다, 대부분의 문제 유형에서 아이디어를 얻고, 이를 코드로 구현하는 모든 과정을 이른다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 주로 "구현" 문제로 일컫는다. EX) 알고리즘은 간단한데 코드가 너무 길어지는 문제, 특정 소수점 자리까지 출력해야하는 문제, 파싱해야하는 문제 등등 완전 탐색: 모든 경우의 수를 주저없이 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 유의해야할 점 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려할 것: list를 여러개 선언하고, 크기가 큰 list가 있을 경우 메모리 에러가 발..
코딩테스트
숫자 카드 게임 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 - n*m 형식의 array - 뽑고자 하는 카드가 포함되어 있는 행 선택-> 선택된 행에서 가장 숫자 낮은 카드 선택 -> 처음 카드 고를 행 선택할 때, 숫자 낮은 카드 뽑을거 고려해서 -> 가장 큰 숫자를 최종적으로 뽑도록 해야함! Greedy 알고리즘 접근법 문제 해결을 위한 아이디어를 떠올리고 이를 구현해보자 ! 가장 큰 수, 가장 작은 수 등의 말이 나온다면 greedy라고 생각하고 구현 아이디어를 떠올려보자 나의 풀이 n,m = map(int, input().split()) #n*m 만큼의 데이터 입력 받기 -> 각 행별 list로 저장 temp =[] for i in range(n): li = li..
큰수의 법칙 예제 법칙 1. 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 m번 더하여 가장 큰 수를 만드는 법칙 2. 단, 배열의 특정한 인덱스에 해당하는 수가 연속하여 k번을 초과하여 더해질 수 없음 3. n=배열의 크기 ; m = 숫자가 더해지는 횟수 ; k:한번에 더할 수 있는 수 WHY Greedy? "가장 큰" 수를 만드는 알고리즘=> 전형적인 그리디 알고리즘이라고 할 수 있다! 아이디어 생각해보기 1. 큰수데로 정렬 수 첫번째, 두번째큰 수만 뽑아두기 -> 그외의 숫자는 필요없어 2. 젤 큰거 k번 더하고 두번째 큰거 1번 더하는 수열 반복 (젤 큰수가 두개 있으면 그냥 그거 싹 더하면됨) 나의 풀이 n,m,k = map(int, input().split()) arr= list(map(..
Greedy 알고리즘 개념 단어 그대로 "탐욕법"으로 번역하여 소개되곤 함 탐욕적이라는 말의 의미: 현재 상황에서 지금 당장 좋은 것만 고르는 방법 다른 유형에 비해 개념과 코드를 암기해야하는 유형은 아님 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력(문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력) 요구 유형 파악 Tip: 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지 확인 EX) 가장 큰 순서대로, 가장 작은 순서대로 정렬 문제와 짝을 이뤄 출제되는 경우 많음 Greedy 알고리즘 예제: 거스름돈 Q. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다..
알고리즘 코딩 테스트 유형 그리디 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 구현: 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 DFS/BFS: 그래프를 탐색하기 위한 대표적인 알고리즘 정렬: 연속된 데이터를 기준에 따라서 정렬 이진 탐색: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하기 다이나믹 프로그래밍: 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 최단 경로: 특정 지점까지 가장 빠르게 도달하는 방법 찾기 그래프 이론: 기타 그래프 관련 이론들 활용한 문제 무작위로 프로그래머스와 백준에 있는 문제를 풀어왔는데, 개념 정리가 필요할 것 같아 책을 보며 정리를 시작한다. 개념 정리 + 관련 문제 풀이 형식으로 포스팅해야겠다. [reference] 도서 "이것..
코테 문제를 풀다보면 "복잡도"라는 개념을 만나게 된다. 알고리즘 문제를 풀때는 보통 시간 복잡도를 의미한다. 프로그래머스를 통해 문제를 풀다보면 몇개의 테스트 케이스에서 시간 제한을 넘겨 통과하지 못한 적이 종종 있었다. 그래서 우선 시간 복잡도에 대한 개념을 정리해보고자 한다. 복잡도의 종류 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘 trade-off 관계 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 알고리즘을 위해 필요한 메모리의 양 표현 방식 빅오 표기법 명칭 $O(1)$ 상수 시간 $O(logN)..
