'Computer Science/Problem Solving' 카테고리의 글 목록 (3 Page)

Computer Science/Problem Solving

Covenant

[백준 1931번 회의실배정] 문제 해설 - 파이썬

2019.12.24

[백준 1931번 회의실배정] 문제 해설 - 파이썬 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다..

[백준 11047번 동전 0] 문제 해설 - 파이썬

2019.12.24

[백준 11047번 동전 0] 문제 해설 - 파이썬 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 문제 접근법 이런 문제와 비슷한 문제가 이름만 들으면 알법한 19년 하반기 모 기업의 코딩테스트 문제로 나왔습니다..

[백준 1759 암호 만들기] 문제 해설

2019.12.20

[백준 1759 암호 만들기] 문제 해설 문제 Start 본 문제는 백트래킹 문제입니다. 백트래킹에 대해 자세히 알지 못한다면 백트래킹(Backtracking)이란? 글을 참고해주세요. Step By Step Step 1 입력 L, C = map(int, input().split()) inputList = list(map(str, input().split())) inputList.sort() 문제에서 주는 값을 입력 받습니다. 알파벳 순으로 출력하기 위해서 .sort 함수를 이용해서 정렬합니다. Step 2 암호문 조합 (solution 함수 후반부) def solution(L, inputList, combStr, index): (중략) solution(L, inputList, combStr+list(i..

백준 2606번: 바이러스

2019.04.27

백준 2606번: 바이러스 문제 문제 보러 가기 풀이 웜 바이러스가 이동할 수 있는 컴퓨터들은 그래프의 형태로 연결되어 있다고 볼 수 있다. 컴퓨터 끼리는 양방향 그래프로 연결되어 있다. (1번과 2번 컴퓨터가 연결되 있다면 [1번]->[2번] 컴퓨터로 갈 뿐만 아니라 [2번]->[1번] 컴퓨터로 이동할 수 있다.) 웜 바이러스는 연결된 컴퓨터들끼리만 이동할 수 있기에 이는 그래프의 탐색으로 풀 수 있다. 본 문제를 DFS를 이용하여 풀었다. 문제의 맨 마지막에서 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 라고 한다. 즉 1번 그래프를 방문한다고 볼 수 있다. 따라서 1번 그래프에서 방문을 시작하여 DFA를 했을 때 방문하는 서로 다른 노드의 갯수를 세면 된다. 코드 import java.io.*; ..

[작성중][18-알고리즘] 재귀식(Recurrence equation)문제풀이

2018.06.18

1. T(n) = T(4/n) + n^2 (n>1) c (n=1)이를 Recursion tree방법을 이용하여 풀어라. 2. S(n) = 0 (n=0) c + s(n-1) (n>0)이를 iteration method를 이용하여 풀어라. [풀이]S(n) = c + s(n-1) = c + c + s(n-2) = 2c + s(n-2) = 2c + c + s(n-3) = 3c + s(n-3) ... = kc + s(n-k) = ck + s(n-k)

[작성중][18-알고리즘]배낭 문제(Knapsack Problem)

2018.06.18

배낭 문제(Knapsack Problem)라는 것은 예를 들어서 도둑이 한 밤중에 어느 가정집에 들어갔다. 그 집에는 금고가 있었다. 도둑은 금고를 여는데 성공을 했다. 금고에는 금, 은, 동, 구리가 있다.(놀랍게도 현금은 없었다.) 도둑의 가방에는 20kg만 담을 수 있다. 그렇다면 도둑은 무엇을 얼마나 담아야지 가방에 담은 물건이 최대의 가치가 들어갈까?의 문제이다. 즉 무엇을 얼마만큼 담아야 가방의 무게가 최대일까?이다. 배낭 문제(Knapsack Problem)는 두 가지로 나누어 진다. 금고에 금 4kg, 은 17kg, 동 10kg이 있다고 하자.(가치는 금>은>동 순이다.) 만약 금, 은, 동을 자를 수 있다고 하면 금 4kg, 은 16kg을 가방에 답는 것이 가방에 최대의 값어치의 물건을 ..

[18-알고리즘]점근적 분석(Asymptotic Analysis)에 대한 예제문제 풀이

2018.06.18

1. For the functions, 4^n and 2^n, what is the asymptotic relationship between these functions? Select all that apply.(a) 4n = O(2n) (b) 4n = Ω(2n) (c) 4n = Θ(2n) [풀이] 4^n은 2^2n이다. 이는 2^2n >= c2^n이다. (c는 c>0인 양의 상수이다.)따라서 4^n이 2^n보다 빠르게 증가하는 것을 알 수 있다. 그래프의 개형은 다음 위의 그림과 같다. (그래프는 n>0에서 형성된다.)f(n) = 4^n, g(n) = 2^n이라고 하자. f(n) >= cg(n)인 4^n >= c2^n 관계가 성립한다.따라서 점근적 하한선을 표시하는 Ω-표기인 (b) Ω(2n)가 답이다.

[18-알고리즘] 문자열 탐색(String Match) 유한 상태 기계를 통한 문자열 탐색(String matching with finite automata)

2018.06.17

유한 상태 기계는 다음과 같이 정의되어있습니다. 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)이라 한다. (출처 : Wikipedia) String matching with finite automata는 유한 상태 기계를 사용하여서 문자열을 탐색하는 것입니다. [그림1] 택스트에 패턴이 있는지 확인하기 위해서 유한 상태 기계[그림2] 같이 만듭니다. 그리고 Text에서 글자 하나가 유한 상태 기계의 하나의 입력값이 됩니다. 입력 값 하나가 들어오면 그게 맞는 상태로 변이가 일어납니다. [그림 2] 패턴을 가지고 유한 상태 기계를 만든 것입니다. 출처 : https://www.ics.uci.edu/~eppstein/161/960222.html ..

[18-알고리즘] 문자열 탐색(String Match) 라빈 카프 알고리즘(Rabin-Karp algorigm)

2018.06.17

앞의 포스팅에서 가장 무식한 방법인 Naive string match를 살펴 보았다. 패턴이 문자열애서 어디있는지 찾기 위해서 앞에서 부터 차례대로 찾는 방법이었습니다. 이렇게 무식한 방법보다 비용이 적게 들면서 빠르게 찾을 수 있는 방법인 라빈 카프 알고리즘을 살펴 보겠습니다. 텍스트 2359023141526739921이 있다고 합시다.(숫자로 구성되어있지만, 이는 문자열로 봅니다.) 여기서 패턴 문자열 31415를 찾으려고합니다. 텍스트 2359023141526739921에 패턴 문자열 31415가 있는지 확인하려고 합니다. 패턴 문자수는 '3', '1', '4', '1', '5' 즉 5개이다. 텍스트를 5개씩 앞에서 숫자로 변형시킬 것입니다. 라빈 카프 알고리즘의 핵심은 문자를 숫자 비교 문제로 바..

[18-알고리즘] 문자열 탐색(String Match) 소개 - Naive string match

2018.06.17

문자열 탐색(String Match)문제는 주어진 문자열에서 패턴 P를 찾는 것입니다. 패턴 문자를 오른쪽으로 한 칸씩 이동해 가면서 텍스트 문자와 하나씩 비교하는 것입니다. [그림 1] 이렇게 Text의 4번째에 찾으려는 ABAA 패턴이 존재함을 확인 할 수 있습니다. 이러한 방식을 Naive String match algorithm이라고 하고 다음과 같은 알고리즘입니다. n ← length [T] // Text의 글자 길이 m ← length [P] // Pattern의 글자 길이 for s ← 0 to n - m do // n - m + 1번 반복 if P[1 . . m] = T[s +1 . . s + m] // 현재 위치에서 pattern 글자가 text글자와 일치한지 확인한다. then retu..

[알고리즘 문제풀이 전략] 소수 구하기 by C언어

2017.08.19

문제1~1000 사이의 숫자 중에서 1과 그 자신 이외의 정수로 나누어지지 않는 소수를 구하는 것. 풀이 해설[12번 라인] 총 1~1000 숫자를 반복한다. [13번 라인] 소수의 특징인 자기 자신을 제외한 1 ~ i-1수를 반복해서 나누며 소수인지 탐색한다. [18번 라인] 소수일 경우 출력하고, count++로 소수의 갯수를 센다.[22번 라인] 출력될 때 한 줄에 8개의 소수가 있으면 다음 줄로 넘긴다. 결과 화면

[알고리즘 문제풀이 전략]05 임의의 숫자 배수의 개수와 합 구하기 by C언어

2017.08.19

문제1~1000 사이의 숫자 중 사용자의 입력을 받아서 해당 수의 배수의 개수와 배수의 총 합을 구하는 문제이다. 나의 풀이

Covenant

티스토리툴바