알고리즘/BOJ
-
백준 2513번 : 통학버스 (C++)알고리즘/BOJ 2021. 12. 6. 19:39
문제: https://www.acmicpc.net/problem/2513 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원 www.acmicpc.net 수용 한계량이 있는 통학버스가 존재할 때, 모든 학생을 태울 수 있는 최소거리를 찾는 문제입니다. 생각을 해보면 모든 학생을 태워야 하므로 멀리 있는 학생 위치도 결국엔 한 번 이상은 지나야 합니다. 그래서 멀리 있는 학생들부터 태워서 오는 길에 수용량이 남으면 태우는 방법으로 하면 최소거리를 구할 수 있는 그리디 문제입니다. 통학버스의 시작 위치를 s라 하면..
-
백준 2473번 : 세 용액 (C++)알고리즘/BOJ 2021. 7. 13. 21:42
문제 : https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 정수 배열에서 3개의 수를 골라 그 3개의 합이 최대한 0에 가까운 조합을 찾는문제이다. 먼저 N의 범위를 보자. N의 범위는 5000이하인 수로 O(N^2) 방법으로 시간내 풀 수 있음을 추측가능하다. 만약 골라야 하는 수가 3개가 아니고 2개라면 투 포인터나 해쉬맵으로 쉽게 해결할 수 있을 것이다. 그런 경우에는 배열의 사전에 정렬해줘야하므로 O(NlogN + N..
-
백준 1744번 : 수 묶기 (C++)알고리즘/BOJ 2021. 7. 7. 16:07
문제 : https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수열을 입력을 받고 임의의 원소들을 묶어 최대 수열 합을 구하는 문제이다. 그리디 알고리즘을 이용하면 쉽게 풀 수 있다. 입력값의 범위를 보면 -10,000 보다 크고 10,000보다 작은 수이다. 즉 양수 음수 혹은 0을 입력받는데 다음과 같은 경우로 나눌수 있다 1. 양수, 양수 둘다 1보다 큰 수면 두 수를 묶어 곱으로 만드는 것이 더 클것이고, 1이 존재한다면 묶지 않는게 더 크..
-
백준 2568번 : 전깃줄-2 (C++)알고리즘/BOJ 2021. 7. 2. 21:04
문제 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 전깃줄이 서로 겹치지 않게 하기 위해 제거해야 하는 전깃줄의 최소 개수와 해당 전기 줄들을 출력해야 하는 문제다. 위 문제는 가장긴부분수열 문제로 만약 해당 문제를 풀지 않았다면 먼저 아래 문제부터 풀어보도록하자 https://www.acmicpc.net/problem/14003 전깃줄 정보를 입력받은 뒤 A 위치에 따라 정렬시킨다음 B 위치 값에 따른 가장긴부분수열을 구하면 된다. ..
-
백준 1799번 : 비숍 (C++)알고리즘/BOJ 2021. 7. 2. 13:18
문제 : https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 체스판에 비숍을 최대 몇개까지 놓을 수 있는지 찾는 문제. 일단 뻔하지만 백트래킹 문제다. 그래서 처음에 별 생각없이 모든 경우에 대해 백트래킹을 시도해니 시간초과 해버렸다... 고민좀 하다가 인터넷에서 풀이를 참고하였다. 생각해보면 체스판은 흑, 백으로 나누어져 있다. 그리고 체스좀 둬본 사람은 알겠지만 비숍은 대각선으로만 이동이 가능하니 다른 색깔의 위치로는 이동이 불가하다. 즉 흑에 있는 비..
-
백준 11505번 : 구간 곱 구하기 (C++)알고리즘/BOJ 2021. 7. 1. 16:12
문제 : https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 구간 곱 구하기 문제로 아래 링크의 구간 합 구하기 문제와 매우 유사하다. 마찬가지로 세르먼트트리로 손쉽게 풀 수 있다. 차이점으로는 합 대신 곱 연산을 해야함과 0일때가 있을수 있으므로 update 함수를 조금 다르게 구현해야한다. 구간합구하기: https://www.acmicpc.net/problem/2042 기존 세그먼트..
-
백준 1062번 : 가르침 (C++)알고리즘/BOJ 2021. 7. 1. 13:46
문제 : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net K개의 알파벳만을 이용해서 최대한 많은 단어들을 가르쳐야하는 문제! dp로 풀어야하나 했는데 n의 범위가 50이하인것을 보고 dfs 백트래킹으로 충분히 풀수있다 판단하였고 백트래킹 + 비트마스킹으로 해결하였다. 알파벳 a~z 는 0~25로 1대1 대응시키고 비트마스킹으로 만약 x를 가르친다면 state |= (x - 'a') 방법으로 비트마스킹 state 관리를 시켜주었다. #in..
-
백준 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;..