Danny's IT

DFS 탐색 DFS는 Depth-First-Search, 즉 깊이 우선 탐색으로 그래프의 깊은 부분부터 우선적으로 탐색하는 알고리즘이다. 특정한 경로로 탐색할 때 그 경로에서 최대한 깊숙이 들어가서 노드를 방문한 후, 더 이상 들어갈 곳이 없다면 위의 노드로 돌아가 다른 경로로 탐색한다. 위와 같은 그래프에서 깊은 부분부터 탐색한다고 하면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순으로 탐색하게 된다. 그래프의 구현은 다음과 같이 리스트에 인접한 노드들을 저장하는 방식으로 할 수 있다. graph = [ [], # 0번 노드는 존재하지 않으므로 0번째 인덱스는 비워두기 [2, 3], # 1번 노드는 2, 3번 노드와 연결되어 있으므로 1번째 인덱스에 2, 3 저장 [1, 4, 5],# 2..

스택(Stack) 먼저 들어온 데이터가 나중에 나가는 형식(선입후출 / First In, Last Out)의 자료구조이다. 입구와 출구가 동일한 형태에 데이터를 쌓는다고 생각할 수 있다. 스택 구현하기 파이썬에서 리스트 자료형의 append() 메서드는 리스트의 맨 끝에 데이터를 입력해주는 기능을 제공하고, pop()메서드는 리스트의 맨 끝의 데이터를 출력해주는 기능을 제공하기 때문에 리스트를 이용하여 스택 구현이 가능하다. stack = [] stack.append(1) stack.append(2) stack.append(3) stack.pop() print(stack) 실행 결과 '1 입력 -> 2 입력 -> 3입력 -> 가장 나중에 들어온 데이터 삭제' 의 과정을 거쳐 리스트에 [1, 2]만 남게 ..

문제 설명 컴퓨터실에서 수업 중인 정보 선생님은 냉난방기의 온도를 조절하려고 한다. 냉난방기가 멀리 있어서 리모컨으로 조작하려고 하는데, 리모컨의 온도 조절 버튼은 다음과 같다. 1) 온도를 1도 올리는 버튼 2) 온도를 1도 내리는 버튼 3) 온도를 5도 올리는 버튼 4) 온도를 5도 내리는 버튼 5) 온도를 10도 올리는 버튼 6) 온도를 10도 내리는 버튼 이와 같이 총 6개의 버튼으로 목표 온도를 조절해야 한다. 현재 설정 온도와 변경하고자하는 목표 온도가 주어지면 이 버튼들을 이용하여 목표 온도로 변경하고자 한다. 이 때 버튼 누름의 최소 횟수를 구하시오. 예를 들어, 7도에서 34도로 변경하는 경우, 7 -> 17 -> 27 -> 32 -> 33 -> 34 이렇게 총 5번 누르면 된다. 입력 ..

문제 설명 vega 선생님은 Miss 피자 가게의 단골 손님이다. 그는 이번 달부터 절약 생활을 시작했다. 그래서 그는 피자 가게에서 주문할 수 있는 피자 중 1 달러 당 열량이 최대가 되는 피자를 주문하고 싶어한다. 이러한 피자를 "최고의 피자"라고 부르기로 하자. "최고의 피자"는 1종류가 아니다. Miss 피자는 N 종류의 토핑에서 여러 종류를 자유롭게 선택하여, 도우 위에 올려 주문할 수있다. 같은 토핑을 2 개 이상 올릴 수 없다. 도우에 토핑을 하나도 하지 않은 피자도 주문할 수있다. 도우의 가격은 A 달러이며, 토핑의 가격은 모두 B 달러이다. 실제 피자 가격은 도우의 가격과 토핑 가격의 합계이다. 즉, 토핑을 k 종류 (0 ≦ k ≦ N) 한 피자의 가격은 A + k × B 원이다. 피자 ..

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로, 탐욕법이라고도 한다. 그리디 알고리즘을 이용할 때는 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다. 코드업(CodeUp) 3301: 거스름돈 문제설명 어떤 가게의 욕심쟁이 점원은 거스름돈을 나눠줄때 거스름돈의 개수를 적게해서 주고자 한다. 거스름돈을 입력 받아 점원이 줄 수 있는 최소 거스름돈의 개수를 출력하시오. 예를 들어 54520원인 경우, 거스름돈으로 50000원권 1장, 1000원권 4장, 500원 1개, 10원 2개 해서 총 8개이다. (※ 현재 우리나라가 사용하고 있는 화폐를 사용한다. 10원 50원 100원 500원 1,000원 5,000원 10,000원 50,000원) 입..

리스트 컴프리헨션 대괄호 안에 조건문과 반복문을 적용하여 리스트를 생성하는 방법으로, 리스트를 쉽게 초기화할 수 있다. # 리스트 컴프리헨션을 사용하지 않은 경우 lst = [] for i in range(1, 11): lst.append(i) print(lst) # 리스트 컴프리헨션을 사용하는 경우 lst = [i for i in range(1, 11)] print(lst) 실행 결과 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 위 예시와 같이 리스트 컴프리헨션을 사용하면 코드가 간단해지며 실행속도도 빨라진다. 리스트 컴프리헨션을 사용하여 리스트 쉽게 초기화하기 # 0부터 19까지의 수 중에서 홀수만 포함하는 리스트 even_lst ..

복잡도 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 빅오표기법(Big-O Notation) 수학적 정의는 모든 $ 0 < n_{0} \leq n $에 대하여 $ 0 \leq f(n) \leq k \bullet g(n) $인 양의 상수 $ k $와 $ n_{0} $가 존재하면 $ f(n) = O(g(n)) $이다. 쉽게 말하면 어떤 프로그램을 실행했을 때 연산횟수가 $ 2n^2 + 5n + 1000 $이라고 하면 이 프로그램의 시간복잡도를 계수를 제외한 최고차항만 남겨서 $ O(n^2) $이라고 하는 것이다. 이렇게 표기하는 이유는 $ n $의 값이 무한히 커지면 최고차항을 제외한 항들은 최고차항에 비해 값이..