깨발랄 개발자 성장기

🔗 문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP의 가장 기초적인 문제 중 하나이다. 어찌저찌 풀긴 했으나, 확실하게 짚고 넘어가기 위해 다양한 코드들을 살펴보고 이것들을 정리해 보도록 하겠다. 🔎 문제 풀이 & 작성 코드 주어진 수를 3으로 나누거나, 2로 나누거나, 1로 빼는 연산을 반복하면서 1로 만들 수 있는 최소한의 연산의 횟수를 구하면 된다. 가장 적은 횟수로 만들려면 무작정 3으로 나눠보고, 안 나눠지면 2로 나눠보고, 그것조차 안될 때는 1로 빼는 식으로 계산하면 문제를 해결할 수 없다. 문제에서도 주어진 예시인데 10에 대해..

🔗 문제 링크 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 이름 그대로 약수의 합을 구하는 문제이지만! 수학적인 계산을 사용해야 제대로 풀 수 있는 문제이다. 🔎 문제 풀이 & 작성 코드 문제에서 자연수 A가 있을 때, 이 자연수의 모든 약수를 더한 값을 f(A)로 표현하였다. 또한, x라는 자연수가 주어졌을 때 x보다 작거나 같은 모든 자연수 y(1~x까지)의 f(y)값을 모..

🔗 문제 링크 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수와 최소공배수를 구하는 문제이다. 나는 단순 구현으로 풀었는데 풀이를 찾아보니 유클리드 호제법을 사용하면 훨씬 간단하게 풀 수 있다! 머리가 무식하면 몸이 고생한다는 걸 체감했다... 🔎 문제 풀이 & 작성 코드 나는 최대공약수와 최소공배수의 정의에 입각해서 코드를 작성하였다. 두 수가 주어졌을 때 최대공약수는 두 수의 공통된 소인수들의 곱이고, 최소공배수는 두 수들의 공통된 배수중에 가장 작은 수이다. 최소공배수를 그래서 최대공약수는 gr..

🔗 문제 링크 https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 문제는 굉장히 단순하다. 축과 평행한 직사각형의 세 점이 주어졌을 때, 나머지 한 점을 찾는 코드를 작성하면 된다. 🔎 문제 풀이 & 작성 코드 직사각형의 기초적인 정의를 따라 코드를 구현했다. 네 점은 (x1, y1), (x1, y2), (x2, y1), (x2, y2)으로, 각각 2개의 x좌표와 2개의 y좌표가 반복된다. 그래서 세 점의 좌표를 x좌표와 y좌표로 구분하여 모두 모은 다음, 한 개만 입력된 좌표를 아직 입력되지 않은 나머지 한쌍을 찾아낼 수 있도..

🔗 문제 링크 https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 주어진 단어에 대해 모든 알파벳이 처음 나온 위치를 찾는 문제이다. 문제 자체는 어렵지 않지만, 나는 일일이 구현했는데 다른 사람의 풀이를 보니 더 나은 코드가 많아서 한 번에 정리해보려고 한다. 🔎 문제 풀이 & 작성 코드 나는 문제에 충실하게 직접 다 구현해냈다. 모든 알파벳에 대해 -1을 갖는 딕셔너리를 선언해 주고, 주어진 단어를 일일이 탐색해 처음 나온 자릿수로..

🔗 문제 링크 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 처음 봤을 때는 문제가 굉장히 복잡해 보였는데 규칙을 찾고 나면 어렵지 않게 해결할 수 있는 문제인 듯하다! 이런 수학 + 구현 문제는 해결 방식을 떠올리는 게 제일 복잡한 것 같다 ㅇ0ㅇ 🔎 문제 풀이 & 작성 코드 이 문제에서는 위의 화살표를 따라가며 N번째 분수를 찾아내야 한다. 내가 생각한 이 문제의 규칙성은 이렇다. 초록색 화살표로 내려가는 것과 주황색 화살표를 따라 올라오면서 이동하기 때문에, 이 특징을 가지고 알고리즘을 작성하였다. 1/1부터 시작되는 주황선은 1,3,5,...번째인 홀수 라인들이라고 ..

🔗 문제 링크 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 상근이가 가진 숫자 카드와 새로 주어진 숫자 카드를 비교해서 새로 주어진 숫자 카드들을 상근이가 가지고 있는지 구하는 문제이다. 문제를 풀고 구글링 해보니까 대부분 이분 탐색으로 풀었는데, 나는 단순 탐색으로 풀었다. 🔎 문제 풀이 & 작성 코드 숫자 카드가 중복되지 않는다는 특징을 이용해서, 단순하게 카드의 범위 전체에 대한 리스트를 생성했다. 원래 ..