https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net # 조건 수직선 위에 N개의 좌표 X1, X2, ... Xn Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. 1

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net # 조건 2xN 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램 작성 방법의 수를 10,007로 나눈 나머지를 출력하라. # 접근 방법 규칙을 찾는 것이 좋을 것 같다. n = 1 인 경우 1가지 n = 2 인 경우 2가지 n = 3 인 경우 3가지 n = 4 인 경우 5가지 n = 5 인 경우 8가지 f(n) = f(n-2) * 2 + f(n-3) 으로 구할 수 있다. 또는 f(n) = ..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net # 조건 방향 없는 그래프가 주어질 때, 연결 요소의 개수를 구하라 1

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net # 조건 여러 개의 정사각형 칸들은 하얀색이나 파란색으로 칠해져있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들자. 전체 종이 크기 NxN(N = 2^k) 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 크기가 똑같은 N/2 x N/2 크기의 색종이로 나눈다. 파란색이..

이분 탐색(Binary Search) 문제들 중 최적화를 위해 결정 문제로 바꿔서 푸는 매개 변수 탐색 문제가 있다. 앞에서 많이 살펴 봤지만 이분 탐색에 대해 간단히 복습해보자. 목차 이분 탐색 LOWER, UPPER BOUND 매개변수 탐색 1. 이분 탐색 정렬된 배열에서 사용 가능한 알고리즘 시작, 끝, 중간점을 이용해 탐색 범위를 절반씩 좁혀가며 탐색한다. target data와 middle data 값을 반복적으로 비교하여 원하는 데이터를 찾는다. 예 - 4를 찾는 과정 # 참고 https://velog.io/@guswns3371/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%A7%A4%EA%B0%9C-%EB%B3%80%EC%88%98-%ED%83%90%EC%83%8..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net # 조건 N x N 크기의 행렬로 표현되는 종이 -1, 0, 1 중 하나가 저장 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용 위의 경우가 아닌 경우 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘리 종이에 대해서 위의 과정을 반복 -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하라 N(1 일치한다면 넘어가고 불일치시 9..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net # 조건 듣지도 못한 사람의 명단 보지도 못한 사람의 명단이 주어질 때 듣지도 보지도 못한 사람의 명단을 구하라 N, M

https://www.acmicpc.net/problem/1697 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net # 조건 수빈이는 현재 점 N(0= k: return n - k elif k == 1: return 1 # 홀수인경우 도착지점+1, 도착지점 -1만 탐색하며 +1 해준다. elif k % 2: return min (find(n, k + 1), find(n, k - 1)) +1 # 짝수인 경우 시작점-도착점, k//2+1 중 최소값으로 갱신해준다. # 또한 k//2 로 이동하여 출발점까지 고고 e..

https://www.acmicpc.net/problem/1711 1711번: 직각삼각형 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,500)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 주 www.acmicpc.net # 조건 2차원 평면에 N개의 점 세 점을 골랐을 때, 직각삼각형이 몇 개있는지를 구하여라. # 접근 방법 피타고라스 정리 c^2 = a^2 + b^2 두 점 사이의 거리를 구해서 가장 긴 변이 빗변이 된다. 빗변을 구한 후 피타고라스 정리를 이용하여 직각삼각형인지 판별 # 브루트 포스 - 시간초과 N = int(input()) dot = [list(map(int, i..