![]()
[문제] https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net [풀이] if kinds in closet.keys(): closet[kinds].append(costume) else: closet[kinds] = [] closet[kinds].append(costume) 의상 종류가 closet 딕셔너리에 있다면 의상을 종류에 맞게 value 리스트에 추가해..
![]()
[문제] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [풀이] 이 문제는 동적 프로그래밍으로 풀어야 하는 문제이다. 동적 프로그래밍의 개발절차는 문제의 사례에 대해 해답을 주는 재귀 관계식 정립 작은 사례를 먼저 해결하는 상향식 방법으로 문제의 사례 해결 개발절차에 따르면 재귀 관계식을 정립해야 하기 때문에 우선 숫자 사이에서 규칙을 찾아보기로 했다. 5까지 직접 계산해 규칙을 찾아보니 이전 3개의 결과를 더한 숫자가 해당 숫자의 답이 되는 것을 발견했다. 이를 이용해 검증하기 위해 문제 예제에서 나온 7을 위의 규칙으로 계산해보니 44가..
![]()
[문제] https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net [풀이] 수를 최솟값으로 만들기 위해서는 마이너스가 나왔을 때 가장 큰 수를 빼면 된다. 따라서 최초의 - 연산자가 나오기 전까지는 전부 더하고, - 엱산자가 나온 이후에는 전부 빼준다. '55 - 50 + 40 - 10 + 20' 을 입력으로 받았을 때 split() 함수를 통해 expression = sys.stdin.readline().strip().split('-') prin..
![]()
[문제] https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net [풀이] main 함수 graph = [[] for _ in range(n+1)] # print(graph) -> [[], [], [], [], [], []] 양방향 노드로 그래프를 만들어준다. 여기서 범위가 n+1인 이유는 노드의 번호가 0이 아닌 1부터 시작하기 때문이다. for i in range(m): a, b = map(int, s..
![]()
[문제] www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net [풀이] 처음에는 부분성공 코드로 제출한 후 아무리 생각해도 답을 모르겠어서 다른 사람 풀이를 찾아봤다. 성공한 코드는 문자열을 만들어서 비교하지 않고 s 내부에서 패턴을 찾아 비교하는 풀이이다. 풀이 중 이해가 안돼서 고민하던 부분을 주석에 숫자로 남겨놓았는데 1. cnt -= 1 : 일치할 경우 첫 번째 'IOI' 패턴 이후부터 검..
![]()
[문제] https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net [풀이] 2021.08.11 - [BOJ] - [Python] BOJ/백준 2630번 색종이 만들기 [Python] BOJ/백준 2630번 색종이 만들기 [문제] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. ..
![]()
[문제] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net [풀이] 분할 정복법 : 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer) 우선 트리의 자식 노드가 4개씩 분할하는 방법을 쿼드 트리라고 한다. 작게 분할한 색종이 안에서 같은 색인지를 판단해 같지 않다면 다시 나누는 과정을 반복한다. 첫 번째 나오는 색을 color에 저장한 후 색종이를 돌면서 전체 색이 전부 ..
![]()
[문제] https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net [풀이] 2개의 리스트의 중복되는 이름을 구하는 문제이다. 이는 교집합을 구하면 쉽게 풀릴 것 같아서 set 자료형으로 풀었다. 듣보잡 명단인 result는 sorted( list( 듣도 못한 사람 & 보도 못한 사람 ) )로 구한 후 result의 길이를 출력, result를 차례대로 출력한다. sys.stdin.readline()[:-1] sys.stdin.readline().str..
![]()
[문제] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [풀이] 2021.08.09 - [BOJ] - [Python] BOJ/백준 2805번 나무 자르기 [Python] BOJ/백준 2805번 나무 자르기 [문제] https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,00..
