Study Log Study Log

https://www.acmicpc.net/problem/5648 list = [] check = 1 while True: try: element = input() # 입력값 없음(null)이면 중지 if element == None: break else: element_split = element.split() # 첫번째 줄 입력만 n 제외하고 반환 if check: element_split = element_split[1:] check = 0 # 역순배열하고 정수형 반환 for i in element_split: i = int(i[::-1]) list.append(i) except: break print(*sorted(list), sep = '\n') Uploaded by Notion2Tistory ..

https://www.acmicpc.net/problem/2230 import sys input = sys.stdin.readline n, m = map(int, input().rstrip().split()) list = [int(input()) for _ in range(n)] list.sort() start, end = 0, 0 min_value = int(2e9) while start = m: min_value = min(list[end] - list[start], min_value) start += 1 # 차이가 m보다 작다면 else: end += 1 print(..

https://www.acmicpc.net/problem/1758 n = int(input()) money = [int(input()) for _ in range(n)] # 내림차순 정렬 money.sort(reverse = True) # 강호가 받는 팁이 양수일때만 팁 계산 tip = [money[i] - i for i in range(n) if money[i] - i > 0] print(sum(tip)) Uploaded by Notion2Tistory v1.1.0

https://www.acmicpc.net/problem/20920 import sys input = sys.stdin.readline n, m = map(int, input().rstrip().split()) words = {} for i in range(n): word = input().rstrip() # 단어의 길이가 m보다 클 때만 단어장 만들기 if len(word) >= m: # 단어장에 입력받은 단어가 있으면 if word in words: words[word] += 1 # 단어장에 입력받은 단어가 없으면 추가 else: words[word] = 1 # 자주 나오는 단어, 단어의 길이, 사전순으로 정렬 words = sorted(words.items(), key = lambda x : (-x..

Ch6. 정렬 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능하다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 면접의 단골주제이기도 하다. 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제 1. 선택 정렬 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 ‘가장 작은 것을 선택’한다는 의미에서 선택 정렬이라고 한다. 시간복잡도 연산 횟수가 N+(N−1)+⋯+2≈N(N+1)/2 이다. 빅오 표기법으로 간단히 O(N^2)으로 표현 가능하다. 다른 정렬 알고리즘보다 비효율적이다. 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 많으..

Ch5. DFS/BFS 1. 꼭 필요한 자료구조 기초 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념 삽입(push) : 데이터 삽입 삭제(pop) : 데이터 삭제 오버플로 : 데이터가 꽉 찬 상태에서 삽입 연산 수행할 시 나타남 언더플로 : 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 나타남 1.1 스택 박스 쌓기와 유사 선입후출 구조 또는 후입선출 구조 가장 마지막에 들어온 데이터쪽부터 삭제되거나 추가 1.2 큐 대기 줄과 유사 먼저 온 사람이 먼저 들어갈 수 있으므로 ‘공정한’ 자료구조 선입선출 구조 가장 먼저 들어온 데이터쪽부터 삭제되거나 추가 1.3 재귀함수 DFS와 BFS를..

Ch4. 구현 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 변수 파이썬에서는 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원 리스트 크기 💡 코딩 테스트의 메모리 제한을 고려해야 한다. 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다. 채점 환경 알고리즘 문제를 풀 떄는 시간 제한과 데이터의 개수를 먼저 확인한 뒤 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 지 예측할 수 있어야 한다. 대부분의 코딩 테스트 환경 시간 제한 : 1초 메모리 제한 : 128MB 일반적으로 시간 복잡도 O($NlogN$) 이내의 알고리즘 이용해서 문제풀기 구현 문제에 ..

Ch3. 당장 좋은 것만 선택하는 그리디 단순하지만 강력한 문제 해결 방법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법 보통 코딩 테스트에서 출제되는 그리디 알고리즘의 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘의 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됨. 그리디 알고리즘으로 문제의 해법을 찾았을 때에는 그 해법이 정당한지 검토해야 한다. 실제 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아니면,..