Algorithm
[이코테] Chapter3-2 / 큰 수의 법칙(그리디 알고리즘)
[이코테] Chapter3-2 / 큰 수의 법칙(그리디 알고리즘)
2021.12.16난이도 - 하 풀이 제한 시간 - 30분 시간 제한 - 1초 메모리 제한 - 128MB 기출 - 국가 교육기관 코딩테스트 '큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 민교는 본인만의 방식으로 다르게 사용하고 있다. 민교의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 떄 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5..
[이코테] Chapter3-1 / 당장 좋은 것만 선택하는 그리디
[이코테] Chapter3-1 / 당장 좋은 것만 선택하는 그리디
2021.12.16그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 이 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 "탐욕법"으로 소개된다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기에서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘은 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교 했을 때, '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유..
시간초과를 대비하는 빠른 입력 받기 방법 sys.stdin.readline(), strip()
시간초과를 대비하는 빠른 입력 받기 방법 sys.stdin.readline(), strip()
2021.11.27input()대신 sys.stdin.readline()을 사용하는 이유는? 단순히 몇줄 입력받는 문제들과는다르게, 반복문으로 여러줄을 연속적으로 입력받아야 하는(정렬, 이진 탐색, 최단 경로 문제)의 경우 input()으로 데이터를 입력받으면 시간초과로 오답판정을 받는 일이 발생할 수 있다. 따라서 입력을 최대한 빠르게 받는 방법을 알아야 한다. sys라이브러리에 정의되어 있는 sys.stdin.readline() 함수를 이용한다. 그 대표적인 예시가 백준 BOJ 15552번 문제이다. import sys #sys 라이브러리를 import n = int(input())# case개수를 입력 받기 for i in range(n):# case개수만큼 반복문 실행 a, b = map(int, sys.stdin..
알고리즘 인터뷰 공부하며 Python Class 상속에 대해 추가로 정리한 것
알고리즘 인터뷰 공부하며 Python Class 상속에 대해 추가로 정리한 것
2021.11.24[알고리즘 공부하며 python class 추가로 정리한 것] class JSS: def __init__(self): self.name = input("이름을 입력 : ") self.age = input("나이를 입력 : ") def show(self): print("나의 이름은 {}, 나이는 {}세 입니다.".format(self.name,self.age)) __init__(self)는 JSS클래스가 만들어지면 바로 실행된다. 이렇게 이름과 나이를 입력하라고 바로 실행된다. 이름과 나이를 입력하고, a.name을 실행하면 입력한 이름이 저장되어 있는 것을 확인할 수 있다. 그리고 클래스는 기존의 클래스를 상속받아서 업데이트 시킬 수 있는데, 그 예시는 아래와 같다. class JSS2(JSS): pas..
[이코테] APPENDIX - A / 코딩 테스트 주요 라이브러리 문법과 유의점(내장함수, itertools, heapq, bisect, collections, math)
[이코테] APPENDIX - A / 코딩 테스트 주요 라이브러리 문법과 유의점(내장함수, itertools, heapq, bisect, collections, math)
2021.11.19파이썬에서 지원하는 표준 라이브러리는 굉장히 다양하지만, 코딩 테스트를 준비하며 반드시 알아야 하는 라이브러리는 6가지 정도이다. (이 6가지 라이브러리의 가장 중요하고 알아두어야 할 핵심 내용만 요약하여 설명하고자 함) 내장함수 : print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함한 기본 내장 라이브러리 itertools : 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리 (순열과 조합 라이브러리) heapq : 힙(Heap) 기능을 제공하는 라이브러리,. 우선순위 큐 기능을 구현하기 위해 사용 bisect : 이진 탐색(Binary Search) 기능을 제공하는 라이브러리 collections : 덱(deque), 카운터(Cou..
[이코테] Chapter2-1~2 / 코딩 테스트 기출문제 유형 분석
[이코테] Chapter2-1~2 / 코딩 테스트 기출문제 유형 분석
2021.10.281. 최신 출제 경향과 준비 방향 코딩 테스트는 '기업/기관에서 직원이나 연수생을 선발할 목적으로 시행하는 일종의 문제풀이 시험'이다. 일반적으로 대기업의 공채와 같이 지원자가 많은 상황에서 효과적으로 지원자를 선별하기 위해 상당수 기업에서는 코딩 테스트를 채용 과정으로 채택하고 있다. IT 직군에서 코딩 테스트를 보는 대표적인 기업으로는 삼성전자, 카카오, 라인플러스코퍼레이션(라인)이 있다. 예를 든 기업은 모두 코딩 테스트를 시행하며, 응시생들에게 2~5시간 동안 여러 개의 알고리즘 문제들을 풀도록 한다는 공통점이 있다. 정확한 알고리즘을 사용하여 얼마나 빠르게 많은 문제를 풀었는지를 토대로 순위를 매기고 있다. 이렇게 정해진 시간 내에 문제를 푸는 방식은 코딩 테스트뿐만이 아니라 다수의 시험에서 차..