코팩

https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 문제 풀이 우선순위 큐를 활용해서 가치가 가장 높은 선물부터 아이들에게 나눠줄 수 있게 코드를 짰습니다. 코드 # 14235번 크리스마스 선물 from heapq import heappush, heappop n = int(input()) values = [] for _ in range(n): a = list(map(int, input().split())) if a[0] == 0: # 아이를 만났고 ..

https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 문제 풀이 다솜보다 높은 득표 수를 가진 후보자들이 없어질 때 까지 표를 뺏는 코드를 작성해주었다. 후보자들 중 가장 높은 득표 수를 가진 후보자의 표를 우선으로 매수했습니다. 코드 # 1417번 국회의원 선거 import sys from heapq import heappop, heappush, heapify n = int(input()) dasom_vote = int(input()) ..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 주어진 문자열의 문자로 변환할 수 있는지 확인하는 문제이다. 문자마다 경유하는 루트가 다르기에 cost변수를 따로 추가해서 경유한 단어의 개수를 기록해주었다. BFS 알고리즘을 이용하기에 가장 먼저 target에 도달하는 루트가 최단 루트이다. from collections import deque def solution(begin, target, words): answer = 0 queue ..

https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 백준의 문제와 마찬가지로 단순하게 종점에 도달할 수 있는지와 소요되는 시간을 측정해주는 문제이기에 문제없이 풀어주면된다. from collections import deque def solution(maps): answer = 0 dxys = ((1,0),(0,1),(-1,0),(0,-1)) queue = deque([[0,0]]) n = len(maps) m = len(maps[0]) vis..

문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 문제를 풀기 위해서 다음과 같은 점화식이 필요하다. 주어진 화폐 단위 별로 해당하는 금액을 완성할 수 있는 동전을 구성하는 개수를 찾아준다. 1. dp[0]을 1로 초기화합니다. 이는 금액 0을 만드는 방법이 하나밖에 없음을 의미합니다(아무 동전도 사용하지 않는 경우). 2. 모든 동전 단위 coin[i]에 대해 반복합니다. 3. 각 coin[i]에 대해 금액 coin[..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 주어진 지문을 그대로 구현하려고 노력했다. 다만 지문에 큰 오류가 있다. 지문의 "현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우"은 이미 청소를 한 구역이어도 지나갈 수 있다. 청소를 한 곳을 다시 방문하지 않게 코딩을 하다가 테스트 케이스를 통과하지 못해서 너무나도 고생했다.... 실제로 아래 짠 코드도 중복되는 코드도 많..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 이중 for문을 사용하면 시간초과가 발생할 수 있다. 파이썬은 1초당 2000만 번의 연산이 가능하다. 그렇기에 n은 최대 500,000이 입력 값으로 주어질 수 있다. 500,000,000,000 -> 5천억 번의 횟수는 주어진 시간제한인 1.5초에 위배된다. 그렇기에 스택을 사용해서 시간 복잡도를 줄여야 한다. 아래의 코드의 시간 복잡도는 O(n)이기에 50만 번의 연산이 이루어진다. ..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 BFS알고리즘을 적용해서 주어진 S초가 지난 뒤에 갱신된 grid에서 목표 값을 출력해준다. 코드 # 18405번 경쟁적 전염 import sys from collections import deque n, k = map(int, sys.stdin.readline().split()) grid = [] queue = [] for i in range(n): li = ..