주발이의 개발새발

1. 문제 1834번: 나머지와 몫이 같은 수 N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다. www.acmicpc.net 2. 코드 using System; class BJ1834 { static void Main() { long n = long.Parse(Console.ReadLine()); long sum = ((n * n * n) - n) / 2; Console.WriteLine(sum); } } 3. 풀이 간단한 수학 문제이다. 그러나 여기서 가장 중요한 것은 바로 형(type) 처음 int로 입력을 받고 입력값을 2,000,000으로 입력했을 때 ..

1) 문제 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 2) 코드 using System; using System.IO; class Multi { static void Main() { int count = Int32.Parse(Console.ReadLine()); //C#에서 숫자 리스트 입력받기 string input = Console.ReadLine(); string[] factorsStr = input.Split(' '); int[] factors = new int[count]; for(int..

1. 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 2. 풀이 ⏰ 시간 초과 : 단순하게 생각해서 if문과 in을 사용하여 확인하였다. 역시나 시간 초과 .. ✔️ 이분 탐색 : 시간초과가 나지 않게 빨리 찾을 수 있는 것은 역시나 '이분탐색'이다 ! 3. 코드 # 1920 def binary_search(target, data): start = 0 end = len(data) - 1 wh..

1. 문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 어렵지 않은 실버5 문제였으나 그리디 알고리즘을 복기하기에 좋은 것 같아 포스팅 해본다 ! 2. 풀이 그리디는 정말 간단하게 생각해보는게 답인 것 같다. 우선 받을 수 있는 거스름돈의 동전은 2, 5원이다. 그렇다면 1,3,..등 2,5로만 이루어지지 않는 수는 -1을 출력해주어야한다. 1) 우선 5로 나누어보고 5로 나누어떨어지지 않는다면 2) 2를 감해준다. 그리고다시 1)번으로 되돌아간다. 1) - 2)를 반복해주고 n이 0보다 작다면 불가능한 경우인(-1)을 출력해주고, n==0으로 나누어떨어진다면 답인 (ans)를 출력해준다 ! 3. 코드 n = int(input..

1. 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제를 보고 막막했다. 지금껏 풀었던 그래프 문제는 주로 방향이 우,하 로 잡혀있었는데 이 문제에서는 상하좌우를 따져주어야했다. 다른 코드를 조금 (많이) 참고했다 ^ ____ ^ .. 그리구 상하좌우를 탐색하는 방법을 알았다 !! 2. 풀이 1) 그래프(미로(0,0))에서 bfs함수를 사용하여 상,하,좌,우 를 모두 검사하고 1인 값을 찾는다 2-1 ) 1이라면 그 전 값 +1 2-2 ) 0이라면 continue 3) 차근차근 모든 미로를 탐색하며 목적지(miros[n-1][m-1..

1. 문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2. 코드 n = int(input()) # 노드 개수 size = int(input()) # n번 노드에 연결된 노드 graph = [[] for _ in range(n+1)] # 방문한 노드는 1, 방문하지 않은 노드는 0 visited =[0]*(n+1) for i in range(size): a,b = map(int,input().split()) # 그래프 넣어주기 ~ graph[a]+=[b] graph[b]+=[a] def dfs(v): # 방문한..

1. 문제 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 2. 해결방법 정렬해서 주어진 배열, 처음과 마지막에서 점점 좁혀들어오는 방식으로 푸는 문제인 점을 고려하여 투포인터 알고리즘을 사용하니 쉽게 해결되었다 ! 우선 투포인터까지 구현은 어렵지 않았으나 .. '특성값이 0에 가까운 용액을 만들어내는 두 용액의 특성값'을 구하는 것이 난관이었다. 생각을 해보잣 ... ! (1) 새로운 리스트를 만들어서 투포인터로 돌면서 (start,end)값을 넣어준 뒤 min(abs(start,end의 두용액의 특성..

1. 문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 2. 해결방법 코알라 강의를 듣고난 후 푼 문제이다. 사실상 해결방안을 미리 알고 푼 문제 .. - 처음엔 누적합을 이용해보았다. obstacle이라는 배열을 두고 장애물을 모두 받은 뒤, imos배열에 (imos방식은 아닌데 왜 배열이름이 imos인가에 대해서는 너그럽게 양해해주시길 바란다.. ) 높이가 i일 때 obstacle이 몇개인지를 각각 알아보았지만 시간초과 ! - 이제 imos..

1. 문제 9417번: 최대 GCD 첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 www.acmicpc.net 2. 해결방법 - 문제에서 큰 힌트를 직접 주었다. GCD 알고리즘을 이용하자 ! - 우선 우리가 구해야할 값은 두 쌍의 GCD의 최댓값이다. 각 테스트 케이스에서 주어진 수 중 2쌍씩 묶자 → 2중 for 문을 사용하고 중복은 제거해주었다. 묶은 2쌍들의 최대 공약수(GCD)를 구한 뒤 →유클리드 알고리즘 최댓값을 출력 ! 3. 코드 n = int(input()) numList = [list(map(int,i..

1. 문제 6219번: 소수의 자격 세 정수 A, B, D가 주어진다. www.acmicpc.net 2. 해결방법 N의 크기가 작았기에 에라토스테네스의 체 알고리즘을 사용하였다. [ 알고리즘/ Python ] 소수 구하기 : 에라토스테네스의 체 코테, 백준 문제를 풀다보면 '소수'를 구하는 문제가 꽤나 나온다. 소수를 사람의 손으로 풀기에는 다소 어려움이 있을 수 있다. 2,3,5,7 .. 정도는 괜찮지만 컴퓨터 암호화에 사용되는 아주 큰 소 0lrlokr.tistory.com 3. 코드 A = [False, False] + [True]*4000000 for i in range(2, 4000000): if A[i]: for j in range(i+i,4000000, i ): A[j] = False a,b..