Algorithm

Gyoogle (규글)
[백준 1931] 회의실 배정
·Algorithm/백준(BOJ)
[백준 1931] 회의실 배정문제 출처 : https://www.acmicpc.net/problem/1931 문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 ..
[백준 11047] 동전 0
·Algorithm/백준(BOJ)
[백준 11047] 동전 0출처 : https://www.acmicpc.net/problem/11047문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만드려고 한다. 이 때 필요한 동전 개수의 최소값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최소값을 출력한다. 예제 입력123456789101110 42001510501005001000..
[알고리즘] 그리디 알고리즘
·Algorithm/개념 정리
그리디 알고리즘만약 문제 중에 그리디 알고리즘이 나오면? -> 가장 나중에 풀자! 생각보다 까다로울 수 있는 문제일 수 있기 때문에 마지막에 시간을 많이 갖고 풀어야 함 결정해야 할 때, 그 순간에 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘그때 그때는 최적일지도 모르지만, 최종적으로는 답이 최적이 아닐 수도 있는 가능성 존재 그리디 알고리즘은 언제 써야하나?지금 이 순간, 가장 좋은 경우를 선택하는 것이 항상 최적인 경우 그냥 생각하면 쉬워보이지만, 왜 최적인지 증명을 해야하기 때문에 그리디 알고리즘은 상당히 어려운 영역임
[백준 9012] 괄호
·Algorithm/백준(BOJ)
[백준 9012] 괄호문제 출처 : https://www.acmicpc.net/problem/9012 문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())())..
[알고리즘] 다이나믹 프로그래밍
·Algorithm/개념 정리
[알고리즘] 다이나믹 프로그래밍큰 문제를 작은 문제로 나눠서 푸는 알고리즘 Overlapping Subproblem겹치는 부분 문제Optimal Substructure문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 Overlapping Subproblem큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.문제를 작은 문제로 쪼갤 수 있다.ex. 피보나치 수 Optimal Substructure문제의 정답을 작은 문제의 정답에서 구할 수 있다.ex. 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다. 이 두 가지를 활용하는 것이 다이나믹 프로그래밍!다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 함Optimal Subst..
[알고리즘] 자료구조 (스택, 큐, 덱, 문자열)
·Algorithm/개념 정리
[알고리즘] 자료구조 (스택, 큐, 덱, 문자열) 스택 (Stack)한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조마지막에 넣은 것이 가장 먼저 나오는 LIFO 구조push : 스택에 자료 넣음pop : 스택에서 자료 뺌top : 스택의 가장 위에 있는 자료empty : 스택이 비어있는지 아닌지 확인size : 스택에 저장된 자료의 개수 확인 사용방법C++STL의 stack 이용Javajava.util.Stack - push stack[size] = v; size += 1; ​ - pop stack[size-1] = 0; size -= 1; 스택 활용 문제괄호 : https://www.acmicpc.net/problem/9012쇠막대기 : https://www.acmicpc.net/problem/1079..
[백준 1003] 피보나치 함수
·Algorithm/백준(BOJ)
[백준 1003] 피보나치 함수 문제 출처 : https://www.acmicpc.net/problem/1003 피보나치를 이용해서 fibonacci(0)과 fibonacci(1)의 출력 개수 구하기 피보나치가 이루어지는 과정은 점화식으로 아래와 같이 나타낼 수 있다. 1fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)cs 클래스로 만들어 zero와 one의 값을 저장시킬 수 있도록 만들었다. 0과 1일 때만 초기값을 정해주면, 2부터는 점화식을 이용해서 값을 얻어낼 수 있다. 전체 소스 코드123456789101112131415161718192021222324252627282930313233343536#include using namespace std;class xy{..
[백준 9095] 1, 2, 3 더하기
·Algorithm/백준(BOJ)
[백준 9095] 1, 2, 3 더하기문제 출처 : https://www.acmicpc.net/problem/9095 문제 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다. 1+1+1+11+1+21+2+12+1+12+21+33+1 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1,2,3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력123434710cs 예제 출력123744274cs 문제 이해하기1, 2, 3을 이용해서 주어진 정수의 합을 구할 수 ..
[백준 1932] 숫자 삼각형
·Algorithm/백준(BOJ)
[백준 1932] 숫자 삼각형 문제 출처 : https://www.acmicpc.net/problem/1932 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 숫자는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1줄까지 숫..
[백준 1475] 방 번호 - java로 풀기
·Algorithm/백준(BOJ)
기존에 c++로 풀었던 방 번호 문제를 java로 풀었습니다. 입력한 수를 하나씩 분리해서 배열에 저장하기 위해 몫과 나머지를 이용했었지만, 이번에는 string으로 저장한 후 다시 하나씩 int형으로 전환시켜서 저장하는 방법을 사용했습니다. 아스키 코드 값을 가져오기 위해 꼭 '0'을 빼주는 것 기억하기 1234567String N = scan.nextLine(); // N을 string으로 저장 int number[] = new int[N.length()]; // N의 길이만큼 배열 생성 for(int i = 0; i
[백준 1463] 1로 만들기
·Algorithm/백준(BOJ)
[백준 1463] 1로 만들기 문제 출처 : https://www.acmicpc.net/problem/1463 문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최소값을 출력한다. 예제 입력110cs 예제 출력13cs 10의 경우 최소 횟수는 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 문제 이해하기 처음에 주어진 숫자를, 3가지..
[백준 1475] 방 번호
·Algorithm/백준(BOJ)
[백준 1475] 방 번호 문제 출처 : https://www.acmicpc.net/problem/1475 문제다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다. 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최소값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) 입력첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력첫째 줄에 필요한 세트의 개수를 출력한다. 예제 입력 19999cs 예제 출력 12cs 문제 이해하기 자기 집의 방..
[백준 11441] 합 구하기
·Algorithm/백준(BOJ)
[백준 11441] 합 구하기 문제 출처 : https://www.acmicpc.net/problem/11441 문제N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N) 출력총 M개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다. 예제 입력 1234567851..
[백준 2292] 벌집
·Algorithm/백준(BOJ)
[백준 2292] 벌집 문제 출처 : https://www.acmicpc.net/problem/2292 문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 입력첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 출력입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다. 예제 입력 113cs 예제 출력 13..
[백준 2438] 별찍기 - 1
·Algorithm/백준(BOJ)
[백준 2438] 별찍기 - 1 문제 출처 - https://www.acmicpc.net/problem/2438 문제첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 입력첫째 줄에 N (1 N; if (N >= 1 && N
[백준 2750] 수 정렬하기
·Algorithm/백준(BOJ)
[백준 2750] 수 정렬하기 문제 출처 - https://www.acmicpc.net/problem/2750 문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력첫째 줄에 수의 개수 N(1 N; for(int i = 0; i > arr[i];}cs i가 N번 반복하면서, 내가 입력한 수들이 arr배열에 저장되었을 것이다. 이제 저장된 arr배열끼리 모두 비교하면서, 가장 작은 것부터 출력해야 한다. arr[0]과 나머지 배열 모두를 비교한다. 만약 arr[0]보다 작은 값이 있으면, arr[0]값과 해당 위치 배열의 값을 바꿔서 저장시킨다. 이러면 기존의 arr[0]의 값은 가장 작은 값이 있던 배열로 이동하고, 배열의 맨 처음은 현재 저장된 값 중에 가장 작은 수가 될..
[백준 1912] 연속합
·Algorithm/백준(BOJ)
[백준 1912] 연속합 문제 출처 - https://www.acmicpc.net/problem/1912 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력첫째 줄에 답을 출력한다. 예제 입력 121010 -4 3 1 5 6 ..
[백준 1149] RGB 거리 문제
·Algorithm/백준(BOJ)
[git] 백준 1149, RGB거리 문제 출처 - https://www.acmicpc.net/problem/1149 문제 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 ..
Gyoogle
'Algorithm' 카테고리의 글 목록 (4 Page)
상단으로

티스토리툴바