본문 바로가기

BOJ89

백준 알고리즘 7568 (덩치) - python (재풀이) 백준 알고리즘 7568 (덩치) - python (재풀이) > https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 자신보다 몸무게와 키 값이 모두 큰 사람이 몇 명인지 알면 된다. [문제 풀이] 1. 자신보다 (무게, 키) 값이 모두 큰 사람을 센다. 2. 아무도 없다면 1등이기 때문에 +1을 result에 저장 3. 한 번에 합쳐서 출력 import sys N = int(sys.stdin.readline()) people = [lis.. 2022. 5. 18.
백준 알고리즘 15650 (N과 M(2)) - python (재풀이) 백준 알고리즘 15650 (N과 M(2)) - python (재풀이) > https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 오랜만에 다시 하니까 헷갈린다...! 중복 없이, 오름 차순 문제! [문제 풀이] 1. N의 index가 헷갈리지 않게 N+1의 자연수화 2. 탈출 조건 depth == M 설정 3. 이전 자릿수보다 크게 되도록 for문에서 i+1 설정 4. 배열에 append 하면서 백트래킹 import sys def DFS(depth,.. 2022. 5. 17.
백준 알고리즘 2231 (분해합) - python (재풀이) 백준 알고리즘 2231 (분해합) - python > https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net [문제 풀이] 1. 자신과 각 자릿수를 더해야하기 때문에, 간단하게 하려면 String으로 접근하는게 낫다. 2. 없으면 0을 출력하기 위해 있을 경우 미리 return 활용 import sys N = int(sys.stdin.readline()) def solve(): for i in range(N): result.. 2022. 5. 16.
백준 알고리즘 15649 (N과 M(1)) - python (재풀이) 백준 알고리즘 15649 (N과 M(1)) - python > https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹의 기본 문제. 1~N까지 자연수 중 길이가 M인 중복되지 않는 수열 출력 [문제 풀이] 1. depth가 늘어날 때마다 배열을 저장해 줄 result 생성 2. 알아보기 쉽게 (N+1) size로 하여 자연수 값 그대로 적용되게 함 3. DFS 탈출 조건 : 길이(이 문제는 depth로 생각해도 됨)가 M을 만족 4. 저장된.. 2022. 5. 7.
백준 알고리즘 1012 (유기농 배추) - python (재풀이) 백준 알고리즘 1012 (유기농 배추) - python > https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 다시 코딩 연습을 시작한다! 가즈아!!! 거의 백지인 상태지만(ㅠ) 이전에 풀었던 문제들을 다시 재풀이해본다. 위 문제를 요약하면, Map의 크기와 1의 좌표 위치를 받아서 1의 군집이 몇 개 있는지를 체크하는 문제이다. [문제 풀이] 1. 입력들을 받아서 _map에 저장 2. 처리할 수 있는 간단한 예외는 미리 처리 (0, 1, 전체) -> 처리 속.. 2022. 5. 7.
백준 알고리즘 2018 (통계학) - python 백준 알고리즘 2018 (통계학) > https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 산술평균, 중앙값, 범위는 모두 sort 후에 간단하게 해결된다. 여기서 고민할 부분은 최빈값. 게다가 생각해볼 조건도 있다. 먼저, 최빈값을 구하기 위해서 count에 적합한 dictionary를 활용했다. (dictionary가 list보다 검색이 빠르다는 장점) ([from collections import Counter] 방법도 결국 dictionary의 확장) 1... 2021. 7. 24.
백준 알고리즘 1932 (정수 삼각형) - C++, Python [문제] 백준 알고리즘 1932 (정수 삼각형) > https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 부분 문제를 정의하여 점화식 찾기 + 누적하는 방식의 문제이다. 부분 문제를 위한 .. 2019. 11. 15.
백준 알고리즘 2630 (색종이 만들기) - C++, Python [문제] 백준 알고리즘 2630 (색종이 만들기) > https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net '분할 정복(Divide and Conquer)' 문제이다. 분할 정복은 보통 재귀함수의 응용인데, 원하는 조건을 만족하지 않으면 문제를 분할(=작은 부문제)해서 해결하는 방식으로 다시 재귀시킨다. 4등분을 하면.. 2019. 11. 8.
백준 알고리즘 1149 (RGB거리) - C++, Python [문제] 백준 알고리즘 1149 (RGB거리) > https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 집에 빨강, 초록, 파랑 중에 하나의 색을 칠하려는데, 이웃은 같은 색을 칠할 수 없다. 각 색깔에 대한 비용이 주어질 때, 모든 집을 칠하는 .. 2019. 11. 7.
728x90

티스토리툴바