(본문은 학교 강의내용을 바탕으로 이해한 것을 정리한 글입니다. 틀린 부분이 있다면 지적 감사하겠습니다.) 이분탐색 알고리즘, Binary Search는 기초적인 탐색 알고리즘이다. 알고리즘을 공부하다 보면 다들 한번쯤은 들어봤을 만한 녀석이다. 나 또한 처음 알고리즘을 접하고 binary search를 접했을 때에는 직관적으로는 이해하기 어렵지는 않았다. 하지만 이녀석을 정확하게 증명한 적은 없었고, 깊이 생각해본 적도 없었던 것 같다. 굳이 왜..? 라는 생각이 들지도 모르지만 학부생일때 이런 경험을 많이 하는게 나중에 도움이 될 거라 믿어 포스팅을 작성하게 되었다. Binary Search // Binary Search // a is sorted array, n: size, x: value to f..

(틀린 부분이 있다면 지적 감사하겠습니다.) 우리는 알고리즘을 얼마나 제대로 이해하고 쓸까? 알고리즘을 정확히 이해하고 쓰는것과 그렇지 않은 것에는 많은 차이가 있다. 오늘은 재귀의 예를 소개하고, 그 정확성을 증명해보고자 한다. 1. 합 구하기 1부터 x 까지의 합을 구하는 프로그램을 작성해보자. unsigned int sum(unsigned int x){ int i, s; s = 0; for(i=1;i8... 이런식으로 가다가 0이 되고, 0을 리턴하면 다시 쭉~~~ 올라와 1부터 10까지 더해진다고 지금껏 이해했다. sum(3) -> sum(2) -> sum(1) -> sum(0) 6 3 1 0 리턴 물론 틀린말은 아니다! 당연한 소리이고, 이런식으로 생각하는 게 이상하지 않다. 그렇지만 이렇게 하..

오늘을 Halting Problem 이라는 유명한 판정 문제를 소개해 보겠습니다. Alan Turing의 증명과 내 나름의 이해한 것을 바탕으로 풀이를 써보았습니다. The Halting Problem - 프로그램 M 과 입력 X 가 있을 때 M에 입력 X를 주고 수행시키면 M은 종료할 것인가? 이 프로그램 M이 계산을 끝나고 멈출지, 아니면 영원히 멈추지 않을지 판정하라. Halting Problem 이라는 유명한 문제인데 이 문제를 처음 봤을 때는 이게 뭐지...? 싶었다. 프로그램 M이 멈추냐, 안 멈추냐 뭐 이런 뜻 같은데.... 상황에 따라 멈출 수도 있고 안 멈출수도 있지 않나? 라고 생각했다. "상황에 따라서" 말이다. 당연한 얘기일 것이다. 프로그램을 어떻게 짜느냐에 따라 멈출 수도 있..

문제 링크 코딩테스트 연습 - 가장 큰 수 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 문제 설명 매개변수로 숫자들이 주어졌을 때, 숫자들을 재배치해 가능한 숫자들 중에서 가장 큰수를 문자열로 return 하면 된다. 문자열로 리턴하는 이유는 값이 너무 큰 경우도 있기 때문이다. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 ..

문제 링크 코딩테스트 연습 - 위장 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 위장 programmers.co.kr 문제 설명 스파이는 가지고 있는 옷을 조합해서 입습니다. 하지만 적어도 하나의 옷은 입어야 하며 같은 종류의 옷은 중복해서 입지 못합니다. 한 부위의 옷은 하나만 입어야 한다는 뜻입니다. 매개변수 clothes[][] 에서는 옷의 종류와 각 종류에 해당하는 옷들을 알 수 있습니다. 서로 다른 옷의 조합의 수를 구하면 되는 문제입니다. 풀이 옷의 종류를 Key, 옷들을 Value 로 가지는 해시맵을 이용합니다. Map map = new HashMap(); map key value 얼굴 A, B, C 상의 D, E 하의 F 스파이가 위 예시처럼 3종류의 옷과, 각 ..

문제링크 코딩테스트 연습 - 카펫 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 갈색, 노란색 격자의 갯수가 주어졌을 때 전체 카펫의 가로, 세로의 길이를 구하는 문제입니다. keypoint 모든 각 격자의 넓이를 1로 생각. 카펫 가로 길이: m 세로 길이 : n 일 때 m, n, yellow, brown 으로 식을 세운 뒤, 가능한 모든 순서쌍을 탐색한다. (완전탐색) 완전 탐색을 할 때 for문에서 변수의 범위를 잘 정해야 한다는 것이다. 이는 여..