맞았습니다!!

20149 선분 교차 3 (백준, python3)

2024.03.03·

PS/BOJ

시간 제한메모리 제한0.25초512MB문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다. 두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다. 좌표의 절대/상대..

31434 당근 클릭 게임 (백준, python3)

2024.02.26·

PS/BOJ

시간 제한메모리 제한2초1024MB문제에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다. 이 게임에서 초기에 에릭은 당근을 0개 가지고 있고, s가 1인 상태로 게임을 시작한다.그 후, 매초 다음 두 가지의 행동 중 하나를 할 수 있다.마우스를 클릭하고 당근을 s개 얻는다.정수 i (1 ≤ i ≤ N)를 고르고, 당근 Ai개를 지불하여 i번째 스피드 효과를 구매한다. 구매 직후, s가 Bi만큼 증가한다. (이전에 구매한 스피드 효과를 다시 구매하는 것도 가능하다.)게임을 개발하느라 에너지를 모두 소모해 버린 에릭을 위해 게임을 K초 플레이한 후 당근을 최대 몇 개까지 가지고 있을 수 있는지 알려주자!입력첫 번째 줄에 두 정수 N, K가 공백으로 구분되어 ..

선분의 교차 판정

2024.02.22·

PS/Algorithm

선분은 직선 상의 두 점과 그 두 점 사이의 점들로 구성되는 유한인 직선의 부분이다. 간단히 두 점을 잇는 최단거리다. 샤프심 두 개를 책상에 쏟았다. 샤프심을 선분이라고 봤을 때 이 두 가닥의 샤프심의 위치관계를 몇 가지로 나누어 설명할 수 있을까. 우선 두 샤프심이 서로 닿은 경우와 닿지 않은 경우가 있을 것이다. 그리고 닿은 경우에는 겹친 경우도 있을 것이다. 닿지 않은 경우도 나란히 놓여서 샤프심의 길이가 무한히 늘어나도 닿지 않는 특수한 경우와 그렇지 않은 경우로 나눌 수 있다. 1. 벡터의 외적 벡터는 고등수학에 따르면 크기와 방향을 가진 물리량을 의미한다. 쉽게 생각하면 화살표로 볼 수 있다. 길이도 있고 방향도 있다. 선분끼리는 더하거나 뺀다는 연산을 길이만 두고 할 수 있으나 벡터는 방향..

분리 집합(Disjoint set)과 유니온 파인드(Union-Find)

2024.02.12·

PS/Algorithm

분리 집합은 두 집합의 관계르 나타내는 것으로 두 집합 A와 B의 교집합이 공집합일 때 A와 B는 분리 집합이라고 한다. 집합의 요소를 놓고 요소들이 포함된 집합이 같은 집합인지 분리 집합인지 확인하고, 두 분리 집합을 하나로 병합하는 알고리즘을 유니온 파인드라고 한다. 1. 분리 집합(Disjoint set) 두 집합 A = {1, 2, 3, 4, 5}와 B = {5, 6, 7, 8, 9}는 '5'를 공통 원소로 갖는다. 이 경우 A, B는 분리 집합이 아니다. 집합 C = {10, 11, 12, 13, 14}가 있을 때, A∪B와 C는 공통 원소가 없는 분리 집합이다. A와 C도 분리 집합이고 B와 C도 분리 집합이다. 여러 정점을 놓고 간선으로 연결한 상태가 주어졌을 때, 정점과 간선을 거쳐 연결된..

2618 경찰차 (백준, python3)

2024.02.08·

PS/BOJ

시간 제한메모리 제한1초128MB문제어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 ..

최장 증가 부분 수열(LIS, longest increasing subsequence)

2024.01.26·

PS/Algorithm

최장 증가 부분 수열 - 나무위키 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. namu.wiki 1. 최장 증가 부분 수열(LIS) LIS 문제를 처음 봤을 때 만능 문제해결 툴 브루트포스를 떠올렸는데 당연히 죽음뿐. LIS 문제의 정해는 보통 두 가지다. O(N2)으로 해결할 수 있는 다이나믹 프로그래밍, O(NlogN)으로 해결할 수 있는 이진 탐색이다. 여기서 또 이진 탐색 해법이 있다는 걸 처음 알았을 때는 "대체 이게 뭔소리냐" 싶었는데 잘 살펴보고 직접 구현해보면 그렇게 어려운 개념은 아니다. 하지만 이 문제를 이미 몇 년 전에 처음 접해서 풀었던 ..

슬라이딩 윈도우(Sliding window)

2024.01.25·

PS/Algorithm

1. 투 포인터(Two pointer)와 슬라이딩 윈도우 리스트에서 데이터에 접근할 때 한 방향으로 탐색하는 선형탐색은 매우 간단하지만 리스트의 크기가 커지게 되면 효율적이지 않다는 문제가 있다. 이를 극복할 수 있는 이진 탐색, 매개변수 탐색 등 다양한 탐색 알고리즘이 있다. 그 중, 두 개의 포인터를 이용해 범위를 좁히거나 이동시키며 탐색하는 방법을 투 포인터라고 한다. 슬라이딩 윈도우는 투 포인터 문제의 특수한 경우로, 두 포인터의 간격이 일정하게 유지되며 이동하는 문제 해결 방법이다. 두 포인터가 움직이는 것이 마치 창틀에 고정된 창문이 움직이는 것과 같아 슬라이딩 윈도우라는 이름이 붙었다. 2. 구현 슬라이딩 윈도우는 간단하게 구현할 수 있다. 두 개의 포인터를 지정하고 한 구간의 탐색을 끝내면..

