본문 바로가기

IT 공부104

[피드백] - 일상 언어를 제대로 이해하자. (문제 해석 실패 사례) 컴퓨터로 문제를 해결할 때, 코딩테스트처럼 미리 전산학/컴퓨터공학적 개념으로 잘 정리된 문제라고 해도 어느 정도는 일상 언어를 통해 문제 사항이 기술된다. 여기서 프로그래머는 요구 사항을 정확하게 해석해야 한다. 이를 위해 커뮤니케이션이 필요하다. 아래는 내 실수다. 문제는 다음과 같다. N개의 사탕을 3명의 어린이에게 나눠주려고 한다. 최대한 공평하게 나누려고 한다. 공평함의 기준은 받는 사탕의 총 무게를 기준으로 가장 무거운 어린이의 사탕 무게와 가장 가벼운 어린이의 사탕 무게의 차이다. 사탕의 무게는 20이하의 정수로 주어진다. 가장 공평한 분배일 때의 무게 차이를 구하는 알고리즘은? 여기서 나는 나름 꽤 만족스런 해법을 고안했으나 결과적으로 완전히 틀린 대답이 되고 말았는데, 그 이유는 문제의 요.. 2024. 3. 25.
주어진 합을 가지는 특정 구간 구하기 문제. 수열과 어떤 값 하나가 주어진다. 구간의 합이 특정 값인 구간을 구하라. 이 문제를 풀기 위한 아이디어로 다음과 같이 생각했다. 1. 시간복잡도 시간복잡도는 적어도 O(N)이다. 절대로 이것보다 낮을 수는 없다. 구간의 "합"을 알아야 하므로 최악의 경우 수열의 전체 구간이 답이 될 수도 있기 때문이다. 2. 나에게 주어진 정보 보통 알고리즘의 Big-O가 N^2이나 N^3이 되는 이유는 불필요한 계산을 하기 때문이다. 불필요한 계산은 문제에서 주어진 정보나, 본인이 계산을 진행해가며 얻은 값들을 정보로 활용하지 않을 때 발생한다. 그래서 나에게 주어진 정보는 아래와 같았다. 문제에서 주어진 정보 = 구간의 값. 계산을 하며 얻을 수 있는 정보 = 0번째 배열부터 시작해 p 까지의 누적합. 3. .. 2024. 3. 20.
[컴퓨터의 기원] 2. 괴델의 불완전성 정리 1. 괴델의 아이디어에서 무엇이 혁신인가? 1-1. 이전 내용 요약 컴퓨터의 본질과 기원에 대해 - 1. 힐베르트 프로그램 1. 힐베르트 프로그램 1-1. 비유클리드 기하학과 러셀의 역설 1-1-1. 비유클리드 기하학의 등장 유클리드 기하학은 우리가 중학교에 입학하고 처음 배우는 바로 그 기하학과 관련이 깊다. 우리는 linocraft.tistory.com 괴델의 불완전성 정리를 시작하기 전에 잠깐 전에 했던 배경지식을 요약해보자. 유클리드 기하학으로 대표되는 수학적 사고방식은 참이라고 받아들이는 명제(공리)들과 논리적 추론 과정을 사용해 참인 명제(정리)를 만들어내는 작업이다. 그러나 비유클리드 기하학의 등장으로 인해 우리가 직관적으로 타당하다고 넘기는 공리들이 사실은 거짓일 수도 있다는 것이 드러나고.. 2024. 3. 17.
[컴퓨터의 기원] 1. 힐베르트 프로그램 1. 힐베르트 프로그램 1-1. 비유클리드 기하학과 러셀의 역설  1-1-1. 비유클리드 기하학의 등장 우리는 초등학교, 중학교 때 배우는 (유클리드) 기하학을 통해 "수학적으로 사고한다"는 것의 진정한 의미를 처음 배운다. 어떤 기하학적 진술이 있고 그것의 참을 증명해나가는 것을 배우는 것이 바로 수학적 사고다.예를 들어, "삼각형의 내각의 합은 180도이다."라는 진술은 기하학의 공리, 혹은 공리에서 증명된 정리를 활용해 아래처럼 엄밀하게 증명할 수 있다. 삼각형의 내각의 합이 180도인 이유(증명)초등학교 때 삼각형 모양의 색종이를 이용하여 삼각형의 세 내각의 크기의 합이 180도인 것을 배웠어요. 즉 아래의 그림에서처럼 삼각형의 세 각의 꼭짓점이 한 점에서 만나도록 이어 붙여보는susuni11.t.. 2024. 3. 17.

티스토리툴바