Algorithm

문제 링크 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 접근 방법 1. N이 200,000이기 때문에 순열로 모든 경우를 고려하는 것은 시간 초과 2. 특정 상황에서 가장 큰 컵라면 값을 뽑아내야 하기 때문에 우선순위 큐 사용 3. 입력된 문제를 시간순 오름차순, 컵라면 값 내림차순 정렬해 deque에 넣는다. 4. deque에서 값을 뽑아내면서 현재 시간보다 데드라인이 크거나 같은 문제의 컵라면 값을 우선순위 큐에 넣어줌 5. 만약에 우선순위 큐의 peek 값이 현재 문제의 컵라면 값보다 작다면 우선순위 큐에서 ..

문제 링크 3954번: Brainf**k 인터프리터 각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([ www.acmicpc.net 문제 개요 질문 게시판을 보면 알 수 있지만 문제 설명도 수정되었었고, 테스트 케이스의 빈틈을 노린 코드들이 재채점 되어 글을 작성하는 날 기준으로 solved.ac 랭크 골드 1 임에도 불구하고 맞은 사람 34명, 정답률 9%를 기록하고 있다. 다시 말해서 구글 검색을 통해 위 문제에 대한 코드를 올린 블로그는 거의 다 틀린 코드고, 이 때문에 모든 검색 방법을 총동원해서 거의 50번 가까이 제출을 하면서 통과한 ..

백준 import sys # 재귀 depth를 늘려줌 sys.setrecursionlimit(10 ** 9) # 파일 입출력 r = sys.stdin.readline # int 하나 입력 받기 length = int(r()) # list 입력 받기 list1 = list(map(int, r().split())) # 문자열 입력받기 string1 = r().rstrip() 백준은 입력부터 출력까지 전부 다 작성해줘야 한다. 하지만 표준 라이브러리에 해당하는 모든 것을 사용할 수 있다. 표준 입출력보단 속도가 훨씬 빠른 파일 입출력으로, 재귀 depth도 늘려준 뒤 사용한다. 프로그래머스 # 여기에 사용할 라이브러리를 선언해줌 def solution(answers): answer = [] return ans..

요즘 코딩 테스트 광탈을 Python으로 면하자는 콘셉트의 자료(게시글, 강의, 책)가 많이 보인다. 지난 1년간 코딩 테스트에 Python을 사용하면서 느낀 점과 주의할 점을 공유해보려 한다. 1. 속도 Python 관련해서 가장 많이 언급되는 부분 중 하나가 속도다. 결론부터 말하면 평균적으로 속도가 느리고, 그 속도를 가늠하기 쉽지 않다. 여기서 말하는 가늠하기 쉽지 않다는 것은 개략적인 시간 복잡도를 판단하는 것이 아닌 실제로 채점 사이트에 나오는 속도(ms)를 말한다. Python은 컴파일러(Compiler)가 아닌 인터프리터(Interpreter) 언어이다. 뿐만 아니라 언어 구조상 코딩 테스트에 주로 사용되는 C++/Java에 비해 속도가 느리다. (언어 구조 및 원리에 대해선 추후 포스팅 ..

변수 관련 # 한 줄에 변수를 2개 이상 선언할 수 있다 a, b = 10, 20 # 자료구조도 마찬가지 c, d = [], [] # *args 문법 board = [1, 2, 3, 4, 5] a, *b, c = board # a=1, b=[2,3,4], c=5 # swap a, b = 5, 10 a, b = b, a # a=10, b=5 list 조작 1 # map board = [1, 2, 3, 4, 5] new_board = list(map(lambda x: x * 2, board)) # new_board = [2,4,6,8,10] # filter board = [1, 2, 3, 4, 5] new_board = list(filter(lambda x: x > 2, board)) # new_board ..