분류 전체보기

문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 숫자의 배열이 주어지면 자신보다 뒤에 있는 숫자 중에 자신보다 크면서 가장 가까이 있는 수로 바꾸고 없다면 -1로 바꾸는 문제이다. 예를 들면 [2, 3, 3, 5]가 주어지면 [3, 5, 5, -1]을 출력해야 한다. 문제 풀이 뒤에 있는 숫자 중 자신보다 크면서 가장 가까이 있는 수라는 점에서 뒤에서 접근해야 한다는 힌트를 얻었다. 자기와 가장 가까워야 한다는 조건이 있어 정렬은 의미가 없다. 뒤에서부터 접근하면서 가장 마지막 값과 비교가 필요하다는 점에서 stack구조를 떠올렸다. 아이디어는 ..

문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아래와 같은 미로가 ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"] 와 같은 형태로 주어지고, L을 방문했다가 E를 방문하는 최소의 이동거리를 구하는 문제이다. 문제 풀이 (DFS, 실패) 처음 문제풀이는 가로, 세로 길이의 범위가 5 이상 100 이하인 조건이 있었기 때문에 숫자가 충분히 크지 않아서 DFS로 충분히 풀 수 있지 않을까? 하는 생각이 들었다. (보통 이런 최단거리문제는 BFS가 맞다) 아무튼 나는 move라는 재귀함수를 만들었다. 재귀함수의 탈출조건에 시..

알고리즘을 공부하다 보니 자료구조에 대한 기본기를 다져야겠다고 생각했다. 앱을 개발하면서도 데이터를 구성할 때 막연하게 구성한 느낌이 난다. 항상 데이터를 구성하면서 느낀 점은 나중에 구조를 바꿀 때 정말 골치가 아프다는 점인데, 이렇게 하나하나 자료구조에 대한 공부를 통해 처음 앱을 구성할 때 이유 있는 데이터 구성을 하고자 자료구조에 대한 공부를 시작하게 되었다. 자료구조란? 자료구조(data structure)란 컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미한다. 데이터 값의 모임, 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다. 실행시간, 메모리 용량을 최소화시켜 정확하게 원하는 데이터에 접근할 수 있게 적절한 자료구조의 선택을 해야 한다. 자료..

문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N개의 마을이 있고, 이 마을간에는 도로가 연결되어있다. 그리고 각 마을간 최소거리가 k이하인 마을의 갯수를 구하는 문제이다. 플로이드-워셜이나 다익스트라 알고리즘을 사용하면 아주 손쉽게 풀 수 있다. 나는 플로이드-워셜 알고리즘을 사용했다. 하지만 이것은 너무나도 치트키 같은 느낌... 특히 문제를 풀어본뒤 질문들을 보는 습관이 생겼는데 BFS, DFS로도 충분히 풀수있는 사이즈이기 때문에 도전해보고자 했다. 플로이드 워셜 알고리즘 아주아주 코드가 쉽다. 3중 for문만 시원하게 써주면 문제풀이 ..

문제 소개 정말 정말 유명한 문제 중 하나인 "하노이의 탑" 문제. 이 문제를 풀면서 정말 점화식, 재귀함수에 관련된 깊은 생각을 한 것 같다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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라고 생각하면 된다. 힙에서의 index inde..