![]()
[문제] 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..
![]()
[문제] https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [풀이] 같은 코드여도 pypy3로 하면 맞는데 python3로 하면 다 시간 초과 오류 떴다.. 처음에는 brute force로 푸는 줄 알고 우왕 쉽다 하면서 풀었는데 시간 초과가 떠서 이건 이렇게 간단하게 풀 문제가 아니라는 걸 직감했다. -> 이분 탐색으로 풀어야 한다 가장 짧은 나무의 길이를 1을 start로, trees 중 가장 큰 값을 ..
![]()
[문제] https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net [풀이] 산술평균, 중앙값, 범위 구하는 법은 쉬워서 패스.. 최빈값 구하는 게 아주 조금 까다로웠다. 처음에 입력 받을 때 sorted함수를 통해 차례대로 정렬한 상태로 리스트에 저장한다. num_cnt 딕셔너리를 생성한 후 try-except문을 활용해 num_cnt에 숫자 당 빈도수를 저장했다. for문으로 num에 있는 숫자를 차례대로 꺼내 num_cnt[i] += 1을 하게 되면 num_cnt..
![]()
[문제] https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net [풀이] 문자열을 sentence 변수에 저장한다. sentence에 있는 문자 하나씩 검사한다 문자가 '(' 이거나 '[' 인 경우 (열린 문자일 경우) stack 리스트에 문자를 추가한다. 문자가 ')' 인 경우 stack 리스트가 empty이거나 stack의 마지막 원소를 꺼냈을 때 '['인 경우 flag를 False로 변환 break로 반복문 나옴 stack의 마지막..
![]()
[문제] https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net [풀이] 원하는 문서가 몇 번째로 인쇄되는지를 출력해야 하기 때문에 인쇄 큐 순서가 바뀔 때마다 인덱스 순서도 같이 바꿔줘야 한다. 그래야만 원래 m번째 문서가 언제 출력되는지 구할 수 있다. 입력값을 알맞게 변수에 넣은 후 idx 리스트를 선언한 후 원하는 문서 인덱스 값은 'target'으로 바꾼다. 예를 들어 예제 입력의 두 번째 테스트 케이스에서 idx[m] = 'target'을 하면..
![]()
[문제] https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net [풀이] 2021.07.28 - [BOJ] - [Python] BOJ/백준 11650번 좌표 정렬하기 [Python] BOJ/백준 11650번 좌표 정렬하기 [문제] https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. ..
![]()
[문제] https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net [풀이] 처음에는 슬라이싱을 이용해 str(i)[-3:] == '666' 이런 식으로 끝에서부터 세 자리씩 '666'과 같은지 비교해야 되나 했다. 생각해보니 문자열은 in을 이용해 간단하게 풀 수 있는 방법이 있었다. i가 666부터 1씩 증가하는 while문이 있다. 만약 i를 str로 바꾼 문자열 내부에 '666'이 있다면 cnt를 1 증가시켜준다. cnt가 입력값인 n과 일치한다..
