본문 바로가기

전체 글

 (2344)
(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) 1166번 : 선물 답 www.acmicpc.net/problem/1166 1166번: 선물 첫째 줄에 N L W H가 주어진다. 모든 값은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 간단한 이분탐색이었으나.. 자료형과 시간초과, 출력을 신경써야되는 그런 문제였습니다. 풀이방법 찾으려는 정육면체 박스의 한변 길이를 mid로 하여 이분탐색을 시행합니다. 1. 이분탐색 로직 1-1. (가로/mid * 세로/mid * 높이/mid)의 값이 n미만이면 박스의 길이를 줄여야 합니다. 곱하게 되므로 int 범위를 초과할 수 있기 때문에 각 항을 long long형으로 변환해줘야합니다. 1-2. 반대라면 박스의 길이를 늘일 수 있습니다. 2. 출력 : 1-2의 경우일때의 left값이 곧 최대의 박스 ..
(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를 정렬 후 적절히 출력합니다. ..
(C++) - 백준(BOJ) 1302번 : 베스트셀러 답 www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 간단한 map을 이용한 구현이었습니다. 풀이방법 1. 책 이름을 key, 책 이름이 나온 빈도 수를 value로 한 map 변수를 만들어 정보를 저장합니다. 2. map 자료구조는 자료를 저장할 떄 key값을 기준으로 오름차순으로 정렬되므로 가장 빈도 수가 높은 값을 찾으면 바로 key값을 출력 후 프로그램을 종료하면 됩니다. Code #include using namespace std; map m; i..
(C++) - 백준(BOJ) 1269번 : 대칭 차집합 답 www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 풀이방법 1. a에 대한 원소를 key, 나온 빈도를 value로 한 map 자료구조를 만듭니다. 2. b의 원소를 map에서 key로 하여 검색했을 때 값이 있다면 a와 공집합에 대한 원소이므로 세줍니다. 3. 답출력 : a원소 개수 + b원소 개수 - (공집합 원소의 개수 * 2)를 출력해줍니다. Code #include using namespace std; map m; int aSize,bSize, ..

티스토리툴바