Algorithm

[백준] 11000. 강의실 배정

[백준] 11000. 강의실 배정 - 파이썬 https://www.acmicpc.net/problem/11000 풀이 Greedy를 생각하며.. 힙을 이용해 품. 강의를 모두 순회하며 강의의 종료시간을 최소 힙에 집어넣는데, 최소 힙의 root(제일 빠른 종료시간) > 처리할 강의의 시작시간 이면 그대로 최소 힙에 처리할 강의의 종료시간을 넣고(강의실을 +1) 아니라면, 그 강의실에서 계속 강의해도 되니까 최소 힙에서 pop하고 다시 새로운 종료시간을 넣음. import heapq import sys read = sys.stdin.readline N = int(read().strip("\n")) lec = [list(map(int, read().strip("\n").split())) for _ in ra..

[프로그래머스] 42862. 체육복

접근 가장 주의할 점은, 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다. 이 조건. 도난당했으나 여벌 체육복이 있는 학생(lost, reserve 배열에 모두 포함되는 학생)은 미리 빼 줄 필요가 있음. 그 이후는 lost를 순회하며 reserve에 +1 or -1 학생이 존재하는 지(앞뒤에 여벌 체육복을 가진 학생이 존재하는 지)만 확인. 확인할 때, 오름차순으로 순회할 거면 index가 -1인 학생(앞에 있는 학생)부터 체육복이 있는 지 조사하고, 내림차순으로 순회할 때는 반대로 index가 +1인 학생(뒤에 있는 학생)부터 조사해야 함. def solution..

[프로그래머스] 43164. 여행경로

풀이 1 deq에 넣어가며 하나씩 빼면서.. from collections import deque def solution(tickets): ticketDeq = deque(tickets) deq = deque(["ICN"]) answer = ["ICN"] while ticketDeq: start = deq.popleft() for s, f in ticketDeq: if s == start: deq.append(f) mini = min(deq) deq.clear() ticketDeq.remove([start, mini]) deq.append(mini) answer.append(mini) return answer 풀이 틀림. 풀이 2 조심해야 할 점이 있었습니다. 중복된(같은 이름의) 티켓이 여러 장 들어갈..

[프로그래머스] 42898. 등굣길

풀이 1 보자마자 생각나는 것.. 확통에서 풀던 최단거리 경우의 수 문제 (같은 것이 있는 순열) 그 방식대로 풀이해보자 from math import factorial def solution(m, n, puddles): def shortcut(m, n): return int(factorial(m+n) / (factorial(m) * factorial(n))) answer = shortcut(m-1, n-1) for li in puddles: answer -= shortcut(m - li[0], n - li[1]) * shortcut(li[0]-1, li[1]-1) return answer 이러면 문제가.. puddles의 개수가 2개를 넘어가면 두 웅덩이를 모두 지나는 경우의 수를 여러 번 빼 주게 되..

[프로그래머스] 43163. 단어 변환

Programmers - 43163. 단어 변환 접근 BFS로 구현. 한 스텝마다, deq에 있는 단어들에서 변경할 수 있는 단어 목록을 뽑아와 저장. 그리고 그 목록을 다시 다음 스텝에 deq에서 하나씩 뽑아와서 반복. from collections import deque def solution(begin, target, words): def canChange(fromWord, toWord): difChar = 0 for i in range(len(fromWord)): if fromWord[i] == toWord[i]: continue else: difChar += 1 if difChar == 1: return True else: return False if target not in words: ret..

[프로그래머스] 43105. 정수 삼각형

Programmers - 43105. 정수 삼각형 접근1 Bottom-Up 방식 사용. 삼각형의 높이만큼 반복 돌리면서 리스트에 저장해나가며 밑으로 한 층씩 내려가면 될 듯? 맨 위를 1층이라고 하면 [[{1층-0번}], [{2층-0번}, {2층-1번}], [{3층-0번}, {3층-1번}, {3층-2번}]] {n층-n번} 에는 그 지점까지 도달할 수 있는 모든 경우의 수를 집합(set)으로저장. [[{7}], [{10}, {15}], [{18}, {16, 11}, {15}], [{20}, {25, 18, 23}, {19, 20, 15}, {19}]] 와 같은 느낌으로. def solution(triangle): dp = [[set([triangle[0][0]])]] for F in range(1, len..

[프로그래머스] 42895. N으로 표현

Programmers - 42895. N으로 표현 접근 일단, N을 1번 사용했을 때 ~ 8번 사용했을 때를 모두 순회하며 확인하면 될 것 같음. 일단 N = 3으로 예시를 들어서 한번 생각해 보자. N을 1번 사용했을 때 {3} N을 2번 사용했을 때 {33}, {3+3, 3-3, 3/3, 3*3} => {33, 6, 0, 1, 9} N을 3번 사용했을 때 여기부터 이제 사칙연산에 어떤 수를 사용하느냐에 따라 갈리는데 3, 3, 3을 사용 3+3과 3을 사용 3-3과 3을 사용 3/3과 3을 사용 3*3과 3을 사용 33, 3을 사용 33*3, 33-3, 33+3, 33/3, 3*33, 3-33, 3+33, 3/33 결국 N을 3번 사용할 때의 결과값은 N을 1번 사용했을 때 (+, -, *, /) N..

[프로그래머스] 42587. 프린터

프로그래머스 - 42587. 프린터 접근 그냥 데크에 넣고 priority가 최댓값인 놈을 만날때까지 돌리고 돌리다가 만나면 pop하고 횟수세고 끝. from collections import deque def solution(priorities, location): # target location 표시 prior = [[i, 0] for i in priorities] prior[location][1] = 1 deq = deque(prior) answer = 0 while True: if deq[0][0] == max(deq, key=lambda x: x[0])[0]: if deq[0][1] == 1: return answer + 1 else: deq.popleft() answer += 1 else: d..