분류 전체보기

문제 소개 정말 정말 유명한 문제 중 하나인 "하노이의 탑" 문제. 이 문제를 풀면서 정말 점화식, 재귀함수에 관련된 깊은 생각을 한 것 같다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아래와 같이 세 개의 기둥이 있고, 크기가 큰 원판부터 기둥에 꽂혀있다. 이제 이것을 크기가 작은 원판이 크기가 큰 원판보다 아래로 가지 않게 하면서, 한 번에 하나의 원판을 이동하며 세 번째 기둥으로 옮길 때 최소로 옮기는 방법을 return 하는 문제였다. 예를 들면, 2를 입력하게 된다면 2개의 원판이 1번에 있고, 이 원판을 세 번째 기둥으로 최소로 옮기는 방..

컴퓨터 알고리즘을 공부하다 보면 시간복잡도에 대해서 당연히 많이 마주하게 되고, 보통은 O(n)처럼 Big-O 표기법을 사용한다. 하지만 시간 복잡도를 나타내는 방법에는 위 세 가지가 있다는 것을 알게 되었다. 이를 간단하게 정리해보려고 한다. 시간복잡도 간단하게 시간복잡도를 살펴보면 아래와 같이 정수 n을 받으면 0부터 n까지 더해주는 함수가 있다고 해보자. func solution(n: Int) -> Int { var result = 0 for i in 0..

문제 27277번: 장기자랑실력이 $4, 2, 3, 5, 1, 6$인 순서로 공연하면, 각 병사가 발휘할 수 있는 실력은 순서대로 $4, 0, 1, 2, 0, 5$이므로 실력의 합이 $12$인 채로 공연을 끝마칠 수 있다.www.acmicpc.net 문제 풀이max(0, 현재값-이전값)에서 최대의 효과를 발휘하려면 (현재값-이전값) > 0이고, 그것이 최대로 클 때 최대 효율을 발휘할 수 있다. 예를 들면 [1,2,3,4]가 있다면 [4,1], [3,2]을 짝지어야 최종합 4로 최댓값을 만들 수 있다. 만약 배열이 홀수일 경우 큰 수와 작은 수를 짝지은 후 남은 값을 맨 마지막에 추가해 주면 된다.import Foundation var n = Int(readLine()!)! var skills = rea..

힙(Heap) 이란?힙은 최댓값 혹은 최솟값을 찾아내는 연산을 빠르게 하기 위해 이진트리를 기본으로 하는 자료구조이다. 구조는 자식노드, 부모노드로 구성이 되어있는데 직관적으로 알 수 있겠지만...(?) 삼각형으로 생각한다면 위 꼭짓점이 부모노드, 아래 두 꼭짓점에 위치한 노드가 자식노드라고 할 수 있다. 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 최대 힙, 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 최소 힙이라고 부른다. 이 두 조건만 만족하게 된다면 숫자의 크기에 따른 순서는 상관이 없다.(예를 들면, 아래의 그림에서 보듯이 20이 느낌상 맨끝에 있어야 할 것 같은데 그렇지 않다던가...) 각 노드 위에 붙은 번호는 index라고 생각하면 된다.힙에서의 indexindex가 ..

Dynamic Programming 동적 프로그래밍, 다이나믹 프로그래밍, 동적 계회법으로 불리는 Dynamic Programming은 큰 문제를 작은 문제로 나누고 작은 문제의 답들을 이용해 원래 문제의 답을 찾는 방법이다. 주어진 문제를 최대한 많이 이용할 수 있는 작은 문제들로 나누는 게 핵심이라고 생각한다. (그래야 재사용이 많이 가능하고, 메모리를 적게 쓴다) Dynamic Programming 의 예시 피보나치수열 가장 쉬운 예로는 피보나치 수열이 있다. 피보나치수열은 아래와 같이 표현할 수 있다. f(0) = 1 f(1) = 1 f(n) = f(n-1) + f(n-2) when n > 1 만약 값을 재사용하지 않는다면...? 아래와 같이 5번째 값을 구하기 위해서는 15번의 연산이 필요하다...

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 간단히 설명하면 S 에서 A, B로가는 최단 거리를 구하는데 A, B가 같이 갈 수 있는 거리를 최대한 같이 간다음 따로따로 가게 되는 경우가 있다면 그 최단거리를 구하는 무제이다. 이를 문제에서는 길간의 거리를 요금, 같이 가는 것을 동승으로 표현했다. 위의 경우는 S에서 5까지 같이 이동한뒤 (34) 5에서 B까지 (46) 5에서 A까지 (2) 가는 경우가 최단거리라고 한다. 위의 길을 준다면 총 82의 최소 거리를 출력해야 하는 문제이다. 문제 풀이 두가지 방법으로 문제를 풀 수 있다...

문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단하게 문제를 소개하면[[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]] 라는 입력값이 나온다면 이 입력값을 모두 포함하는 최소의 실수가 몇개인지 출력하는 문제이다. 아래에서는 3이라는 출력값이 나온다. 문제 풀이 아주 간단하게 접근을 했다. 우선 이런 문제들은 하나를 기준으로 정렬해주는 것이 핵심 포인트 인듯 싶다. 그 후 미사일 문제라 aim 이라는 변수를 두었고, 이 aim이라는 구간에 target이 포함된다면 상관 없고, 만약 target의 범위가 좁다면..

문제 소개 프로그래머스 - 길 찾기 게임 (이진 트리 순회 문제) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 이진 트리 순회 문제였다. 아래와 같은 트리 순회방법이 네가지가 있는데, 여기서는 전위 순회, 후위 순회를 물어보는 문제였다. 예를 들면 [5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2] 같은 노드가 주어진다면 아래와 같은 이진 트리가 만들어지고, 전위 순회, 후위 순회가 [[7, 4, 6, 9, 1, 8, 5, 2, 3], [9, 6, 5, 8, 1, 4, 3, 2, 7]] 형태로..