주요 정보

알고리즘은 원하는 결과를 얻기 위해 따라야 할 정의된 과정입니다. 우리 삶의 많은 부분이 알고리즘에 의해 결정됩니다. 어떤 알고리즘을 따라야 하는지 알면 더 효율적이고 효과적인 의사결정이 가능해집니다.

삶에서의 알고리즘

최근에 다시 읽었어요 Algorithms to Live By브라이언 크리스천과 톰 그리피스가 쓴 책으로, 알고리즘이 우리 삶에서 더 효과적으로 살 수 있도록 돕는 방법에 관한 내용입니다. 작년에 프로그래밍을 시작하면서 이번에는 더 많은 것을 얻었습니다.

알고리즘은 과정이며, 어떤 작업을 완료하기 위해 따라야 할 지침으로 생각할 수 있습니다. 예를 들어, 숫자를 더하는 법을 배우는 것은 간단한 알고리즘입니다 ¹.

더 복잡한 지침은 인생의 다른 문제에 대한 결과를 계산할 수 있습니다. 이자율, 웹 검색 순위, 소셜 미디어 피드 모두 알고리즘의 결과에 기반합니다. 책은 여러 알고리즘을 살펴보고, 개인적으로 마주할 수 있는 문제들과 연결짓습니다.

그들이 언급하는 모든 알고리즘을 설명하기는 너무 어렵습니다 ²그래서 대신 몇몇 인사에서 짧은 하이라이트를 작성하고, 보통은 정량적인 결론보다는 정성적인 핵심에 집중할 예정입니다.

또한 대부분의 알고리즘은 특정 가정에 의존합니다; 매번 명시하기보다는 읽을 때 그것을 당연한 것으로 받아들이세요. 관심 있는 분들을 위해 각주에 몇 가지 가정을 추가하겠습니다.

논의된 문제들 중 일부는 다음과 같습니다:

• 최상의 결과를 얻기 위해 언제 면접을 중단해야 할까요
• 이미 알고 있는 것을 즐기기 위해 새로운 선택지를 탐색하는 것을 멈춰야 할 때가 언제
• 목표에 따라 업무를 스케줄링하는 방법

이제 문제를 언제 멈춰야 하는지에 대한 첫 번째 알고리즘을 살펴보겠습니다.

최적 정지

구직자, 주택 제안, 주차 공간 등 여러 옵션을 평가할 때, 선택하는 데 소요하는 시간과 ‘최선의’ 선택지를 선택할 확률 사이에 상충관계가 있습니다. 이를 다음과 같이 합니다. secretary problem - 비서를 고용한다면, 최고의 비서를 찾을 기회를 얻으려면 몇 번의 면접을 봐야 할까요?

이 경우에는 정확한 비율이 있습니다. 지원자 풀의 37%를 본 후 기다렸다가 다음으로 좋은 지원자를 뽑아야 합니다 ³. 예를 들어, 지원자가 100명이라면 처음 37명을 보고 나서 지금까지 본 지원자보다 더 나은 다음 지원자를 선택하세요.

그것이 수학적으로 가장 적합한 인재를 뽑을 가능성이 가장 높은 지점입니다. 너무 일찍 그만두면 나중에 면접을 놓칠 수 있습니다. 너무 늦게 그만두면 시간을 낭비하게 됩니다 ⁴.

익스플로잇 탐색

최적 정지 상황과 비슷하게, 정보 수집(탐색)과 즐기기(익스플로잇) 사이에 트레이드오프가 있습니다. 예를 들어, 카지노에 있고 어떤 기계를 플레이할지 결정하고 싶다고 가정해 봅시다. 당첨금을 극대화하고 싶지만, 기계의 정확한 배당률을 모른다면(만약 알았다면 가장 좋은 기계를 선택할 것입니다).

이 경우, 다음과 같은 숫자가 있습니다. Gittins Index, 이 조합이 최적의 게임을 제공합니다 ⁵. 승리, 패배 횟수, 그리고 미래 이익을 얼마나 중요하게 생각하는지 알면 각 선택에 대해 정확한 값을 계산할 수 있습니다. 흥미로운 특성들:

