본문 바로가기

백준54

[Python] 백준 9935번 문자열 폭발 https://www.acmicpc.net/problem/9935 풀이string 내장함수 partition을 사용하면 문제를 쉽게 해결 할 수 있으나 string 범위가 1000000 이므로 시간초과가 발생합니다.따라서 stack구조를 사용해 한번의 반복문으로 해결합니다.stack의 폭발문자열의 길이에 해당하는 마지막 문자열을 검사하여, 폭발문자열이라면 stack에서 pop 해줍니다.string = input()exp = input()ex_len = len(exp)# while True:# s = string.partition(exp)# if s[1] == '':# break# string = str(s[0]) + str(s[2])# if string == '':# .. 2024. 9. 27.
[Python] 백준 대피소 https://www.acmicpc.net/problem/28215 from itertools import combinationsimport sys# sys.stdin = open('input.txt')N, K = map(int, input().split())X = []Y = []for i in range(N): x, y = map(int, input().split()) X.append(x) Y.append(y)def sol(c): b = 0 for h_idx in range(N): a = 100000 for c_idx in c: a = min(a, abs(X[h_idx] - X[c_idx]) + abs(Y[h_idx] - Y[c_i.. 2024. 9. 25.
[C++] 백준 전자레인지 https://www.acmicpc.net/problem/10162풀이최소 버튼 조작으로 정해진 요리시간을 만들 수 있는지 구하는 문제입니다. 그리디 알고리즘을 사용해 문제를 해결할 수 있습니다.#include #include using namespace std;int main(){ // freopen("input.txt", "r", stdin); int time; cin >> time; int a_bt = 300; int b_bt = 60; int c_bt = 10; vector v(3, 0); v[0] = time / a_bt; time = time % a_bt; v[1] = time / b_bt; time = time % b_bt.. 2024. 6. 20.
[C++] 백준 세탁소 사장 동혁 https://www.acmicpc.net/problem/2720풀이거스름돈으로 남겨주는 동전의 갯수를 최소화 하는 문제입니다.그리디 알고리즘을 사용해 답을 구할 수 있습니다.#include #include using namespace std;int main(){ // freopen("input.txt", "r", stdin); // Quarter = 0.25 // Dime = 0.1 // Nickel = 0.05 // Penny = 0.01 int TC; cin >> TC; double dollar; double quater = 25; double dime = 10; double nickel = 5; double penny = .. 2024. 6. 20.
[C++] 백준 고층 건물 https://www.acmicpc.net/problem/1027풀이현재 건물에서 바라보는 건물의 기울기를 검사하여, 현재까지의 기울기보다 큰 경우는 서로를 볼 수 있는 경우이므로 카운트한다.초기 기울기는 문제에서 가능한 최솟값으로 초기화 후, 현재 값보다 큰 기울기가 나오면 업데이트 해준다. #include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); // freopen("input.txt", "r", stdin); int N; cin >> N; vector buildings; for (int i = 0; i > height;.. 2024. 6. 18.
[C++] 백준 투명 https://www.acmicpc.net/problem/1531 #include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); // freopen("input.txt", "r", stdin); int N, M, lx, ly, rx, ry; int ans = 0; cin >> N >> M; vector> p(102, vector(102, 0)); for (int i = 0; i > lx >> ly >> rx >> ry; for (int row = lx; row M) ans++; } .. 2024. 6. 18.
[C++] 백준 DNA 해독 https://www.acmicpc.net/problem/1672 1672번: DNA 해독 N개의 A, G, C, T로 구성되어 있는 DNA 염기서열이 있다. 그리고 우리는 이 염기서열을 아래의 표를 이용하여 해독을 해야 한다. 해독 방법은 염기 서열에서 제일 끝에 있는 두 개의 염기를 An-1, An이 www.acmicpc.net 풀이 염기서열의 길이 범위가 N(1 ≤ N ≤ 1,000,000) 이므로 한번의 반복문으로 해결해야 하는 문제입니다. 주어진 염기 표를 map 자료구조를 사용해 해싱하여 문제를 해결할 수 있습니다. map 을 선언하고 모든 표를 기록해줍니다. 문자열을 빼는 경우 string의 pop_back() 함수를 사용하면 됩니다. #include #include using namespa.. 2024. 1. 30.
[C++] 백준 평균은 넘겠지 https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다. 정답과 출력값의 절대/상대 오차는 10-3이하이면 정답이다. www.acmicpc.net 리뷰 cout > tc; for (int i = 0; i > num; double avg = 0; vector v; for (int j = 0; j > score; avg += score; v.push_back(score); } avg = (double) avg / num; int cnt = 0; for (auto n : v) { if (n > avg) { cnt++.. 2024. 1. 23.
[C++] 백준 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 행의 크기가 2, 열의 크기가 n인 입력이 주어졌을 때 상,하,좌,우로 이웃하지 않는 숫자를 더해 만들 수 있는 최대합을 구하는 문제입니다. 숫자를 선택하는 점화식을 찾아 bottom-up방식의 다이나믹 프로그래밍을 사용해 문제를 해결할 수 있습니다. dp[i][j]에는 i, j 에서의 최대합을 저장해야 합니다. 최종 j에 도달한 후에는 dp[0][j]와 dp[1][j] 중 최대값.. 2024. 1. 22.
[C++] 백준 N과 M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 N과 M이 주어졌을 때, N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제입니다. 단, 중복된 조합을 출력해서는 안되며, 오름차순 출력해야 합니다. 입력 받은 자연수 N개를 오름차순 정렬한 후, 재귀를 사용해 모든 조합을 만들면서 이미 만들어진 조합은 해쉬를 사용해 판단하는 방식으로 알고리즘을 구현했습니다. 입력 받은 N개의 자연수를 담기위한 변수 vector v 와, 만들어진 조합을.. 2024. 1. 21.

티스토리툴바