algorithm/problems

백준 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..

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

문제 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..

편집 거리

편집 거리 알고리즘이란, 두 문자열의 유사도를 판단하는 알고리즘이다. 리벤슈테인 거리라는 이름으로도 불린다. 문제를 통해 알아보자. 문제 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B를 만들고자 한다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다. 삽입 : 특정한 위치에 하나의 문자를 삽입한다. 삭제 : 특정한 위치에 있는 하나의 문제를 삭제한다. 교체 : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하라. 입력 문자열 A, B 각 문자열은 영문 알파벳으로만 구성되어 있으며,..

못생긴 수

문제 못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미한다. 1은 못생긴 수라고 가정한다. n번째 못생긴 수를 찾아라. 못생긴 수 : {1,2,3,4,5,6,8,9,10,12,15....} 입력 n (1 ~ 1,000) 출력 n번째 못생긴 수를 출력한다. 풀이 n = int(input()) ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블) ugly[0] = 1 # 첫 번째 못생긴 수는 1 # 2배, 3배, 5배를 위한 인덱스 i2 = i3 = i5 = 0 # 처음에 곱셈 값을 초기화 next2, next3, next5 = 2, 3, 5 # 1부터 n까지의 못생긴 수들을 찾기 for l in range(1, n): # 가능한 곱셈 결과 중에서 가장 작은 수를 선택..

백준 18353 - 병사 배치하기

www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예..