• 최적의 머신을 플레이하고 다시 이기면, 그 머신을 계속 플레이하는 것이 합리적입니다
• 최적의 머신을 플레이하다가 한 번 졌다면, 그 머신을 계속 플레이하는 게 더 합리적일 수 있습니다
• 완전히 알려지지 않은 기계는 자주 이기는 기계보다 더 나을 수 있고, 그 알려지지 않은 기계는 미래의 이익을 더 중요하게 생각할수록 더 가치가 높아집니다

기타 관련 함의들:

• 탐험은 어릴 때 더 큰 영향을 미칩니다; 아기들이 모든 것을 입에 넣는 것은 그들의 입장에서 이해가 됩니다
• 착취는 인생 후반에 더 큰 영향을 미친다; 그래서 노인들은 사회적 네트워크를 줄이고 좋아하는 식당으로 돌아가는 것을 선호한다

분류

책에서는 프로그래밍에서 흔히 사용되는 정렬 알고리즘의 몇 가지 예시를 제시했습니다. 예를 들어, 검색 결과를 반환하려면 당신에게 가장 관련성 높은 결과를 정렬해야 합니다.

정렬 알고리즘에 대한 자세한 논의는 이해가 필요하니 다음 기회로 미루겠습니다 time complexity. 다음은 몇 가지 정성적 결론입니다:

• 정렬 방식에 따라 다른 방법보다 훨씬 효율적일 수 있습니다(>10배 빠름)
• 어떤 상황은 정렬 효율성만을 요구하지 않습니다. 예를 들어, 스포츠 시즌 매치업 달력을 계획할 때는 시즌이 얼마나 흥미로울지도 고려해야 합니다. 정렬 효율성을 최적화할 수는 있지만, 시즌이 덜 흥미롭게 느껴질 것입니다
• 더 효율적인 정렬일수록 실수에 더 취약해질 수 있습니다. 예를 들어, ‘최고’ 팀이 월드컵 같은 단판 토너먼트(사실상 정렬 알고리즘)에서 실수로 탈락할 수 있습니다 ⁶.

캐싱과 메모리

캐시의 개념은 1) 작고 빠른 메모리(저장) 섹션과 2) 크고 느린 메모리 섹션을 갖는 것입니다. 그 후 의도에 따라 두 가지를 번갈아 가며 사용할 것입니다. 이렇게 하면 원하는 활동에 대해 일정 속도와 크기 모두를 얻을 수 있습니다.

예를 들어, 좋아하는 옷은 옷장에 있고, 사용하지 않은 옷은 다락방에 있을 수 있습니다. 가장 많이 쓴 옷은 빠르게 꺼낼 수 있지만, 원한다면 못생긴 크리스마스 스웨터를 넣을 공간도 남을 수 있습니다. 캐시는 복잡해 보일 수 있지만, 우리는 일상 대부분에서 자연스럽게 저장을 합니다.

어떤 아이템을 빠른 섹션에 넣을지, 어떤 아이템을 느린 섹션에 넣을지 어떻게 결정하나요? 무작위 아이템, 최신 아이템, 가장 큰 아이템 등을 넣을 수도 있습니다.

이 경우, 가장 최근에 사용한 아이템을 작고 빠른 구역에 두는 것이 최적의 선택입니다. 이는 다음과 같은 이유로 temporal locality. 최근에 사용한 무언가가 다시 필요할 가능성이 더 큽니다. 예를 들어, 구글 드라이브는 자주 사용하는 파일을 하이라이트해 빠르게 접근할 수 있게 합니다.

일정

대부분의 사람들은 할 일 목록에서 우선순위를 정하는 방법을 결정해야 합니다. 이는 보통 응답 속도(응답 속도)와 처리량(얼마나 많은 일을 할 수 있는지) 사이의 균형을 요구합니다.

일정 관리와 우선순위 설정에서 중요한 점은 목표 지표를 정의하는 것입니다. 이는 어떤 알고리즘을 사용할지 결정하기 때문입니다 ⁷. 반응 속도를 극대화하려면 할 수 있는 업무량이 줄어듭니다:

