본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 3151 : 합이 0 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 학생 수 n, 정답을 출력할 변수 ans, 코딩 실력을 저장할 vector v를 선언한 후 적절히 입력받습니다. 이후 v를 오름차순으로 정렬해줍니다. 📔 풀이과정 n이 1만이므로 brute force로 3중 for loop를 수행하면 O(4억)이 넘어 4초 초과로 틀리게 됩니다. O(n^2log(n))으로 2개의 수를 결정했으면 나머지 한 개의 수..
(C++) - 백준(BOJ) 14625 : 냉동식품 https://www.acmicpc.net/problem/14625 14625번: 냉동식품 첫째 줄과 두 번째 줄에 시작시간과 종료시간이 시 H(0 ≤ H ≤ 23)와 분 M(0 ≤ M ≤ 59)이 정수로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 몇 분이 나오는지 알고 싶은 숫자 N(0 ≤ N ≤ 9)이 주 www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 시작 시간, 분, 끝 시간, 분, 찾을 한 자리 수, 정답을 출력할 변수 ans를 선언 후 입력받습니다. 이후 s, e변수에 분으로 환산한 값을 계산해 저장해줍니다. 📔 풀이과정 시간형식 00시 00분을 맞춰 문자열을 반환해주는 함수 getTimeString을 실행해줍니다. 반환값은 curTime에 저장해줍니다...
(C++) - 백준(BOJ) 9469 : 폰 노이만 https://www.acmicpc.net/problem/9469 9469번: 폰 노이만 250마일 길이의 철로 양 끝에 두 기차 A와 B가 있다. A는 시속 10마일, B는 시속 15마일로 서로를 향해 출발했다. 두 기차의 출발과 동시에 기차 A 앞에 붙어있던 파리 한 마리가 기차가 충돌할 때 까 www.acmicpc.net 간단한 수학공식을 이용한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 철로 길이 d, 기차 a, b속력, 파리 속력 f, 기차가 부딪힐 때까지 걸리는 시간 timeLeft를 선언한 후 적절히 입력받습니다. 📔 풀이과정 시간 = 거리/속력입니다. 서로를 향해 출발하므로 다음 공식이 성립합니다. 시간 = d / (a+b) timeLeft에 해당 값을 저장합니다. 📔 정답출력 파리가 ..
(C++) - 백준(BOJ) 21866 : 추첨을 통해 커피를 받자 https://www.acmicpc.net/problem/21866 21866번: 추첨을 통해 커피를 받자 첫 번째 줄에 9개의 정수가 주어진다. 각 정수는 $0$ 이상 $1\,000$ 이하의 정수다. 각 정수는 해당 학생이 각 문제에서 얻은 점수를 의미한다. www.acmicpc.net if문을 사용해보는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 일차원 점수 배열 score, 최대 점수 배열 limit, 상태 state, 전체 점수 totalScore를 선언 후 적절히 입력받습니다. 📔 풀이과정 9개의 점수 정보에 대해 for loop를 수행합니다. 누적 점수를 totalScore에 추가해줍니다. 만약 최대 점수를 넘었다면 state = 2로 만들어줍니다. 📔 정답출력 state가 0이면 none..
(C++) - 백준(BOJ) 23235 : The Fastest Sorting Algorithm In The World https://www.acmicpc.net/problem/23235 23235번: The Fastest Sorting Algorithm In The World It is common to compare sorting algorithms based on their asymptotic speeds. Some slower algorithms like selection sort take O(N2) time to sort N items, while comparison-based sorts like merge sort can go no faster than O(N log(N)) time, under reasonable a www.acmicpc.net 간단한 출력문제였습니다. 📕 풀이방법 📔 입력 및 초기화 문자열 ..
(C++) - 백준(BOJ) 20438 : 출석체크 https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 누적합 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 학생 수 n, 조는 인원 k, 출석코드를 받은 학생 수 q, 구간 개수 m, 구간 s와 e, 정답을 출력할 ans, 학생 vector, map sleep, attend를 선언후 입력받습니다. 📔 풀이과정 * 5000의 학생 수에 대해 50000개의 구간이 들어온다면 brute force로 탐색 시 2..
(C++) - 백준(BOJ) 9161 : Sir Bedavere’s Bogus Division Solutions https://www.acmicpc.net/problem/9161 9161번: Sir Bedavere’s Bogus Division Solutions The wise Sir Bedavere often uses non-standard logic, yet achieves positive results. Well, it seems he has been at it again, this time with division. He has determined that canceling the common digit of a numerator and denominator produces the correct answe www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 사소한 경우(111..
(C++) - 백준(BOJ) 18409 : 母音を数える (Counting Vowels) https://www.acmicpc.net/problem/18409 18409번: 母音を数える (Counting Vowels) 長さ N の英小文字からなる文字列 S が与えられる．S のうち母音字の個数，つまり a，i，u，e，o の個数の総和を求めよ． www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 문자열 s, 모음사전 vowel, 문자열 s의 길이 n, 정답을 출력할 ans를 선언한 후 적절히 입력받습니다. 📔 풀이과정 문자열 s에 대해 for loop를 수행하며 문자마다 모음을 가지고 있는지 vowel과 비교하며 모음이 존재하면 ans를 1씩 더해줍니다. 📔 정답출력 ans를 출력해줍니다. 📕 Code #include using namespace std; string s, ..

티스토리툴바