주발이의 개발새발

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..

크루스컬 알고리즘이란 * 신장 트리 : 하나의 그래프가 있을 때, 모든 노드를 탐색하면서 사이클은 존재하지 않는 트리 ** 최소 신장 트리 : 그래프 G에서 노드 v를 포함하는 E에 속하는 Edge를 사용하여 만든 트리(신장트리)에서 가중치의 합이 가장 작도록 하는 트, 즉 최소비용으로 만들 수 있는 신장 트리 크루스컬 알고리즘을 배우는데 왜 갑자기 신장트리가 나오는가 .. 에 대한 의문이 있으셨을 것이다. 왜 나온고하니 .. 최소 신장 트리를 찾는 대표적인 알고리즘이 바로 크루스컬알고리즘 ! 그리디 알고리즘에 속하며 순환 시, 사이클이 만들어지지 않도록 가중치가 가장 적은 간선을 선택하며 업데이트 된다 ~ 크루스컬 알고리즘 동작원리 1. 간선 데이터를 비용에 따라 오름차순 정렬 2. 간선을 하나씩 확인..

모의 코딩 테스트 .. 를 쳤다 .. 컨셉 : 카카오 코딩 테스트 (문자열 파싱 등) 난이도 : 실제 코딩테스트의 80~90% 정도 난이도와 컨셉은 이런느낌 3시간동안 10문제중 4문제를 해결했다 .. .. ㅜ - 우선 시간 잡고 푸는 연습을 해서 좋았다.. 그리고 한 문제 한 문제 토의하는 시간까지 !! 알찬 .. 시간이었다 .. 오늘은 비도 오고 나가기 싫어서 느적거리다가 집에서 좌식테이블에 앉아서 쳤는데 .. 다음부터는 준비 일찍 해서 약간의 긴장감 가지고 집중해서 풀어야겠다 !! - 문제 난이도를 가리고 시험을 쳐봤다. 약간 긴장된다.. 문제를 해결하고 나면 난이도가 보이는데 체감 난이도보다 훨씬 낮았다 (= 쉬운 문젠데 어렵게 보임 ) 1번 3004번: 체스판 조각 상근이는 3003번에서 동혁이..

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): # 방문한..

CCW 알고리즘이란 ? Counter Clockwise의 약자로 세 점의 방향성을 구하는 알고리즘이다! 즉, 평면상에 존재하는 세 점에 대해서 위치 관계를 알 수 있는 알고리즘임 ~ 결론만 먼저 말해보자면 세 점 A(x1,y1), B(x2, y2), C(x3, y3)이 주어졌을 때 , 점 A,B,C를 순서대로 봤을 때 반시계 방향이면 양수를, 시계 방향이면 음수를, 직선상에 있으면 0을 반환한다. CCW 공식 : (Bx-Ax) * (Cy-Ay) - (Cx-Ax) * (By-Ay) 벡터의 외적(Cross product) CCW 알고리즘에 관한 증명 기하 알고리즘에서 필수적으로 알아야한다는 기초적인 개념인 외적, 열심히 배워보고 까먹지 않도록 하자 ~ 이 경우에서 점 C는 선분 AB의 반시계방향에 위치하고 ..

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