본문 바로가기

백준 풀이

 (20)
백준 1208 - 부분 수열의 합 2 (Python) 참고 블로그: https://ku-hug.tistory.com/190 [Python/파이썬] 백준 1208번: 부분수열의 합 2 문제 풀이 1. 주어진 수열을 절반으로 나눈다. [-7, -3, -2, 5, 8] -> [-7, -3], [-2, 5, 8] 2. 나눠진 수열의 부분 수열을 구한다. A : [-7, -3] -> [-7], [-3], [-7, -3] B : [-2, 5, 8] -> [-2], [5], [8], [-.. ku-hug.tistory.com 깃허브: https://github.com/MSIQOC/BOJ/blob/master/b1208_%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4%EC%9D%98%ED%95%A92.py https://www.acmicpc.net/pr..
백준 5052 - 전화번호 목록 (Python) https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 파이썬의 리스트에 전화번호를 String 형태로 append해주고 sort를 하면 길이가 짧은 순서대로 정렬이 됩니다. (예: [123, 12345, 253, 8897, 88958]) 리스트가 arr이라고 할 때 리스트를 처음부터 n-1까지 순회하며 arr[i]가 arr[i+1]의 접미사인지 확인하면 됩니다. (주의: 포함이 돼있는지 확인하는게 아니라 접미사인지 확인하는 것..
백준 7453 - 합이 0인 네 정수 (Python) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 어떻게 푸는지 몰라서 검색을 해본 결과, a,b,c,d의 조합을 전부다 구하면 O(n^4)의 시간이 걸리기 때문에 a+b+c+d = 0을 변형해서 a+b = -(c+d)로 바꿔서 a와 b의 조합, 그리고 c와 d의 조합을 각각 O(n^2)의 시간에 구해서 풀면 되는 문제였다. 그리고 파이썬에서 제공해주는 dict()를 사용하면 dict는 해쉬 알고리즘을 이용해서 O(1)만에 원하..
백준 11657 - 합이 0인 네 정수 (Python) 깃허브: https://github.com/MSIQOC/BOJ/blob/master/b11657_%ED%83%80%EC%9E%84%EB%A8%B8%EC%8B%A0.py GitHub - MSIQOC/BOJ: 백준 문제들에 대한 저의 풀이가 포함돼있습니다. 백준 문제들에 대한 저의 풀이가 포함돼있습니다. Contribute to MSIQOC/BOJ development by creating an account on GitHub. github.com https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, ..
백준 17298 - 오큰수 (Python) 깃허브: https://github.com/MSIQOC/BOJ/blob/master/b17298_%EC%98%A4%ED%81%B0%EC%88%98.py https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net https://reakwon.tistory.com/196 [스택] BOJ17298 오큰수 문제 풀이 및 전체 코드(C++) BOJ 17298 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의..
백준 11047 - 동전0 깃허브: github.com/MSIQOC/BOJ/blob/master/b11047_%EB%8F%99%EC%A0%840.java www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 직관적으로 생각했을 때, K원을 만드는데 필요한 동전 개수의 최솟값을 구하려면 값이 큰 동전부터 사용해나가면 된다. 사용할 수 있는 값이 제일 큰 동전부터 사용하고 그 다음에 차례대로 큰 동전들을 사용하는 방식으로 문제를 ..
백준 1149 - RGB거리 깃허브: github.com/MSIQOC/BOJ/blob/master/b1149_RGB%EA%B1%B0%EB%A6%AC.java www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제의 조건은 다음과 같은데, 해석해보면 한 집과 인접한 집의 색깔은 같지 않아야한다는 뜻이다. 문제를 봤을 때 i번째 집에서 i-1번째집과 i+1번째 집의 색을 어떻게 칠해야할지 다 고려해봐야할 것 같지만, 사실 위 그림처럼 1번집부터 차례대로 칠해나갈 때 바로..
백준 9461 - 파도반 수열 깃허브: https://github.com/MSIQOC/BOJ/blob/master/b9461_%ED%8C%8C%EB%8F%84%EB%B0%98%EC%88%98%EC%97%B4.java www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 주어진 그림에서 계속해서 나선모양으로 정삼각형을 그려나가며 규칙을 찾아보았다. 1부터 9까지는 기본적으로 주어진 것이고, 그 뒤로 계속 구해보다보면 규칙을 발견하게 된다. 위 그림을 토대로 기본적으로 주어진 것의 다음 숫자에 대해서는..

티스토리툴바