yevdev◡̈

문제 https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 처음 풀이 코드 (Numpy 라이브러리 이용) import numpy as np a, b, c, d, e, f = map(int, input().split()) A = np.array([[a,b],[d,e]]) B = np.array([c,f]) C = np.linalg.solve(A,B..

문제 https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 풀이코드 (Python) from collections import deque n, m = map(int,input().split()) input_arr = [0]*n for i in range(n): input_arr[i] = list(map(int, input().split())) output_arr = [0]*n for i in range(n)..

문제 https://www.acmicpc.net/problem/17362 17362번: 수학은 체육과목 입니다 2 첫 번째 줄에 19번 문제 세 번째 줄에 등장하는 수 '1000'을 자연수 n으로 바꾸었을 때 그에 해당하는 답의 번호를 출력한다. 즉, 1 이상 5 이하의 자연수 중 하나를 출력해야 한다. www.acmicpc.net 풀이 코드 (Python) n = input() n = int(n) rem = n % 8 if rem == 1: print(1) elif (rem == 2) or (rem == 0): print(2) elif (rem == 3) or (rem == 7): print(3) elif (rem == 4) or (rem == 6): print(4) else: print(5) 풀이 설..

문제 https://www.acmicpc.net/problem/22351 22351번: 수학은 체육과목 입니다 3 이환이의 선생님이 부른 두 정수 $A$와 $B$를 공백으로 구분하여 출력하라. 만약 가능한 답이 두 가지 이상이라면, 그중 $A$가 가장 작은 것을 출력하라. 이환이는 항상 정확한 답을 쓰기 때문에, www.acmicpc.net 풀이 (Python) from sys import stdin input = stdin.readline s = stdin.readline().strip() def solv(): if len(s) < 4: flag = True for i in range(1,len(s)): if s[0] != s[i]: flag = False break if flag: print(s, s..

https://www.acmicpc.net/problem/22354 22354번: 돌 가져가기 처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다. www.acmicpc.net 사실,, 해결 못했다,,, 몇시간을 풀어보고 결국 마지막에 구글링을 했는데,, 다른 사람들도 내가 푼 방식대로 한거 같은데 왜 안되는거야..!!! 일단 내가 푼 코드는 아래와 같다. N = int(input()) array = list(input()) scores = list(map(int, input().split())) result = 0 def funcMax(i, j): if i > j: retu..

백준의 좌표압축(18870)번 문제를 풀다가 시간초과로 한참 고민함 .. ㅠㅠ 문제는 생각보다 쉬웠다. 해결방법은 1. 입력받을 숫자개수(n)을 입력받고, 2. n개 만큼의 숫자를 list로 받은 후, 3. set으로 중복을 제거하고, 4. sort함수로 정렬한 후, 5. 기존 list로 입력받은 숫자 배열과 sort 함수로 정렬된 배열을 비교하여 index를 출력하면 된다고 생각했다. 근데, 여기서 시간초과가 발생한 것은 "기존 list로 입력받은 숫자 배열과 sort 함수로 정렬된 배열을 비교하여 index를 출력" 하는 부분이었다. 원하는 값의 index를 출력하는 index()함수의 시간 복잡도는 배열의 원소 하나하나를 따져야하기 때문에 O(n)의 시간복잡도를 갖는다. 따라서, 배열의 원소들을 각..

지난번 NP-완전 문제 (1) 포스팅에 이어서 계속한다. 저번 포스팅에서는 결정문제까지 다루었는데, 이번 포스팅에서 다룰 건 아래와 같다. NP-완전(NP-Complete, NP-완비) 문제를 이해하기 NP-완전 증명 방법을 이해하기 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합 NP-완전이라는 사실이 판명됨으로써 얻을 수 있는 이득을 이해하기 음 일단 그전에! P와 NP 문제를 이해해보자 1️⃣ 문제의 분류 ( P와 NP ) P : 다항식 시간복잡도를 가진 알고리즘으로 해결되는 (polynomial) 문제 집합 [결정문제 관점에서] 결정 문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합. 다항식 시간에 Yes 또는 No 대답을 할 수 있는 문제 전산학자들이 제안한 '풀기 쉬운' 문제의..

NP-완전 이론 : 문제를 현실적인 시간에 풀 수 있는가에 관한 이론 복잡한 문제가 주어졌을 때, 고민할 것 답이 존재? 어떻게 답을 찾는가? 찾은 것이 올바른지 어떻게 검증? 쉬운문제 / 답은 구하는데 시간이 짧은 문제 어려운 문제 / 답을 구하는데 시간이 오래 걸리는 문제 풀 수 없는 문제 / 너무 어려워서 풀리지 않는 문제 아리송한 문제 / 어떤 집단 문제들은 어려워 보이기는 하지만, 그 답을 보면 옳다는 것을 검증하기가 쉬운 그러한 집단 문제 예) 퍼즐 맞추기 : 모나리자를 500조각 낸 퍼즐을 구입하여 짝을 맞추는 문제 : 문제를 푸는 것은 어렵지만, 답을 보고는 그것이 옳다는 것을 판정하는데 500 조각만 조사하면 됨으로 검증하기 쉽다. 이번 포스팅에서 다룰 것. 문제의 난이도 "다루기 힘든 ..

Miller-Rabin Primality Test : 밀러-라빈 소수판별법 임의의 수 a가 소수인지 아닌지를 확률적으로 판별해주는 알고리즘 이 알고리즘은 주어진 수 a이 소수임을 증명하지 않고, 소수가 아닐 확률(여사건)을 분석하여 소수를 판별함. 왜 확률적인가? a가 큰수이고, 소수 판별을 위해 먼저 2로 나누어 떨어지지 않는다고 가정한다면, 2, 4, 6, 8 등의 2의 배수인 수로도 나누어 떨어지지 않는다. 즉 이 수들에 대해서 검사할 필요가 없다. -> 전체 자연수에 대해서 50%의 숫자들을 검사한 효과! a가 3으로 나누어 떨어지지 않는다면 6, 9, 12 등의 수에 대해서도 검사할 필요가 없다. -> 전체 자연수에 대해서 33%의 숫자들을 검사한 효과 a가 5로 나누어 떨어지지 않는다면, 10..

기수정렬? 데이터끼리의 직접적인 비교 정렬이 아닌, 숫자를 부분적으로 비교하는 정렬방법 제한적인 범위 내에 있는 숫자에 대해서 낮은 자릿수부터 자릿수 별로 비교 정렬하는 알고리즘 어느 비교 정렬 알고리즘보다 빠른 큰 장점!! 기 (Radix)? 특정진수를 나타내는 숫자들 10진수의 기 : 0,1,2,3,4,5,6,7,8,9 2진수의 기: 0,1 🚫주의할 점 10의 자리가 같을 때 왜 035가 131 위에 위치하면 안되는 것인가? -> 1의 자리에 대해 정렬해 놓은 것이 아무 소용이 없게 되기 때문이다. ❗️정렬알고리즘은 안정성을 가진다. 입력에 중복된 숫자가 있을 때, 정렬된 후에도 중복된 숫자의 순서가 입력에서의 순서와 동일하다. 💡RadixSort 알고리즘 (의사코드) 입력 : n개의 r진수의 k자리..