📍 그리디 알고리즘 단계 별로 가장 좋은 것을 선택하는 알고리즘. 정렬하여 차례차례 선택해 나가면 된다. 1. 현재 상태에서 가장 좋은 것을 선택 2. 문제 조건을 만족하는지 검사 3. 원래 문제가 해결되었는지 검사, 해결되지 않았다면 다시 1번으로 돌아가 반복한다. 📌 더보기 # problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8 5 1 4 2 3 3 5 4 6 5 7 # solve: 1. 종료시간이 가장 빠른 회의 순서..
분류 전체보기
📍 맨하탄 거리 계산법 | x1 - x2 | + | y1 - y2 | ✔️ code def solution(numbers, hand): answer = '' keyboard= { 1:(0, 0), 2:(0, 1), 3:(0, 2), 4:(1, 0), 5: (1, 1), 6:(1, 2), 7:(2, 0), 8:(2, 1), 9:(2, 2), '*':(3, 0), 0:(3, 1), '#':(3, 2) } lh='*' #왼손 rh='#' #오른손 for i in numbers: if i in [1, 4, 7]: lh=i answer+='L' elif i in [3, 6, 9]: rh=i answer+='R' else: #맨하탄 거리 계산법 사용(블럭 기준) Ldistance=abs(keyboard[lh][0]..
📌 더보기 # problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8 5 3 1 2 8 4 9 ✔️ code import sys sys.stdin=open("input.txt", "r") #말이 들어갈 수 있는 마구간 수를 세는 함수 def Count(len): cnt=1 #이미 한마리는 들어가 있다. a=Room[0] for i in range(1, N): if Room[i]-a>=len: cnt+=1 a=Room[i] re..
📍 이분 탐색 사용 📌 더보기 # problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8 9 3 1 2 3 4 5 6 7 8 9 # solve 9개의 비디오를 3개의 DVD에 나누어야 한다. 답의 범위를 먼저 설정해야 한다. input에 따라 답은 1~모든 동영상 길이 합 사이에 있다. 1~45 사이에서 DVD를 3개 이상 만들 수 있는 DVD 1개 길이의 최소 용량을 구해야 한다. 예를 들어 DVD 최소 용량이 23분이라면 ..
✔️ code def solution(s): answer = s #숫자와 영단어 매칭 number_dict={'zero':0, 'one':1, 'two':2, 'three':3, 'four':4, 'five':5, 'six':6, 'seven':7, 'eight':8, 'nine':9} for key, value in number_dict.items(): if answer.find(key)!=-1: #만약 key 를 answer에서 발견한다면, (반환값이 정상) answer=answer.replace(key, str(value)) return int(answer) >>> 지금 보니 0~9 를 설정할 때 string 형으로 해주는게 편할 수도 있을 것 같다. 바로 replace()를 사용해도 되는데 fin..
✔️ code import re def solution(new_id): answer = list() #1단계: 소문자 치환 new_id=new_id.lower() #2단계: 특정 문제 제외 모든 문자 제거 symbols=['-', '_', '.'] new_string=re.sub(r"[^a-zA-Z0-9]","",new_id) #new_id에서 문자와 숫자만 남기기 for i in new_id: if i not in symbols: if i not in new_string: new_id=new_id.replace(i, "") #3단계: 마침표 2번 연속 하나로 치환 for i in range(len(new_id)): if new_id[i]==".": if i+1!=len(new_id) and new_id..
📍 이분검색 검색 범위를 반으로 줄여가며 찾는 방법 자료를 반으로 나누어 반만 탐색하는 것으로 특정 범위 내에 답이 있다는 것이 특징이다 ex) 1~1000 에 해당하는 자료가 있을 때, ① 1~500 / 501~1000 으로 나누고 원하는 output이 1~500 범위 내에 있다면 ② 1~500 을 1~250 / 251~500으로 나누고 원하는 output이 251~500 범위 내에 있다면 … 이를 반복하는 탐색이다. 이때 시작 위치와 종료 위치가 변화하기 때문에 코드를 짤 때 주의해야 한다. 📌 더보기 # problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%..
📌 1부터 9까지의 자연수로 채워진 7*7 격자판이 주어지면 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성하세요. 회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 말합니다. 2 4 1 5 3 2 6 3 5 1 8 7 1 7 8 3 2 7 1 3 8 6 1 2 3 2 1 1 1 3 1 3 5 3 2 1 1 2 5 6 5 2 1 2 2 2 2 1 5 ✔️ code import sys sys.stdin=open("input.txt", "r") arr=[list(map(int, input().split())) for _ in range(7)] #7x7 matrix cnt=0 #행->열 탐색 #첫 원소부터 다음 5번째까지..
📌 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색 깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오면 스도쿠를 정확하게 푼 경우이다. 완성된 9×9 크기의 수도쿠가 주어지면 정확하게 풀었으면 “YES", 잘 못 풀었으면 ”NO"를 출 력하는 프로그램을 작성하세요. 1 4 3 6 2 8 5 7 9 5 7 2 1 3 9 4 6 8 9 8 6 7 5 4 2 3 1 3 9 1 5 4 2 7 8 6 4 6 8 9 1 7 3 5 2 7 2 5 8 6 3 9 1 4 2 3 7 4 8 1 6 9 5 6 1 9 2 7 5 8 4 3 8 5 4 3 9 6 1 2 7 ✔️ code import sy..
✔️ code def solution(id_list, report, k): #유저 ID 딕셔너리화 id_dict=dict.fromkeys(id_list, 0) answer=dict.fromkeys(id_list, 0) #신고 중복 제거 report_set=set(report) report=list(report_set) for i in report: #신고당한 유저 i=i.split()[1] #유저ID에 해당하는 key값과 비교하여 신고당한 횟수를 누적 if i in id_dict: id_dict[i]+=1 #만약 value가 k이상이라면 정지 대상 for j in report: if id_dict[j.split()[1]] >= k: #정지 유저를 신고한 유저의 값 증가 answer[j.split()[0]..