본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 10423 전기가 부족해 (다익스트라) 문제 출처 : www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net K개의 발전소, N개의 도시, M개의 케이블수가 주어졌을때, 발전소에서 시작해서 모든도시까지 전기를 공급하는 문제다. 풀이 입력받은 발전소들을 시작지점으로해서 다익을 돌리면된다. 예를들어, 발전소가 3개일경우 다익의 시작지점은 총 3개가 된다. 코드를 짜면서 몇가지 반례?가 될수있는걸 생각해봤는데, 도시와 발전소 사이에 발전소가 존재할경우..? 발전소 N..
[백준 / BOJ] 9009 피보나치 문제 출처 : www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n� www.acmicpc.net N을 입력받았을때, 피보나치수들을 최소한으로 사용해서 N을 만들면 되는 문제다. 예를들어, N = 100일때, 피보나치수 3 8 89 풀이 피보나치수들을 최소한의 수로 조합해서 N을 만들어야 하기 때문에, N에서 가능한 가장 큰 피보나치수 부터 빼가면서 출력하면 된다. 피보나치수는 0 1 1 2 3 5 8 13 21 34 55 89 144... 이렇게 늘어나고, 100의 경우 144 는 100보다 ..
[백준 / BOJ] 3042 트리플렛 문제 출처 : www.acmicpc.net/problem/3042 3042번: 트리플렛 상근이와 창영이는 트리플렛이라는 게임을 하고 있다. 이 게임을 하려면 칠판에 N*N 그리드를 그려야 한다. 그 다음 알파벳 대문자를 적절히 각 칸에 써 넣는다. 한 알파벳을 여러 칸에 쓸 수는 �� www.acmicpc.net N*N그리드가 주어지고, 각 칸에 알파벳 혹은 '.'이 주어진다. 이때 3개의 알파벳이 한 직선을 이루면 이를 트리플렛 이라고 한다. 예를들어, ...A ..B. .C.. D... 은 ABC가 하나의 트리플렛을 이룬다, BCD가 트리플렛을 이룬다... 라고 생각하면된다. 풀이 그냥 완전탐색을 할경우, N이 최대 100이고 N*N이므로, 칸의 총 갯수는 100*100 = 10000개이다. 여기서 ..
[백준 / BOJ] 8901 화학 제품 문제 출처 : www.acmicpc.net/problem/8901 8901번: 화학 제품 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 상근이가 가지고 있는 A, B, C의 양이 주어진다. 둘째 줄에는 AB, BC, CA의 가격이 주어진다. www.acmicpc.net 상근이는 세 종류의 화학물질 A, B, C를 가지고 있다. 화학물질을 AB, BC, CA로 조합해서 세가지 제품을 만들수있는데, A,B,C의 갯수와 AB,BC,CA의 가격이 주어졌을때, 상근이가 얻는 최대이익을 출력하는 문제다. 풀이 완전탐색으로 풀리는문제다. 하지만, 그냥 모든경우를 봐줄경우, 1000 * 500 * 250 * 250 ?? 처럼 나와서 시간초과가 난다. 한가지 제..
[백준 / BOJ] 15658 연산자 끼워넣기 (2) 문제 출처 : www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수� www.acmicpc.net N개의 수가 주어지고, +, -, *, /연산자의 갯수가 주어진다. 이때, N개의 수와 연산자들로 만들수있는 조합중 최댓값과 최솟값을 찾는문제다. (단, 주어진 수의 순서를 꾸면 안된다.) 풀이 백트래킹을 이용한, 구현문제다. 연산자와 숫자를 전부 사용하지않고도 최댓값, 최솟값이 나올수있다는 조건을 주의하면서 코딩하자. ope[i] = 연산자 사용가능 ..
[백준 / BOJ] 2313 보석 구매하기 출처 풀이 : www.acmicpc.net/problem/2313 2313번: 보석 구매하기 첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 2×n개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1 ≤ L ≤ 1,000)이 주어지고, 그 다음 줄에 www.acmicpc.net 보석가게에 보석이 여러줄에 걸쳐 진열되어있다. 각각의 보석은 정수로 표현된다. 이때 음수도 나올수있다. 보석은 연속해서 구매할수있는데, 1 2 3을 구매할수있지만, 1 3 을 구매하지 못한다. 보석 가치의 총합이 최대가 될때를 찾아는 문제다. 풀이 한줄당 최대 1000개의 보석이 있을수있고, 최대 1000개의줄이 나올수있다. 따라서 최대 보석은 1000000개 만..
[백준 / BOJ] 12933 오리 문제 출처 : www.acmicpc.net/problem/12933 12933번: 오리 첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다. www.acmicpc.net 오리의 울음소리는 quack이다. 'q', 'u', 'a', 'c', 'k'로 이루어진 문자열이 주어졌을때, 존재할수있는 오리의 최소수를 구하는 문제다. 풀이 구현문제다. 가능한 최소한의 오리 수를 구해야하므로, 'q'를 만났을때부터 시작해서 오리의 울음(quack)을 만들때마다 각 문자열 위치를 체크해준다. 한 오리를 최대한 많이 울게하면 된다. 예를들어, 울음소리가 quqacukqauackck로 주어졌다면 0번 인덱..
[백준 / BOJ] 5635 생일 문제 출처 : www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 각 학생이 이름 년도 월 날짜 로 주어질때, 가장 나이가 많은 학생의 이름, 가장 나이가 적은 학생의 이름을 출력하는 문제다. 풀이 pair로 선언하고 오름차순 정렬하면 끝나는 문제다. vector vec; 처럼 선언하고 {{년도, 월},{날짜, 이름}}이 들어갔을때, 이를 오름차순 정렬하면, 1. 빠른년도순으로 2. 년도가 같으면 3. 빠른 월 순으로 4. 월이 같다면 빠른 날짜 순으로 자동 정렬해준다. 각 벡터의 끝과 시작을 출력하면 된다. 소스코드 https://gith..

티스토리툴바