본문 바로가기

알고리즘

 (368)
[Python] 3533번 Explicit Formula https://www.acmicpc.net/problem/3533 3533번: Explicit Formula Consider 10 Boolean variables x1, x2, x3, x4, x5, x6, x7, x8, x9, and x10. Consider all pairs and triplets of distinct variables among these ten. (There are 45 pairs and 120 triplets.) Count the number of pairs and triplets that contain at least one variab www.acmicpc.net 22/08/27 오늘은 좀 바빠서 브론즈 한 문제만 풀고 넘기려고 했다. 근데 왠걸, 브론즈 3 문제 치고는 비주얼..
[Python] 1654번 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 22/08/26 클래스 2 문제 중 안 푼 문제가 있길래 푼 문제이다. 전형적인 이분탐색 문제이고, 이분탐색 문제 특성상 범위나 종료 조건을 잘못 설정하면 맞왜틀을 하기 쉽기 때문에 나도 맞왜틀을 여러 번 했다. 당연히 이분탐색이 무엇인지 알고 있다는 전제 하에서 글이 쓰여있으므로, 풀이를 참고할 생각이 있다면 이분 탐색기법을 알아야 할 것이다. 문제 접근 방법: 기존..
[Python] 1699번 제곱수의 합 / 17626번 Four Squares https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 22/08/..
CCW 알고리즘(CCW Algorithm) 최근에 배우게 된 CCW 알고리즘에 대해 글을 써보고자 한다. CCW 알고리즘이란? Counter-ClockWise의 줄임말로, 직역하면 반시계 방향이라는 뜻임. 세 점 p1, p2, p3가 주어져 있고, 이 세 점을 p1, p2, p3 순서대로 직선으로 이었을 때, 시계방향으로 휘어지는가, 반시계 방향으로 휘어지는가, 혹은 일직선을 이루는가를 판별하는 알고리즘. 방향이 중요하기 때문에 벡터의 개념을 알아야 함. 이 알고리즘을 활용하여 다양한 기하학 알고리즘에 적용할 수 있음. 대표적으로 선분 교차 판정 알고리즘, 볼록 껍질 알고리즘(컨벡스 헐) 등이 있음. 요약된 내용으로만 보아서는 무슨 뜻인지 잘 모를 수도 있을 것이다. 그래서 다음과 같이 그림을 준비했다. 위의 그림처럼 세 점 P1, P2, P3를..
[Python] 2013번 선그리기 https://www.acmicpc.net/problem/2013 2013번: 선그리기 첫째 줄에 선분의 개수 N(1 p2[0]: return p1 elif p1[0] = p2[1]: return p1 else: return p2 def point_swap(p1, p2): if point_compare(p1, p2) == p1: return p2, p1 else: return p1, p2 def line_swap(p1, p2, p3, p4): if point_compare(p1, p3) == p1: return p3, p4, p1, p2 else: return p1, p2, p3, p4 def can_draw_once(line1, line2)..
[Python] 21650번 Чемпионат по стрельбе https://www.acmicpc.net/problem/21650 21650번: Чемпионат по стрельбе Победитель школьного этапа олимпиады по информатике нашел дома в старых бумагах результаты чемпионата страны по стрельбе из лука, в которо www.acmicpc.net 22/08/24 이 문제 또한 실버 랜덤 디펜스를 하다가 만나게 된 문제이다. 어떻게 보면 언어의 장벽이 제일 크게 느껴졌던 문제였다. 잘못 해석하고, 실수해서 9번이나 틀렸습니다! 를 받았으니깐 말이다. 이 문제를 통해 얻은 점은 러시아어 문제를 풀 때는 영어로 한번 중역을 해야 자연스럽게 번역이 된다는 사실이..
[Python] 3199번 ABCD https://www.acmicpc.net/problem/3199 3199번: ABCD 정찰 부대가 지금 막 새로운 보고를 보내왔습니다. 그 보고의 내용은 바로, ABCD(Atomic Beryllium-Cesium Destroyer)라는, 이름만 들어도 소름이 끼치는 병기가 테러리스트들에게 넘어갔다는 것입니다. ABCD www.acmicpc.net 22/08/24 실버 랜덤 디펜스를 하다가 만난 문제. 전형적인 기하학 문제이다. 문제 요약: 직사각형의 넓이를 최소화하는 문제인데, 직사각형의 각 꼭짓점은 4개의 평행선 위에 놓여야 한다. 각 평행선 사이의 거리는 순서대로 p, q, r이다. 만약 직사각형을 만들 수 없으면 0을 출력, 만들 수 있으면 그 직사각형의 최솟값을 소수점 4자리까지 출력하면 된다...
[Python] 4411번 The Trip https://www.acmicpc.net/problem/4411 4411번: The Trip Standard input will contain the information for several trips. The information for each trip consists of a line containing a positive integer, n, the number of students on the trip, followed by n lines of input, each containing the amount, in dollars and c www.acmicpc.net 22/08/24 실버 랜덤 디펜스를 하던 도중 만난 문제이다. 문제에서 요구하는 사항은 다음과 같다. 문제 요약: 학생들이 여행을..

티스토리툴바