정지문제 (Halting problem) 정지문제는 처음으로 증명된 판정불가능한 문제가 되었다고 한다. 정지문제를 간단하게 요약해보면 아래와 같다. 프로그램과 입력값이 주어졌을 때, 프로그램에 입력값을 넣고 실행한다면 프로그램이 계산을 끝내고 멈출지, 무한으로 계산할지 판정할수 있는가? 1936년에 앨런 튜링은 모든 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 간단한 증명 귀류법을 사용하면 간단한데, 프로그램 a와 문자열 i입력으로 실행이 끝나면 true, 실행이 멈추지 않고 영원히 계산된다면 false가 결과값으로 나오는 halt(a, i)라는 알고리즘이 있다고 해보자. 이러한 완벽한 알고리즘을 가지고 아래의 함수를 구현했다고 한다면, 만약 trouble(..
분류 전체보기
이진탐색 알고리즘을 풀다보면 특정 조건을 만족하는 해를 찾아야 하는 경우가 있는데 이 경우 유용한 알고리즘이 이진탐색이다. 물론 데이터가 오름차순, 내림차순으로 정렬되어있는 경우, 어떠한 기준에 의하여 순서가 정해져 있는 경우에만 사용이 가능하다. 원리를 아주 간단하게 요약하자면 계속 반토막 내면서 탐색범위를 줄여나가는 것이라고 생각하면 쉽다. 그리고 확인하는 것은 탐색범위의 중간값이다. 따라서 시간복잡도는 아래의 식에 의해서 O(logN)이다. (log2 상수는 무시된다) 이진탐색 과정 이진탐색은 다음과 같은 과정을 거친다. 인덱스를 기준으로 low를 왼쪽의 맨 끝, high를 오른쪽의 맨 끝으로 정하고 시작한다. 그 low, high의 중간을 mid로 둔 뒤, mid에 있는 값을 검색한다. 임의로 여..
문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제가 아주 심플한데, n명의 병사, k번의 무적권(?)을 가지고 enemy 배열이 주어졌을 때 최대 몇 라운드까지 갈 수 있는지를 구하는 문제였다. 문제 풀이 과정 문제 접근은 아래와 같다. 우선 무적권를 초반에 몰아서 쓴다. 그리고 그것을 stack에 넣어서 stack의 요소 중에 가장 적은 요소보다 큰 enemy가 나왔을 때 무적권을 취소하고, 그 enemy에 무적권을 쓰고, 그 제일 작은 요소에 병사를 사용하는 것으로 문제를 해결했다. 일종의 그리디 알고리즘 느낌이랄까...? 그때그때 최적을..
문제 설명 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr시소 짝궁을 구하는 문제인데, 시소의 길이는 2, 3, 4가 있다. 만약 무게가 [100,180,360,100,270] 라고 한다면 [100, 100]은 시소 짝궁이 되고, [180, 360]도 4, 2길이에 앉게된다면 시소 짝궁이 된다. 문제 풀이무게의 배열이 10만개가 주어지기 때문에 이중 for문을 하기에는 시간초과가 확실했다. 어떻게 하면 for문을 중복해서 사용하지 않을 수 있을까? 생각보다 정말 간단하게 접근이 가능했다. 우선 same 배열, multi 배열을 만들어서 무게의 최댓값이 1000..
문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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문만 시원하게 써주면 문제풀이 ..
