문제풀이

[문제] https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [풀이] 이 문제는.. 지문에 나와있는 `최소 일수`, `인접한 여섯 방향의 토마토가 익음` 키워드로 bfs 문제임을 알 수 있다. 최소 일수를 구하는 문제는 bfs를 이용한다. 이전에 풀었던 7576 토마토 문제 + 2차원 의 문제이다. 해당 문제가 어렵고 7576번을 아직 풀지 않았다면 .. 7576번부터 먼저 풀면 도움이 될 것 같다. 2022.06.22 - ..

[문제] https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net [풀이] 가장 간단한 방법인 max, min 으로 찾는 방법은 시간초과가 나온다 (당연함) 파이썬의 우선순위 큐 문제는 heapq, PriorityQueue 두 가지 라이브러리를 사용할 수 있다. https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-pytho..

[문제] https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net [풀이] 이 문제는 지문에 나와있는 `최소 일수`, `인접한 네 방향의 토마토가 익음` 키워드를 통해 bfs문제임을 알 수 있다. 최소 일수를 구하는 문제는 bfs를 이용한다. 나름의? 주의해야할 점은 첫 번째 날에 토마토 박스에 1이 여러 위치에 있을 경우 동시다발적으로 각 위치 주위의 토마토가 익어야하기 때문에 main에서 bfs 함수를 부를 때 상자에 저장된 토마토들..

[문제] https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net [풀이] 간단한 dfs 문제였는데 exit(0)을 생각을 못해서 좀 걸렸다 우선 이렇게 풀어놓았지만 exit 을 이용하지 않고 제대로 푸는 방법을 생각해봐야겠다 -> 수정 완료 [코드] import sys n = int(sys.stdin.readline()) square = [] for _ in range(n): square.append(list(map(int, sys.stdin.readli..

[문제] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [풀이] 이 문제는 피보나치 값이 아닌, 특정 값의 피보나치를 구하기 위해 호출되는 fibonaaci(0)과 fibonacci(1)의 호출 횟수를 구하는 것이다. 피보나치 문제는 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용하는 동적 계획법 으로 풀었다. fibonacci(n)을 구하기 위해서는 fibonacci(n-1)와 fibonacci(n-2)을 더해야 하기 때문에 fibonacci(n)을 호출할 경우 실행되는 fibonacci(0)과 fibonacci(1)은 '..

[문제] https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net [풀이] 입력되는 내용을 딕셔너리 타입의 book에 key : value 값을 각각 {번호 : 이름}, {이름 : 번호} 로 저장한 뒤 key 값을 이용해 value 를 찾아 출력한다. [코드] import sys if __name__ == '__main__': input = sys.stdin.readline n, m = map(int, input().spli..

[문제] https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr [풀이] 각 의상별 가짓수 계산 부위별 옷에서 아무것도 안입는 경우가 있을 수 있어 각 가짓수에 1을 더해 곱한다. 하루에 최소 한 개의 옷은 입기 때문에 모두 안입은 경우인 1을 뺀다. [코드] def solution(clothes): closet = {} for cloth in clothes: if cloth[1] in closet: closet[cloth[1]] += 1 else: closet[cloth[1]] = 1 answer = 1 for i in closet.values(): answer *= (i + 1) return ans..

[문제] https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr [풀이] 문제에서 필요한 과정을 나누면 총 3가지로 나눌 수 있다. rows x columns 크기 행렬 선언 후 1부터 rows x columns 까지의 숫자 대입 행렬 테두리 회전하기 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자를 순서대로 배열에 담기 1. rows x columns 크기 행렬 선언 후 1부터 rows x c..

[문제] https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr [풀이] 문제가 너무 길어서 처음엔 어려운 문제인줄 알았다. 읽어보니까 순서는 전혀 상관없고 민우가 구매한 로또 번호와 당첨 번호가 일치하는 개수 민우가 구매한 로또 번호 중 0의 개수 이렇게 두 가지를 구하면 첫 번째는 최저 순위, 첫 번째와 두 번째를 더한 경우는 최고 순위가 된다. 민우가 구매한 로또 ..