본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 2343번 : 기타 레슨 답 www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이분탐색 문제였습니다. 이분탐색시 pivot역할을 하는 left, right의 초기값과 max값을 잘 생각해 작성해야합니다. 풀이방법 1. 이분탐색시 비교할 초기값 생각하기 : 가장 긴 레슨이 곧 해당 블루레이 길이의 최소가 되므로 이를 left로 두고 right는 블루 레이의 개수가 1개, 10만개의 레슨 개수, 모든 레슨의 길이가 1만일경우 한 블루레이의 길이는 1만 * 10만 = 10000 * 100000 = 1..
(C++) - 백준(BOJ) 2141번 : 우체국 답 www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 X[1] A[1], X[2] A[2], …, X[N] A[N]이 주어진다. 범위는 |X[i]|≤1,000,000,000, 0≤A[i]≤1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 이분탐색 문제였습니다. 지문이 헷갈렸는데 먼저 우체국은 무조건 마을이 있는 위치에 세워야 합니다. 1.5 위치같은 소수점 위치에 세우거나 마을이 존재하지 않는 위치에 우체국을 만드는 경우는 없습니다. 또한 우체국을 세운 위치로부터 왼쪽 끝 마을에 위치한 사람들까지의 합, 우체국을 세운 위치 바로 다음 마을부터 오른쪽 끝 마을에 위치한 사람들까지의 합이 ..
(C++) - 백준(BOJ) 2022번 : 사다리 답 www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있다. www.acmicpc.net 피타고라스 정리, 그래프 식세우기를 이용해 이분탐색을 하는 문제였습니다. 풀이방법 입력받는 x,y를 각각 a,b라고 가정한 뒤 구하려는 값을 k, 두 빌딩의 높이를 각각 A,B라고 가정했습니다. 이 때 가장 왼쪽 하단 꼭지점을 0,0으로 하여 직선 a,b에 대한 방정식을 구했습니다. 이 정보들을 공식으로 표현하면 다음과 같습니다. $A = \sqrt{a^2 - k^2}$ $B = \sqrt{b^2 - k^2}$ 직선 a에 대한 방정식 f(x) $f(x) = -\frac{A}{k}x + ..
(C++) - 백준(BOJ) 1590번 : 캠프가는 영식 답 www.acmicpc.net/problem/1590 1590번: 캠프가는 영식 첫째 줄에 버스의 개수 N과 영식이가 버스터미널에 도착하는 시간 T가 주어진다. 둘째 줄부터 총 N개의 줄에 각 버스의 시작 시각, 간격, 대수가 공백을 사이에 두고 주어진다. 버스의 개수와 각 www.acmicpc.net 예외경우 처리가 중요했던 완전탐색 문제였습니다. 풀이방법 1. 유효한 버스 도착시간의 범위(남은시간) : 영식의 도착시간 - 버스 출발시간 x번째 버스 = 남은시간 / 배차간격 , 나머지가 0이면 그대로 적용 : 나머지가 0이 아니면 +1을 적용 2. 남은시간이 음수라면 버스타지 못하므로 x번째 버스는 0 3. 영식의 도착시간보다 늦게 도착하는 버스의 도착시간 : 버스 출발시간 + 배차 * x번째버스 4. ..
(C++) - 백준(BOJ) 1935번 : 후위 표기식 2 답 www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net stack을 이용해 후위 표기식을 구현했습니다. 풀이방법 1. 알파벳이라면 stack push해줍니다. 2. 알파벳이 아니라면 2개의 피연산자를 pop한 뒤 결과값을 stack push해줍니다. Code #include using namespace std; string operation; stack calculator; map m; int main(){ int n; cin >> n >> operati..
(C++) - 백준(BOJ) 1972번 : 놀라운 문자열 답 www.acmicpc.net/problem/1972 1972번: 놀라운 문자열 대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문 www.acmicpc.net 풀이방법 1. backtracking 알고리즘을 이용해 조합으로 두 개의 문자를 뽑고 그 때의 거리를 계산해 vector에 저장합니다. 2. vector의 index가 곧 거리가 되며 해당 거리에 모인 문자열들이 저장되었으니 매 index마다 문자들을 검사하여 map에 없는 문자열이라면 insert해주고 있는 문자열이라면 놀랍지 않으므로 false를 반환해줍니다. 3. 놀라움의 여부에 따라 적절한 문구를 출력해..
(C++) - 백준(BOJ) 1072번 : 게임 답 www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net 최대 값 설정, 승률 계산 방식을 신경써 푼 기본 이분탐색 문제였습니다. 풀이방법 앞으로 할게임 수를 mid로 두어 z값이 바뀌는 최소값을 이분 탐색을 통해 찾습니다. 1. 승률이 99%라면 게임을 아무리 많이해도 100%가 될 수 없으므로 -1을 반환합니다. 2. 승률이 달라질 경우(기존 승률보다 ) r = mid - 1, 아닐경우 l = mid+1로 l= 99) return -1; while(l> game >> win; cout
(C++) - 백준(BOJ) 1822번 : 차집합 답 www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net map, vector 자료구조를 이용해 간단히 풀 수 있었던 문제였습니다. 풀이방법 1. b의 원소를 key, 해당 원소의 빈도 수를 value로 한 map 자료구조를 만들어 저장합니다. 2. a의 원소들중 map(b의 원소-key, 그 원소가 나온 빈도수-value)에 없는 원소들을 vector 자료구조에 저장합니다. 3. 저장된 vector를 정렬 후 적절히 출력합니다. ..

티스토리툴바