본문 바로가기

알고리즘

[Algorithm] 10026. 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 비교적 쉬운 문제였다. 처음에 bfs 를 적록색약인 사람용 / 적록색약 아닌 사람용 => 이렇게 두 개 만들어야 하나 싶었는데, 그냥 적록색약인 사람용 그림을 새로운 리스트에 새로 선언해줘서 그거만 기존 bfs 함수에 돌렸다. import sys from collections import deque input = sys.stdin.readline dx = [0, 0, 1, -1] dy = .. 더보기
[Algorithm] 2589. 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 내 오답 포인트 - 굳이 combination 을 썼다. 그래서 시간초과남. import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(a, b): global result q = deque() visit[a][b] = True q.append((a, b, 0)) while q: x, y, cnt = q... 더보기
백준 3273. 두 수의 합 문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 오답 원인 이 문제를 봤을 때, 이중 for문을 생각했다. 시간복잡도는 O(N^2) 이므로 시간 초과가 났다. // 시간초과 for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j.. 더보기
순열 (Permutation) 알고리즘의 모든 것 1~N까지 이루어진 수열을 생각해보자. 1 2 3 4 1 3 2 5 4 2 3 1 6 5 1 2 3 4 크기는 항상 N이 되어야 하고, 겹치는 숫자가 존재하지 않는다. 크기가 N인 순열은 총 N!개가 존재한다. 순열을 사전순으로 나열했을 때 N = 3인 경우에 사전순은 다음과 같다. 1 2 3 - 첫 순열 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 - 마지막 순열 첫 순열은 무조건 오름차순이고, 마지막 순열은 내림차순임을 알 수 있다. 순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾아보자. C++ STL의 algorithm에는 이미 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다. (이럴때마다 C++로 갈아타야.. 더보기
Boj 1358. 하키 백준 1358. 하키 풀이 ① 왼쪽 반원에 포함될 때 카운트 ② 가운데 직사각형에 포함될 때 카운트 ③ 오른쪽 반원에 포함될 때 카운트 반원에 포함될 때 풀이는 (a,b)에서 원의 중심까지의 거리 더보기
[개념] 유클리드기하학,택시기하학 / Boj 3053. 택시 기하학 유클리드 기하학에서의 원 원의 넓이 구하는 공식은? 택시 기하학에서의 원 (우리가 생각하는 마름모이다) 마름모 넓이 구하는 공식은? 백준 3053번. 택시 (분류 - 기하 알고리즘) 소스코드는 전혀 어려운 게 없다.. 이건 사실 알고리즘보단 기하문제 #define _USE_MATH_DEFINES #include #include int main() { double R, S1, S2; scanf("%lf", &R); S1 = M_PI * R * R; S2 = R * R * 2; printf("%.6f\n", S1); printf("%.6f\n", S2); return 0; } 더보기
[개념] 플로이드 와샬 (Floyd Warshall) / 백준 11404 '모든 정점' 에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다. 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다. 또한 플로이드 와샬은 기본적으로 다이나믹 프로그래밍(DP) 기술에 의거한다. 위와 같은 그래프가 존재한다고 해보자. 이때 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 출력하면 다음과 같다. 이제 이 테이블이 의미하는 바는 '현재까지 계산된 최소 비용' 이다. 이러한 이차원 배열을 반복적으로 갱신하여 최종적으로 모든 최소 비용을 구하는게 목적이다. 바로 그러한 반복의 기준이 '거쳐가는 정점'인 것이다. 바로 1을 거쳐가는 경우부터 차례대로 살펴보도록 하자. (자기자신에서 출발하여 자기자신으로 도착하.. 더보기
[개념] Bit연산 비트연산 logical right shift arithmetic right shift - 부호를 염두해두고 하는 shift 연산자 ① getBit bit연산자를 이용해 숫자 9의 이진수 값에서, i=(3)번 인덱스 값을 가져오려면? 9의 경우 3번 인덱스의 값이 1이다. (01001) 20의 경우 3번 인덱스의 값이 0이다 (10100) 우리가 원하는건 해당 자리수의 값이므로, 나머지 자리들은 다 0으로 만들어주고 해당 자리수만 원본데이터에서 가져오는 값을 만들어줘야 한다. 그렇게 구하기 위해서는 해당 인덱스의 값을 1로 세팅하고 나머지는 0으로 세팅하여 -> 1000 & 연산자를 해주면 원하는 값을 얻을 수 있다. = X 그러면 연산할 값인 1000은 어떻게 만들어낼까? 1을 i만큼 왼쪽으로 shift.. 더보기

티스토리툴바