아는게 없어서 쓰는 블로그 아는게 없어서 쓰는 블로그

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의 두용액의 특성..

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

코테, 백준 문제를 풀다보면 '소수'를 구하는 문제가 꽤나 나온다. 소수를 사람의 손으로 풀기에는 다소 어려움이 있을 수 있다. 2,3,5,7 .. 정도는 괜찮지만 컴퓨터 암호화에 사용되는 아주 큰 소수는 판별하기 어렵다. 그럼 컴퓨터에게 이 소수를 구하라고 시키는 프로그램을 작성해보자 ~ 1. 소수 1과 그 수 이외의 자연수로는 나눌 수 없는 자연수 소수는 2,3,5,7...에서 볼 수 있듯 약수가 2개라는 특징을 가진다. 이러한 특징 때문에 1은 소수가 될 수 없다. import math n = int(input()) def isPrime(n): if n

1. 문제 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 해결 사실 해결 방법은 단순했다. - DP를 사용해자. - [ 알고리즘 ] 다이나믹 프로그래밍(DP) - 개념 - 문제에서 '구하라는 값'에 집중하자 → 나머지 값을 메모이제이션에 넣어보자 ~ 3. 코드 n = int(input()) dp= [0,1,1] for i in range(3,n+1): dp.append((dp[i-1]+dp[i-2])%1000000007) print(dp[n]) 4. 잊지말자 많이 헤멨던 문제다. DP를 배우기 전 그냥 재귀호출로만 풀다가 시간초과, 런타임 에러를 띄우고.. DP를 배우고 다시 돌아왔다. 하지만 메모리 ..

1. 다이나믹 프로그래밍(DP)이란 ? 큰 문제를 작은 문제로 나누어 푸는 알고리즘 다이나믹 프로그래밍, 동적계획법은 문제를 어떤 형태로 변형시켜 쉽게 푸는 방법을 의미한다. * 여담이지만 '동적(Dynamic)'은 멋있어보여서 붙은 이름이라고 한다. 처음에 이 사실을 모르고 Dynamic에 집중해서 이 알고리즘을 보았는데 .. 계속 어느 부분이 동적으로 작동한다는 거지? 라고 생각했었다. 이 사실을 알고 나서는 '계획법'을 집중해서 보게 되었다.. ! 2. DP의 2가지 필수 조건 1) Overlapping Subproblem 같은 문제는 항상(구할 때 마다) 정답이 같다. 큰 문제가 작은 문제로 세분화될 수 있고, 같은 방법으로 풀릴 때 ex. 피보나치 수 - Fib(n-1) = Fib(n-2) + ..