전체 글
-
1154번 : 팀 편성알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 16. 19:55
https://www.acmicpc.net/problem/1154 1154번: 팀 편성 첫째 줄에 학생 수를 나타내는 자연수 N이 주어진다. (N≤1,000) 편의상 각 학생들은 1부터 N까지 번호가 붙어 있다고 가정한다. 둘째 줄부터 각 줄에 두 개의 자연수 a와 b가 빈 칸을 사이에 두고 주 www.acmicpc.net 학생들을 주어진 조건에 따라 두 그룹으로 나누는 문제이다. 아이디어 : 어떤 학생과 친구가 아니라는 것은, 무조건 그 친구와 다른 그룹이어야 한다는 것이다. 그렇다면, 답이 나오는 상황이라고 가정했을 때, 모든 학생에 대해서 해당 학생과 친구가 아닌 학생들을 전부 그룹으로 묶는 과정을 반복하면, 최종적으로는 두 그룹으로 나뉘어지게 될 것이다. 그 두 그룹에 대해 검증을 한번 더 하면,..
-
1131번 : 숫자알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 14. 20:30
https://www.acmicpc.net/problem/1131 1131번: 숫자 자연수 N이 주어졌을 때, N의 각 자리수를 K제곱 한 후에 그 합을 구하는 함수를 SK(N)이라고 하자. 예를 들어, S2(65) = 62 + 52 = 61이다. 이제 다음과 같은 수열을 하나 만들어보자. N, SK(N), SK(SK(N)), … www.acmicpc.net i부터 시작해서 나열되는 수들 중 가장 작은 수의 합을 구하는 문제이다. 아이디어 : 그래프로 생각한다. 수 하나에서 시작하여 일정 수들을 거치면 항상 사이클이 생기는 것을 파악했다. 따라서 사이클에 속해있는 수들은 항상 똑같은 dp값을 가지고, 그게 아닌 수들만 따로 예외처리 해준다. 구현 : 먼저 p배열엔 0~9의 K제곱을 저장해준다. nxt엔 ..
-
1125번 : 바닥 장식알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 12. 18:49
https://www.acmicpc.net/problem/1125 1125번: 바닥 장식 방 바닥을 꾸미려고 한다. 다음과 같이 1×5 크기의 나무 판으로 만든 무한한 패턴의 평면을 생각해보자. 가장 왼쪽 위 좌표는 (0,0)이고, X좌표는 왼쪽에서 오른쪽으로 증가하고, Y좌표는 위에서 www.acmicpc.net 어떠한 구역에서 바닥 장식 크기마다 개수를 다 구해주고, 그 개수들을 이용해서 1x5 나무 판을 최소한으로 사야하는 문제다. 아이디어 : 첫 번째. 1x1, 1x2, 1x3, 1x4, 1x5 타일이 각각 몇개씩 필요한지 찾는다. 두 번째. 구매해야하는 1x5타일 개수의 최소값을 찾는다. 우선 주어진 구역보다 작은, 5x5 격자에 딱 맞는 직사각형을 하나 더 찾는다. 문제의 예시에선 저 보라색 ..
-
18186번 : 라면 사기 (Large)알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 20:25
https://www.acmicpc.net/problem/18186 18186번: 라면 사기 (Large) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 18185번과 매우 유사한 문제다. 2022.01.09 - [sunrin] - 18185번 : 라면 사기 (Small) 아이디어 : 다만, 한가지가 다르다. B와 C가 주어졌는데, 18185에서는 비용이 3, 5, 7로 연속3개의 공장에서 사는게 무조건 이득이었다. 하지만, 18186에서는 2, 1002, 2002 이런식으로 주어질 수도 있다. 즉, 모든 라면을 B로 사는 케이스..
-
18185번 : 라면 사기 (Small)알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 20:11
https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 연속된 1개 공장에서 라면을 사면 비용 3, 연속된 2개 공장에서 라면을 사면 비용 5, 연속된 3개 공장에서 라면을 사면 비용 7 의 비용을 내고 라면을 살 수 있을 때, 최소 비용을 구하는 문제였다. 아이디어 : 접근은 dp였다. i번째까지 최적화된 배열이 있을 때 i+1번째를 최적화 시키는 방법은 뭐가 있을까? 먼저 라면을 사는 방법은 총 3가지이다. i+1에서만 비용 3 ..
-
1071번 : 소트알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 19:18
https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 문제는 단순하다. A[i] + 1 != A[i+1] 을 만족하도록 모든 수를 다시 배치하는 것이다. 아이디어 : 두 수를 비교해서 위치를 바꾸는 일반적인 정렬 방식은 사용하지 않는다. 수들을 처음부터 하나하나 다시 배치하는 아이디어로 접근한다. 우선, 수를 하나 택한다고 생각해보자. 이 수를 뺀 나머지 수들을 이용해서 절대로 배열을 완성할 수 없다면, 그 수를 택할 수 없다. 반대로 말하면 -> ..
-
1050번 : 물약알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 14:15
https://www.acmicpc.net/problem/1050 1050번: 물약 첫째 줄에 LOVE를 1만큼 만드는데 드는 비용의 최솟값을 출력한다. 만약 그 값이 1,000,000,000보다 크다면 1000000001을 출력한다. 만약 LOVE를 만드는 것이 불가능 하다면 -1을 출력한다. www.acmicpc.net N개의 주어진 재료와 M개의 조합식(또는 새로운 재료)를 갖고 LOVE를 만들 수 있는지 , 만들 수 있다면 그 최솟값은 무엇인지 구하는 문제이다. 아이디어 : 우선, 주어진 재료들의 이름과 비용은 map을 사용해서 나타낼 수 있다. 조합식들은 항상 a=k1*m1+k2*m2+... 꼴로 나타낼 수 있으며 파싱을 잘 해서 {계수, 재료이름} 꼴로 나타낼 수 있다. M제한이 50이고, 모..
-
1047번 : 울타리알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 11:20
boj.kr/1047 1047번: 울타리 첫째 줄에 N이 주어진다. N은 2보다 크거나 같고, 40보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 나무가 심어져 있는 위치와 그 나무로 만들 수 있는 울타리의 길이가 순서대로 주어 www.acmicpc.net 아이디어 : 기준을 나무가 아닌, 울타리, 즉 직사각형에 초점을 맞추자. 직사각형은 가로선 2개와 세로선 2개로 만들 수 있고, 가로선 2개의 안쪽 영역과 세로선 2개의 안쪽 영역의 겹치는 부분이 곧 직사각형의 내부 영역이 된다. 가로 기준으로 나무(=점) 2개, 세로 기준으로 점 2개를 골라서 이 4개의 점이 이루는 직사각형을 먼저 구한다. 그 다음 직사각형에 포함되는 점들과 포함되지 않는 점들로 나눈다. 포함되지 않는 점들은 다 잘라놓고..
-
확장 유클리드 호제법 (EEA)알고리즘/알고리즘 이야기 2022. 1. 1. 17:45
유클리드 호제법에서는 최대공약수를 빠르게 찾을 수 있었다. int gcd(int a, int b){ if(b==0) return a; return gcd(b,a%b); } 이 때 나오는 최대공약수를 d라고 하자. gcd(a,b) 의 값이 d이다. 우리는 ax + by = d 가 되는 x와 y를 찾고 싶다. "베주 항등식"에 의하여 ax + by = d를 만족하는 x와 y가 무조건 있다. 유클리드 호제법의 과정을 나열해보자. gcd(a,b) => gcd(b,r2) => gcd(r2,r3) => gcd(r3,r4) ... 이런 과정으로 나아갈 것이다. 이 과정을 수식으로 나열 해보면, a = b * q0 + r2
-
내일 일기 - 내일을 시작하는 첫 발걸음 [2021국방오픈소스아카데미 해커톤 출품작]군대 이야기 2021. 10. 23. 20:27
개발 문서 및 전체적인 소개 : GitHub - osamhack2021/app_TomorrowDiary_TomorrowDiary: 내일 일기 내일 일기. Contribute to osamhack2021/app_TomorrowDiary_TomorrowDiary development by creating an account on GitHub. github.com 구글 플레이 링크 : 내일 일기 - 내일을 시작하는 첫 발걸음 - Google Play 앱 내일 일기 드디어 출시! 내일의 일기를 적고, 오늘의 일기를 완성하고, 목표에 달성하세요! play.google.com 개발 과정 및 후기 : 2021 국방오픈소스아카데미 해커톤 참여 후기(Feat. 싸지방에서 개발하기) 우선 나는 20년 10월 19일에 육군..