알고리즘
-
백준 2357번 : 최솟값과 최댓값알고리즘/BOJ 2021. 6. 28. 16:37
문제 : https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net s Eng 1.s dollar(s); [$] (포르투갈) escudo(s); peso(s); sol[soles]; yuan(s) 2.s. second(s) 초; section; see; series; set; sign; silver; singular; small; society; solidus ((L = shilling(s))); son; south;..
-
백준 16562번: 친구비알고리즘/BOJ 2021. 6. 27. 20:48
문제 : https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 친구 관계를 유지하기 위해 친구비를 내야하는데, 그 최소의 친구비를 구해야하는 슬픈 문제다. 문제를 읽어보면 바로 알겠지만 집합문제다. 집합문제는 80% 이상 union-find 알고리즘으로 풀리는데 이 문제도 해당된다. 그런데 요즘 set 자료형을 안써서 오랜만에 기억좀 환기할겸 set 자료형을 이용한 풀이로 풀어봤다. 1번 학생부터 n번 ..
-
백준 11003번 : 최솟값 찾기알고리즘/BOJ 2021. 6. 26. 14:21
문제 : https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net L 길이 만큼 각 subarray에서 최솟값을 찾는 문제다. 당연한 소리지만 만약 모든경우를 탐색하는 즉 O(NL) 방법으로 이 문제를 풀면 시간초과가 뜰것이다. 그래서 매번 최소값을 찾기위한 연산이 필요없는 자료구조를 구현해야한다. 처음에는 항상 정렬된 상태를 가지는 우선순위 큐를 생각했다. 그런데 평범한 우선순위큐를 사용했을때 생기는 문제는, 만약 su..
-
백준 5430번: AC (C++)알고리즘/BOJ 2021. 6. 26. 13:53
문제 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제는 굉장히 쉽다. 굉장히 쉬운 문제지만 굉장히 귀찮고 짜증나는 문제다. 이 문제의 핵심은 첫번째는 reverse order에서 소비되는 시간을 줄이기 위해 디큐(데크)를 사용하는것과 [1,2,3] 처럼 괴상하게 input으로 들어오는값을 잘 처리하는 것이다. 처음에는 input의 각 숫자를 stoi 함수를 이용해서 처리하니까 시간초과가 나서 char타입을 처리해서 int 타입으로 바꿔주는 방법을 사용했다. #include #include #..
-
백준 1937번: 욕심쟁이 판다 (C++)알고리즘/BOJ 2021. 6. 25. 22:06
문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 판다가 너무 곱게 자랐는지 밥을 더 안주면 굶어 죽는 문제다. 딱보면 알겠지만 탐색문제이다. 브루트포스 문제를 풀듯이 모든 좌표에 대해 가능한 모든 경우의 수를 탐색하는 방법으로 풀어도 가능은 하겠지만, 그런 방법으로 풀면 분명 시간초과가 뜰것이다. 근데 조금 생각해보면 판다가 미쳐서 밥을 더주는 방향으로만 이동한다. 즉 그래프로 치환하여 생각하면, 사이클이 없을것이고 트리처럼 ..
-
백준 4195번: 친구 네트워크 (C++)알고리즘/BOJ 2021. 6. 25. 21:56
{"mean":["develop\n \t\t\t\n\t \t(←development) [동사]\n\t\t ~ (sth) (from sth) (into sth)\n\t\t \t\t성장[발달]하다[시키다]","development\n \t\t\t\n\t \t(←develop) [명사]\n\t\t \t\t발달, 성장","step [명사]\n\t\t \t\t(발)걸음\n\n\t\t 참조 footstep, goose-step","by [전치사]\n\t\t \t\t… 옆[가]에","go\n \t\t\t\n\t \t(←goes) [동사]\n\t\t \t\t(한 장소에서 다른 장소로) 가다"],"word":"\n\t\t\t\t\t\tdevelop\n \t\t\t\n\t \t(←development)\n\t ","sou..
-
구글 킥스타트(Kickstart) 2021 Round A 문제풀이알고리즘/킥스타트 2021. 3. 24. 00:25
문제 풀고 나중에 혼자 다시볼겸 남기는 포스트 Prob.1 K-Goodness String 입력 받은 문자열을 좌우대칭이 되게 만드는게 목표 그냥 깊게 생각할것도 없이 좌우 끝으로 부터 하나씩 비교하면서 서로 다른 경우 횟수를 기록해주고 이 횟수와 주어진 K와의 차가 답이 된다 test_n = int(input()) for tn in range(test_n): string_len, k = map(int, input().split(' ')) string = input() score = 0 ans = 0 for i in range(0, int(string_len/2)): if string[i] != string[string_len-i-1]: score += 1 ans = abs(score - k) print..