본문 바로가기

programming study/Algorithm

 (275)
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (15)(2021.2.8) 본 내용은 해당 강의 토대로 작성 1. 응급실(큐) 나의 전략 1 순위: 위험도, 2 순위: 순서 순서대로 환자를 검사하고 위험도가 그 환자보다 높은지 본다. deque 자료구조 popleft로 뽑아내서 검사 튜플 문제 풀이 from collections import deque n, m = map(int, input().split()); # n: 환자 수 , m번째 환자 a = list(map(int, input().split())); # 위험도 dan = []; # 환자받을 리스트 for x in enumerate(a): # 튜플로 입력 dan.append(x); dan = deque(dan); # deque target = dan[m]; # 목표 환자 cnt = 0; # 카운트 p = 0; # 환자 ..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (14)(2021.2.7) 본 내용은 해당 강의 토대로 작성 1. 공주구하기(큐) 문제 해설 큐 자료구조 선입선출(First In Frist Out) 스택의 반대 먼저 들어간 것이 먼저 빠지게 된다. 파이썬에서는 deque 자료구조 append, pop : 뒤 쪽에서 넣거나 뺀다. appendleft, popleft :앞쪽에서 넣거나 뺀다. 문제의 조건에 따라 popleft, append 하는 경우, popleft만 하는 경우를 구분하자. 문제 풀이 from collections import deque n, k = map(int, input().split()); p = deque([]) # 왕자들을 담을 리스트 for x in range(1, n + 1): # 왕자들 리스트에 넣기 p.append(x); while len(p) !..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (13)(2021.2.4) 본 내용은 해당 강의 토대로 작성 1. 후위표기식 만들기 문제 해설 중위표기식 : 연산 우선 순위에 따라 순차처리를 하지 못함. 컴퓨터가 처리하기 힘들다. 3+5*2/(7-2) 후위표기식 : 컴퓨터가 연산 우선 순위에 따라 순차처리 할 수 있다. 스택 자료구조 352*72-/+ 중위표기식에서 후위표기식으로 변환할 때도 스택 자료구조 사용 숫자는 바로 출력 연산자는 우선순위에따라 스택에 저장 or 출력 여는괄호는 만났을 때 스택에 append 닫는괄호 만났을 때는 여는 괄호 전까지의 연산자들 처리 문제 답안 a = input(); stack = []; res = ''; # 출력할 변수 for x in a: # 문자 탐색 if x.isdecimal(): # 피연산자인 경우 res += x; else: if ..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (12)(2021.2.3) 본 내용은 해당 강의 토대로 작성 1. 가장 큰 수 문제 해설 순서를 유지하되, 가장 큰 수가 되도록 숫자를 제거 어느 숫자가 있을 때, 그 숫자의 앞에 자신보다 작은 숫자가 없어야 한다. 위 규칙으로 리스트화를 하면, 내림차순으로 정렬된다. 스택 자료 구조 사용하기 LIFO(Last In First Out): 후입선출 리스트의 append, pop이 스택과 같은 개념 문제 답안 num, m = map(int, input().split()); num = list(map(int, str(num))); # str로 변환하면 하나하나 접근하여 리스트화 stack = []; # 빈 리스트 만들기 for x in num: while stack and m > 0 and stack[-1] < x: # 스택의 마지막 ..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (11)(2021.2.2) 본 내용은 해당 강의 토대로 작성 1. 씨름 선수(그리디) 문제 해설 키 순으로 정렬하기 제일 위의 사람은 키로 모든 사람을 이기는 것 그 아래의 사람은 자신보다 키가 큰 사람보다 몸무게가 많아야 한다. 위를 반복하여 답을 구할 수 있다. 최댓값을 갱신하며 진행 문제 풀이 n = int(input()); p = []; for i in range(n): # 선수 튜플로 입력 받기 h, w = map(int, input().split()); p.append((h, w)); ans = 0; # 답 for i in range(n): cnt = 0; # 카운트 for j in range(n): if p[i][0] > p[j][0] or p[i][1] > p[j][1]: # 키 또는 몸무게가 클 경우 카운트 cnt..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (10)(2021.1.31) 본 내용은 해당 강의 토대로 작성 1. 마구간 정하기(결정알고리즘) 문제 해설 입력받은 마굿간을 오름차순으로 정렬하기 주어진 조건하에, 가장 가까운 두 말의 최대거리를 이분 검색으로 찾기 첫 번째 말은 무조건 첫 번째 마굿간에 넣기 문제 풀이 def Count(mid): cnt = 1; # 카운트 h = a[0]; # 말을 놓은 곳 for i in range(1, n): if a[i] - h >= mid: cnt += 1; # 말 배치 h = a[i]; return cnt; n, c = map(int, input().split()); a = []; for _ in range(n): x = int(input()); a.append(x); a.sort(); s = 1; e = a[n - 1]; while s..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (9)(2021.1.30) 본 내용은 해당 강의 토대로 작성 1. 이분검색 이분검색 오름차순 정렬된 상황에서 목표로하는 값을 찾을 때 리스트를 반으로 나눈 뒤에 검색목표값보다 중간점이 작은 경우 시작점을 중간점 +1에 두고 다시 검색목표값보다 중간점이 큰 경우 끝점을 중간점 +1에 두고 다시 검색목표값과 중간점이 같을 때까지 위를 반복문제 풀이 n, m = map(int, input().split()); arr = list(map(int, input().split())); s = 0; # 시작점 e = n; # 끝점 arr.sort(); # 오름차순 정렬 while s m : # 중간점보다 목표값이 작은 경우 e = mid - 1; 문제 답안 n, m = map(int, input().split()); a = list(map(in..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (8)(2021.1.28 ~ 29) 본 내용은 해당 강의 토대로 작성 1. 격자판 최대합 문제 해설 2차원 배열 문제 문제 풀이 import sys sys.stdin = open("in5.txt", "rt") n = int(input()); arr = [list(map(int, input().split())) for _ in range(n)]; # 2차원 리스트로 입력 받기 arrSum = 0 ; # 합 maxSum = 0; # 최대합 for i in range(n): # 각 행의 합 최대 구하기 for j in range(n): arrSum += arr[i][j]; if maxSum < arrSum: maxSum = arrSum; arrSum = 0; for i in range(n): # 각 열의 합 최대 구하기 for j in rang..

티스토리툴바