본문 바로가기

Algorithm

(2139)
(C++) - 백준(BOJ) 16479번 : 컵라면 측정하기 www.acmicpc.net/problem/16479 16479번: 컵라면 측정하기 첫째 줄에 K의 값이 주어진다. 둘째 줄에는 D1과 D2의 값이 사이에 공백을 한 개 두고 차례대로 주어진다. 단, K, D1, D2의 값은 양의 정수이다. www.acmicpc.net 수학 문제였습니다. 풀이방법 상기와 같이 3가지 형태의 컵라면이 나올 수 있습니다. 하지만 이를 하나의 공식으로 한 번에 높이를 구할 수 있습니다. n = (max(d1,d2) - min(d1,d2)) / 2 정답 : k * k - n * n Code #include using namespace std; double k,d1,d2,n; int main(){ cin >> k >> d1 >> d2; n = (max(d1,d2)-min(d1,d..
(C++) - 백준(BOJ) 1138번 : 한 줄로 서기 www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net greedy 문제였습니다. 풀이방법 1. 가장 작은 키의 사림이 위치한 곳은 자기가 왼쪽으로부터 떨어진 거리입니다. 왜냐하면 무조건 자기 보다 큰 사람이 왼편에 서기 때문입니다. 이를 착안한다면 n^2의 시간복잡도로 문제를 해결할 수 있습니다. 2. 0의 개수를 세줍니다. 그래서 0의 개수가 i번째 사람의 키와 같고 비어있는 위치라면 바로 정답배열에 키의 값을 넣어줍니다. Code #include usi..
(C++) - 백준(BOJ) 11497번 : 통나무 건너뛰기 www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 정렬문제였습니다. 풀이방법 인접한 높이 차이가 최소가 되려면 가장 높이가 높은 통나무 양 옆으로 작은 통나무가 배치되어야 합니다. 또한 이를 직접 배치하지 않고서 알 수 있는 방법은 정렬 후 한 칸 더 건너뛰어 2칸 떨어진 통나무끼리의 높이 차이들 중 최대를 구하면 이는 곳 난이도가 됩니다. Code #include using namespace std; int t; int main(){ cin >> t; wh..
(C++) - 백준(BOJ) 3273번 : 두 수의 합 답 www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net map을 이용해 푼 문제였습니다. 풀이방법 1. map에 key는 a의 원소, value는 존재여부(0은 없음,1은 있음)으로 해 저장합니다. 2. (x - map.first, map.first) 가 모두 1이라면 한 쌍이 만들어지므로 답 변수 ans++해줍니다. 3. 중복해서 더해졌으므로 ans/2를 출력합니다. Code #include #define l..
(C++) - 백준(BOJ) 1431번 : 시리얼 번호 답 www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 정렬 문제였습니다. 풀이방법 stl의 sort함수는 정렬기준을 커스터마이징한 함수를 넣어 원하는 대로 정렬할 수 있습니다. Code #include using namespace std; int n; vector serial; bool cmp(string a, string b){ if(a.size() == b.size()){ int sumA = 0,sumB = 0; for(int i = 0; i < a...
(C++) - 백준(BOJ) 11652번 : 카드 답 www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net map을 사용해 푼 문제였습니다. 풀이방법 1. key : 카드의 수, value : 해당 수가 나온 개수인 map자료구조 변수 m을 선언합니다. 2. 가장 많이 나온 수를 구하고 map을 처음부터 순회하면서 iterator의 second와 같다면 first를 출력하고 종료합니다. *int범위를 초과하므로 변수를 long long으로 선언해야합니다. Code #include #define ll long l..
(C++) - 백준(BOJ) 10825번 : 국영수 답 www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 정렬 문제였습니다. 풀이방법 stl에서 sort함수를 사용할 때 정렬 기준을 커스터마이징할 수 있습니다. Code #include using namespace std; int n; struct Student { string name; int korean, english, math; }; vector v; bool cmp(Student &a, Student &b){ if(a.korean ==..
(C++) - 백준(BOJ) 17298번 : 오큰수 답 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 stack으로 푼 문제였습니다. 풀이방법 1. 인덱스를 넣어줄 스택을 만들어줍니다. 입력을 받은 뒤, 스택이 비어있지 않다면 현재 값보다 작은 동안 해당 인덱스의 값을 갱신해주고 스택 pop해줍니다. 2. 그렇게 모두 수행한다면 찌꺼기가 남는데 오른쪽에 더이상큰 값이 없는 경우에 해당합니다. 그런 값들의 index를 저장하고 있는 stack에 대해 stack이 빌 때까지 top에 해당하는 인덱스의 값들을 -1하고 pop해줍니..