볼록다각형(Convex)의 넓이 구하기

2024.01.17·

PS/Algorithm

얼마전 볼록껍질 문제를 해결하고 기하 문제에 관심이 생겨 백준 1077번 넓이 문제에 도전해봤다. 새로 배워야 할 개념이 많았는데 넓이를 구하는 기초적인 아이디어를 잘 구현해낸 것 같아 정리해보고자 한다. 1. 볼록다각형의 정의 이 문제를 연구하다가 새로 알게된 사실이다. 볼록다각형은 이웃하지 않는 두 점을 이은 선분이 도형 내부에 존재하는 단순다각형을 말한다. 단순다각형은 다각형을 이루는 변들이 서로 교차하지 않는 다각형을 말한다. 볼록 집합이라는 것도 있는데, 집합 내에서 어떤 두 점을 선택해도 선분이 집합 내부에 그려지게 되는 집합을 말한다. 볼록다각형은 볼록 집합을 이루는 단순다각형이기도 하다. 엄밀한 볼록다각형은 모든 내각의 크기가 180도 미만이어야 한다. 어떤 문제들은 이 조건을 명시하지만 ..

볼록껍질 문제(Convex Hull), 그라함 스캔(Graham's scan)

2024.01.11·

PS/Algorithm

여러 객체가 주어졌을 때, 객체를 둘러싸는 껍질을 만드는 문제다. 적용되는 가장 직관적인 현상은 고무줄이다. 몇 개의 못을 박아두고 못을 전부 안쪽으로 감싸도록 고무줄을 걸어주면 고무줄이 만든 도형이 볼록껍질이 된다. 1. 문제상황 볼록껍질을 만드는 문제상황을 아래 그림을 예시로 생각해 보자. 평면상에 10개의 좌표가 주어져있고 이 점들을 감싸는 최소 면적의 볼록 다각형을 구성하는 점을 특정하는 것이 이 문제의 해가 된다. 해를 구할 수 있는 방법은 모든 점을 방문하며 확인해보는 방법도 있겠으나, 가장 널리 알려진 것은 O(NlogN)의 시간복잡도를 가진 그라함 스캔(Graham's scan)이다. 2. CCW(Counter Clock Wise) 알고리즘 그라함 스캔 알고리즘을 수행하기 위해서는 두 점으..

31002 그래프 변환 (백준, python3)

2023.12.30·

PS/BOJ

시간 제한메모리 제한1초1024MB문제그래프의 변환(f:g↦g′)을 다음과 같이 정의한다. G의 간선을 G'의 정점으로 보고 G의 인접한 간선끼리 G'에서 간선으로 연결하여 G에서 인접하였음을 나타낸다. 서로 다른 두 간선이 같은 정점을 하나 이상 공유하면 두 간선이 인접한다고 표현한다. 다음은 그래프 변환의 예시 중 하나이다. 그리고 변환한 그래프를 다시 변환하는 것도 가능하다. N-완전 그래프를 K번 변환한 그래프의 정점이 몇 개인지 구하시오. N-완전 그래프는 정점이 N개인 그래프에서 서로 다른 두 정점에 대해 반드시 간선이 존재하는 그래프이다.입력첫째 줄에 정수 N, K가 공백을 사이에 두고 주어진다. (3 ≤ N ≤ 100,000, 0 ≤ K ≤ 100,000) 출력 K번 변환한 그래프의 정..

1052 물병 (백준, python3)

2023.12.28·

PS/BOJ

시간 제한메모리 제한1초512MB문제지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다. 물은 다음과 같이 재분배 한다. 먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다. 이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 ..

비트로 부분집합 표현하기(비트마스크, Bitmask)

2023.12.21·

PS/Algorithm

경우의 수를 나타낼 수 있는 다양한 방법이 있다. 비트마스크는 원소를 선택하는 경우와 선택하지 않는 경우 둘로 나뉘는 문제에 유용하게 활용할 수 있는 방법이다. 1. 비트마스크 마스크는 두 값을 합쳐 and, or, nor등의 연산을 수행하는 것으로, 이를 비트 연산에 적용한 것이 비트마스트다. 비트는 컴퓨터 연산의 최소 단위이므로 연산 과정에 다른 변환이 불필요하기 때문에 매우 빠른 속도를 갖는다는 장점이 있다. 비트마스크를 적용할 수 있는 문제라면 수행 시간, 메모리 면에서 큰 이점이 있다. 2. 비트 연산자 and, or, xor, nor, nand 연산자는 두 개의 비트를 입력으로 받아 하나의 비트를 출력으로 내놓는다. 두 비트에 대해 각 연산자 별 출력은 다음과 같다. a b and or xor..

티스토리툴바