algorithm

비트마스크 알고리즘

비트마스크 비트마스크(Bitmask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. 비트마스크를 사용하면 더 빠른 시간 내에 연산을 해결하는 경우가 있다. 예를 들어, 2의 50승을 구해야 하는 문제가 있다고 하자. 이 경우 for문을 50번 돌려서 2를 계속 곱해나가야 한다 생각할 수 있지만, 비트마스크를 사용하면 1

백준 1248 - Guess

https://www.acmicpc.net/problem/1248 1248번: Guess Given a sequence of integers, a1, a2, …, an, we define its sign matrix S such that, for 1 ≤ i ≤ j ≤ n, Sij="+" if ai + … + aj > 0; Sij="−" if ai + … + aj < 0; and Sij="0" otherwise. For example, if (a1, a2, a3, a4)=( −1, 5, −4, 2), then www.acmicpc.net 풀이 1. 기본적으로 재귀를 이용한다. dfs(index + 1)을 계속 호출하면서 answer가 s 배열을 만족하는지 check 함수를 통해 확인한다. 2. 문제에서 중..

백준 3665 - 최종 순위

문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올..

백준 2887 - 행성 터널

문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109..

커리큘럼

문제 N개의 강의를 듣고자 한다. 이 때, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 동시에 여러 강의를 들을 수 있다고 할 때 N개의 강의에 대하여 수강하기 까지 걸리는 최소 시간을 각각 구하라. 입력 첫째 줄 -> N (1 ~ 500) N개 줄 -> 각 강의의 강의 시간(1 ~ 100,000)과 선수 강의들의 번호가 주어진다. 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝난다. 출력 N개의 강의에 대하여 수강하기까지 걸리는 최소 시간 풀이 from collections import deque import copy # 노드의 개수 입력받기 v = int(input()) # 모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0] * (v..

그래프 이론

서로소 집합 서로소 집합 자료구조는 몇몇 그래프 알고리즘에서 매우 중요하게 사용되므로 그래프 알고리즘 이론 전에 설명하고자 한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다. union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 그래서 서로소 집합 자료구조는 union-find 자료구조라고 불리기도 한다. 서로소 집합 자료구조 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합 정보가 주어졌을 때 트리 자료구조를 ..

알고리즘 문제 - 볼링공 고르기

문제 A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. 예를 들어, N이 5이고, M이 3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 두 사람이 공을 고르는 경우의 수는 8가지이다. 입력 첫 째줄 -> 볼링공의 개수 N(1 ~ 1000), 공의 최대 무게 M(1 ~ 10) 둘 째줄 -> 각 볼링공의 무게 K (1 ~ M) 출력 두 사람이 볼링공을 고르는 경우의 수 풀이 3가지 풀이를 해봤다. 1. 이중 loop n,m=m..

최단 경로

가장 빠르게 도달하는 방법 최단 경로(Shortest path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점(국가 or 마을 등)은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출력된다. 코딩 테스트 수준에서는 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형만 파악해도 충분하다. 더불어 앞서 공부한 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다. 다익스트라 최단 경로 알고리즘 다익..