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

Computer Science/Problem Solving

Covenant

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 사이의 숫자 중 사용자의 입력을 받아서 해당 수의 배수의 개수와 배수의 총 합을 구하는 문제이다. 나의 풀이

[알고리즘 문제풀이 전략]04 피보나치 수열 byC언어

2017.08.19

문제f_n = f_n-1 + f_n-2 의 점화식을 가지는 피보나치 수열을 구현하라. 코드

[알고리즘 문제풀이 전락]02 숫자 맞추기 byC언어

2017.08.19

문제프록그램에서 임의의 숫자를 생성하여, 사용자가 정확히 답을 맞출 때까지 프로그램이 멈추지 않고 계속 실행되게 하라. 나의 풀이

[알고리즘 문제풀이 전략]01-10진수와 16진수 변환 프로그램 by C언어

2017.08.18

문제10진수를 16진수로 바꾸거나 16진수를 10진수로 변환하는 프로그램을 제작해보라. 작성 코드