알고리즘4 오늘의 피드백 - 거꾸로 생각할 때 주의할 점. 1. N개의 수열에서 구간의 합이 최대인 구간 찾기 문제는 아래와 같다. N개의 정수가 담긴 수열이 주어진다. 이때 특정 구간의 합이 최대가 되는 구간을 찾는 효율적인 방법은? 문제는 워낙 간단하다. 그래서 무식하게 풀 수 있다. 존재할 수 있는 모든 구간 (p, q) 범위를 for 문을 통해 일일이 접근한다. 해당 구간의 합을 구해서 최대인지 확인한다. 그러나 이러한 방식은 시간복잡도가 사실상 쓸모 없는 수준이다. O(N^3)이다. 무려 세제곱이다. for 문을 통해 모든 p, q 구간을 접근해야 하므로 N 제곱의 처리가 소요되고, 또 더하기 연산을 위해서 또 O(N)이 필요하다. 즉, 복잡도는 세제곱이다. 개선해봤자 O(N^2)이 될 뿐이다. 특정 p 값에서 시작해서 q를 하나씩 늘려나가면 이전에 사.. 2023. 11. 7. 메모리 계층 구조와 알고리즘의 공학적 한계 1. 개발에 있어서 컴퓨터 하드웨어 문제 컴퓨터 기계 장치의 하드웨어적인 본질은 무엇일까? 폰 노이만 아키텍처에 따르면, 컴퓨터의 기계적 본질은 프로세서인 CPU와, 데이터와 명령어가 저장된 스토리지인 RAM이다. RAM와 CPU 두 하드웨어만 있으면 그것이 곧 흠 잡을 데 없는 컴퓨터다. 튜링 기계와 등가다. 실제로 컴퓨터 장치를 공부할 때, NAND 게이트를 차곡차곡 조립해나가 8비트나 16비트 컴퓨터를 만들 때가 있는데, 이때도 간단한 CPU와 RAM만으로 컴퓨터를 완성할 수 있다. 이것만으로도 컴퓨터의 원리를 설명하는데 충분하기 때문이다. 그러나 컴퓨터는 기계 장치다. 물리적인 제약 조건에 강하게 결합되어 있다. 실제 컴퓨터는 구체적인 재료와 물리적인 비용을 바탕으로 설계된다. 즉, 그 속도와 명.. 2023. 11. 3. 수열에서 중간값 찾기 문제와 분할/정복 알고리즘의 정수 1. 중간값 찾기 문제 임의의 N개의 원소를 가진 수열이 주어졌을 때, 그 중간값을 찾는 문제다. 여기서 중간값이란 그 값을 기준으로 작은 모든 원소들과 그 값보다 큰 모든 원소들을 이등분하는 값을 말한다. 간단하게 생각하면 정말 정의 그대로, 그냥 주어진 배열을 정렬하고 중간에 있는 값을 선택하면 될 것 같다. 물론 그렇게 해도 풀리며, O(N logN) 정렬 알고리즘을 선택해 사용하면 될 것이다. 그러나 이렇게 푸는 것은 매우 아쉽다. 컴퓨팅 사고력에서 중요한 능력 중 하나는 쓸데없는 계산을 줄이는 것이라고 배웠다. 지금 문제는 중간값을 찾으면 되지, 굳이 정렬까지 할 필요는 없다. 위치만 알면 되기 때문이다. 나는 이 문제를 N/2 크기의 힙(Heap) 자료구조를 이용하는 식으로 생각했다. Min .. 2023. 11. 2. 하노이 탑 재귀 문제는 엉뚱하게 해결할 수 있으니 주의해야 한다. 1. 하노이의 탑 하노이의 탑은 알고리즘 과목에서 "재귀"를 공부할 때 단골로 나오는 예제 중 하나다. 너무 자주 나와서 모르는 개발자가 없는 것 같다. 그래서인지, 문제는 사실 꽤 어려운 편에 속하는 데도 불구하고 문제 난이도가 최하로 분류되곤 한다. 문제는 매우 간단하다. 왼쪽의 원판 N개를 3번째 막대기로 하나씩 옮기면 된다. 이때 각 원판은 자신보다 무거운 것이 위에 있으면 안 된다. 하노이의 탑 알고리즘은 구글링을 해서 누구나 쉽게 알 수 있으니, 이 글에서는 내가 이 문제를 풀면서 저질렀던 실수를 작성하고 이에 대해 피드백(반성)을 하려고 한다. 2. 알고리즘은 풀기만 하면 안 된다. 알고리즘 문제들을 가지고 IT기업에서 면접을 보는 이유는 그것을 풀 수 있는가의 여부가 아니라, 그것을 어떻게.. 2023. 10. 26. 이전 1 다음
