그리디, 백트래킹 문제https://www.acmicpc.net/problem/1339접근 방식 그리디 알파벳이 각각의 자릿수에 몇번 등장하는지를 자릿수 별로 10의 거듭제곱 승의 가중치를 부여하여 알파벳 dictionary에 기록-> 가중치 값이 가장 큰 알파벳 순서대로 9 ~ x 까지의 숫자를 부여한 후 결과값 출력백트래킹9 ~ x (각기 다른 알파벳의 갯수만큼)의 수를 순열로 배치 -> 합했을 때에 가장 큰 결과값이 나올 때의 값을 기록짚고 넘어갈 Point✏️ 백트래킹 전에는 시간 복잡도 계산을 하자 !순열 주어진 n개의 원소 중에서 r개를 선택하여 배열하는 경우의 수조합 순서를 고려하지 않고 주어진 n개의 원소 중에서 r개를 선택하는 경우의 수 ✏️ Dictionary에서 key값이 아닌 key..

스위핑, 우선순위큐, 그리디 문제https://www.acmicpc.net/problem/11000💡 풀이코드 (성공 - 스위핑)import sys import heapq n = int(sys.stdin.readline())lecture = []for _ in range(n): a, b = map(int, sys.stdin.readline().split()) heapq.heappush(lecture, (a, 1)) # start heapq.heappush(lecture, (b, 0)) # end cnt = 0ans = 0while lecture: a, b = heapq.heappop(lecture) if b == 1: cnt += 1 else: ..

그리디 문제https://www.acmicpc.net/problem/2212문제 설명고속도로 위에 최대 K개의 집중국을 세워 N개의 센서에 도달해야 한다.이때, N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 한다.각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.접근 방식그리디우리는 최대 K개의 집중국을 세워 모든 N개의 센서에 도달하는 것이 목표이다.즉, 최대 K개의 집중국을 세워 n(n1,n1,..)-k(k1,k2,..)의 최솟값의 합을 구하는 것이 목표이다.여기서 N개의 센서와 K개의 집중국이 의미하는 바가 무엇인지 알아보자.N개의 센서 : 우리가 도달해야 하는 센서의 개수로, 각 센서는 원점으로부터의 정수 거리의 위치에 놓여 있다.K개의 집중국 : 세울 수 있는 집중국의 개수로,..

그리디 문제https://www.acmicpc.net/problem/13164초기 접근 방식1. 이진탐색이 문제를 처음에 그리디로 접근하고자 하였으나, 생각보다 잘 풀리지 않아 그 다음 방식으로 이진 탐색을 떠올렸다. 백준에 있는 공유기 설치 문제와 유사하다고 생각하여 이 문제 또한 이진탐색으로 접근하여 문제를 풀어보았다.https://www.acmicpc.net/problem/2110 2. 잘못된 이유이진 탐색에서 mid의 의미가 명확하지 않다. 공유기 설치 문제 : mid = 공유기 사이의 최대 간격 -> 이를 바로 답에 활용할 수 있었음.행복 유치원 문제 : mid = 조를 S개 만큼 나누면서, 각 조의 첫번째 원생 사이의 간격이 최소가 되도록 하는 수 -> 문제에서 요구하는 바와 일치하지 않음.이..

그리디 알고리즘 문제 ex) input 12 2 HPHPHPHHPPHP output 6 (1) 처음 내 코드 (실패) a,b=map(int,input().split()) ham = list(input()) # H P cnt=0 for i in range(len(ham)): if ham[i]=="P": change=False for j in range(i-b,i,1): if j=a: continue else: if ham[j]=="H": ham[j]="O" change=True cnt+=1 break if change==False: for j in range(i+b,i,-1): if j=a: continue else: if ham[j]=="H": ham[j]="O" change=True cnt+=1 bre..

그리디 알고리즘 문제 (1) 처음 내 코드 (성공) n=int(input()) price=[] cost=0 for _ in range(n): a=int(input()) price.append(a) price.sort(reverse=True) if len(price)