모든 프로젝트의 최대 지연을 최소화하고 싶다면 ⁸, 그 Earliest Due Date 알고리즘은 가장 먼저 마감한 프로젝트부터 시작하라고 알려줍니다.

총 완료 시간을 최소화하고 싶다면, Shortest Processing Time 알고리즘은 가장 빠른 작업을 먼저 하라고 알려줍니다.

만약 작업의 중요성이 같지 않다면, 각 작업에 가중치를 두고 시간 대비 가중치 비율을 계산하면 어떤 작업을 할지 결정하는 데 도움이 됩니다; 시간 대비가 가장 높은 프로젝트를 선택하세요.

실질적으로, 이는 팀이 이 트레이드오프에 대해 어떻게 생각하는지, 그리고 어떤 방식을 선호하는지 매니저와 대화하는 것이 아마도 가치 있음을 의미합니다.

스케줄링에서 또 다른 중요한 개념이 있는데, 그것은 context switching - 작업 간 전환이 필요할 때. 문맥 전환은 실제 작업이 아니기 때문에 시간 낭비이지만, 당신 쪽에서 시간과 노력을 많이 들여줘요.

예를 들어, 이메일을 작성하다가 슬랙 메시지에 방해받았다면, 슬랙 메시지에 답장하는 데 시간이 걸리고, 이메일에 대해 무엇을 하려는지 기억하는 데 시간이 걸립니다.

최악일 때는 맥락 전환이 스래시로 전환되는데, 전환에만 너무 집중해서 생산적인 일을 하지 못할 때입니다. 스래시를 피하는 방법들은 다음과 같습니다:

• 과제에 ‘아니오’라고 말하는 것, 저자들은 우리가 종종 그렇게 할 수 없다는 점을 인정한다
• 더 멍청하고 비효율적으로 일하는 것. 최적 방법으로 일을 처리하는 대신, 그냥 무언가를 시작해서 끝내세요

베이즈 규칙과 분포

베이즈 법칙을 설명하려면 아마도 한 편의 기사가 필요할 테니, 어떤 일이 일어날 가능성을 예측하는 데 도움이 되는 규칙으로 받아들이죠 ⁹. 저자들이 강조하고자 하는 점은 이것이 당신의 이벤트가 어떤 분포에서 발생하는지에 따라 달라진다는 것입니다. 생각해야 할 주요 분포는 세 가지가 있습니다:

• 멱법칙: 어떤 일이 오래 지속될수록 더 오래 지속될 것으로 기대합니다. 예를 들어, 한 회사가 오랫동안 성장해왔다면, 우리는 그 회사가 계속 성장할 것으로 기대합니다
• 일반: 초기 사건은 놀라우고, 늦은 사건은 예상된다. 예를 들어, 우리는 인생 초기에 죽는 사람에게는 놀라움을 느끼지만, 늦게 죽는 사람은 놀라지 않는다.
• 얼랑: 사건은 결코 더 놀랍거나 덜 놀랍지 않다. 예를 들어, 룰렛 휠의 기억 없는 분배나 the coin flips we discussed last week

게임 이론

대부분의 사람들은 아마도 게임 이론이라는 개념을 들어본 적이 있을 텐데, 이는 게임을 할 때 최적의 전략이 무엇인지 생각하는 방식입니다. 몇 가지 주요 내용:

• 상대보다 너무 높은 레벨로 플레이하면 상대가 실제로는 모르는 정보를 가지고 있다고 생각하게 되고, 상대는 당신이 원하는 생각을 하지 못하게 됩니다. 다시 말해, 당신은 얻고 싶지 않습니다 너무 전략을 똑똑하게 써
• 모든 2인 게임에는 최소 한 명씩 존재합니다 Nash Equilibrium, 두 플레이어가 스스로 최적의 전략을 선택하는 경우입니다
• 하지만 내쉬 균형을 찾는 것은 해결하기 어려운 문제이며, 이는 게임 이론의 실용성에 한계가 있음을 의미합니다
• 균형이 모든 플레이어에게 최선의 결과가 아닐 수도 있습니다. It may be optimal for an individual to compete, but optimal for the group to cooperate. 이를 ‘무정부주의 대가’로 정량화할 수 있는데, 이는 협력과 경쟁 사이의 격차를 측정합니다.
• 또한 직관에 반하는 개념도 있습니다 mechanism design, 이는 다음을 보여준다. 악화되고 있다 모든 결과가 오히려 균형을 변화시켜 모두를 더 좋게 만들 수 있습니다

위에서 언급한 알고리즘 외에도, 저자들은 다음을 다룹니다:

• 의사결정 과정을 과적합하게 만들고 있을 때와 그에 대해 할 수 있는 일은 언제 이루어졌는지
• 현실 문제들이 이론만큼 좋지 않을 때 무엇을 해야 하는지, 그리고 왜 제약을 완화해야 하는지
• 정보 네트워킹과 인터넷이 어떻게 작동하는지에 대해 어떻게 생각해야 할까요

전반적으로 이 책은 알고리즘이 삶에서 흥미로운 방식으로 나타나는 방식을 개관적으로 이해하기 위해 읽을 가치가 있다고 생각했습니다. 그래서 더 잘 이해했습니다 이후 다만 컴퓨터 과학을 배우고 있으니 그 점을 염두에 두세요. 또한 실용적인 예제가 좀 더 포함되어 있었으면 좋았을 텐데요 ¹⁰, 왜냐하면 다양한 가정을 기반으로 한 결과물을 삶에 적용하려고 하기 어렵기 때문입니다.

Footnotes

1. 아이들에게 계산을 외우고 언제 숫자를 가져가야 하는지 알려주는 것은 쉽지만, 컴퓨터로 구현할 때는 놀랍게도 명확하지 않습니다. full adder logic gate ↩

2. 내가 모든 걸 설명할 때쯤이면 이미 설명한 거나 다름없다고 말할 수도 있겠죠 written the entire book ↩

3. The percentage is 1 divided by e, euler’s number. 지원자 풀이 커져도 확률은 변하지 않지만, 주에 따라 정보가 달라집니다 ↩

4. 기지 비서 문제는 거절한 후보자에게 다시 돌아갈 수 없다는 전제이지만, 현실과 좀 더 비슷한 변형도 있습니다. ↩

5. 이 문제는 기계에서 보상이 발생할 확률이 시간에 따라 변하면 해결 불가능하다; 즉, 해결 불가능하다는 뜻이다. 어떤 문제들은 해결하기 어렵다. 이런 경우, 일부 제약을 완화하고 “충분히 근접한” 해법을 받아들이는 것이 문제 구조에 큰 도움이 된다. ↩

6. 또는 미국인들은 3월 광란을 겪었다 ↩

7. 전체 일정 문제 중 효율적으로 해결할 수 있는 문제는 9%에 불과합니다. ↩

8. 즉, 지연된 모든 프로젝트를 보고, 그 중 최대치를 기준으로 하세요. 그게 가장 줄여야 할 지표입니다. ↩

9. 참고 here 베이즈 원칙을 설명하는 글을 위해서요. 베이즈 원칙은 (적어도 저에게는) 직관적이지 않아요. 그래서 알아두는 것도 좋은 일이에요 ↩

10. 공정하게 말하자면, 각주에 더 자세히 설명하는 정보가 꽤 많습니다 ↩

토론

What did I miss?

사려 깊은 반론, 추가 근거, 문제를 바라보는 다른 시각을 환영합니다.

토론을 불러오는 중…

표시 이름

토론에 참여하기

Website

게시

비공개 대화를 원하시나요? Leon에게 이메일 보내기.

관련 글

효과적인 사전 검거 방법

그룹에 무슨 일이 잘못될 수 있는지 묻지 마세요

Risk & Decision Making · Nov 23, 2019 · 4 min read

과학에서의 재현성 위기

많은 대중 연구들이 사실이 아닌 것으로 드러난다

Risk & Decision Making · Feb 23, 2019 · 5 min read

더닝 온 더닝 크루거

데이비드 더닝이 자신이 대중화한 효과를 설명합니다

Risk & Decision Making · Feb 2, 2019 · 5 min read