<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Dowon Jeong on Medium]]></title>
        <description><![CDATA[Stories by Dowon Jeong on Medium]]></description>
        <link>https://medium.com/@jeongdowon?source=rss-ac0072c85d14------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*FU9ug6fYXeV2AuU-JrqoqA.jpeg</url>
            <title>Stories by Dowon Jeong on Medium</title>
            <link>https://medium.com/@jeongdowon?source=rss-ac0072c85d14------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 00:58:15 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@jeongdowon/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Readability]]></title>
            <link>https://jeongdowon.medium.com/readability-73cdb3491ef1?source=rss-ac0072c85d14------2</link>
            <guid isPermaLink="false">https://medium.com/p/73cdb3491ef1</guid>
            <dc:creator><![CDATA[Dowon Jeong]]></dc:creator>
            <pubDate>Tue, 16 Dec 2025 13:25:24 GMT</pubDate>
            <atom:updated>2025-12-20T01:26:30.154Z</atom:updated>
            <content:encoded><![CDATA[<p>코드를 잘 짠다는 것은 무엇일까? 나는 <strong>가독성이 좋은 코드를 만드는 것</strong>이라 생각한다. 그럼 가독성이 좋은 게 뭘까? 적은 두뇌 에너지만 사용해서 내용을 잘 이해할 수 있다면 나는 가독성이 좋다고 생각한다.</p><h4>가독성 좋은 코드의 장점</h4><p>일단 다른 개발자의 에너지와 시간을 아껴준다. 간결하고 가지런하게 정리되어 있는 코드를 읽다보면 기분이 좋다. 그 이유는 첫 번째로 잘 이해가 되서 좋고 두 번째로 내가 어디부터 수정 혹은 추가해야할지 빠르게 판단할 수 있어서 좋다.</p><h4>가독성이 안좋은 코드들</h4><p>가독성이 안좋은 코드의 예를 들어 본다.</p><pre>result = setUserInfo(info);</pre><p>setter 메소드에 리턴값이 존재하면 그 타입이 무엇일지 직관적으로 와닿지 않는다. 그래서 별로 궁금하진 않지만 함수 내부를 찾아가본다.</p><pre>public UpdateResult setUserInfo(UserInfo info) {<br>  if (info == null) return null;<br><br>  ...<br><br>  if (...) return UpdateResult.FAIL;<br><br>  ...<br><br>  repository.save(info);<br>  return UpdateResult.OK;<br>}</pre><p>리턴 타입이 enum이고 경우에 따라 null인 경우가 있다. enum은 OK이거나 FAIL일 수도 있다. 그럼 FAIL과 null은 무슨 차이일까? 혹시 exception이 발생하는 경우는 없을까? 결국 궁금하지 않은 setUserInfo 메소드를 다 읽어버렸지만 찝찝함을 지울 수 없다.</p><h4>가독성 안좋은 코드의 영향</h4><p>코드 파악/변경하는 시간이 늘어난다. 버그가 늘어난다. 장애가 늘어난다. 모두의 스트레스가 증가한다. 그 코드를 보기 싫어진다. 개발자 수가 늘어나도 개발 속도가 비례해서 증가하지 않는다. 오히려 로그함수처럼 증가율이 감소한다.</p><h4>가독성을 올리기 위한 현실적인 방법들</h4><p>가장 확실한 방법은 코드 잘 짜는 사람의 리뷰를 받는 것이다. 한두번이 아닌 여러 번 받아야한다. 주변에 신뢰할 만한 사람이 없다면 AI에게 ‘가독성 높은 코드로 리팩토링 해줘’라고 요청해야한다.</p><p>사실 개인의 의지와 노력이 필요하다. 좋은 코드들을 살펴보고 clean code와 같은 책도 쓰윽 읽어보면 좋지만 관심사가 아니라면 현실적으로 어렵다.</p><p>다음으로 회사 차원에서 노력이 필요하다. 빠른 개발 속도도 중요하지만 가독성 있는 코드를 짜는 노력에 대한 인정과 보상이 필요하다. 구체적인 방법은 아직 고민 중이다.</p><p>내가 느끼기에 가독성이 떨어진다면 직접 기여해야한다. 내일이 아닌 오늘 해야한다. 나중은 없다.</p><p>특정 주기마다(예: 1년) 과감하게 처음부터 다시 작성하는 것도 필요하다. 이미 누더기가 된 코드를 조금 고치기보다는 처음부터 깔끔하게 작성하는게 나을때도 있다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=73cdb3491ef1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Simplicity]]></title>
            <link>https://jeongdowon.medium.com/simplicity-6dff6cdc4985?source=rss-ac0072c85d14------2</link>
            <guid isPermaLink="false">https://medium.com/p/6dff6cdc4985</guid>
            <category><![CDATA[simplicity]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[backend-development]]></category>
            <dc:creator><![CDATA[Dowon Jeong]]></dc:creator>
            <pubDate>Fri, 12 Dec 2025 08:15:40 GMT</pubDate>
            <atom:updated>2025-12-16T12:39:28.038Z</atom:updated>
            <content:encoded><![CDATA[<p>나는 단순한 것을 좋아한다.</p><p>단순한 원리를 갖고 있는 무언가는 누구든 금방 이해할 수 있다. 호주로 놀러 간적이 있는데 방문이 열리지 않아 몇 분동안 당황한 적이 있다. 아무래 잠금장치를 풀고 손잡이를 아래로 내려도 열리지가 않아 고장난 줄만 알았다. 알고보니 문을 열려면 손잡이를 위로 올려야했다. 만약 손잡이가 아래로 내려가지 않았다면 더 빨리 방법을 찾았을 것 같다.</p><p>코드도 마찬가지이다. 의도가 모호하거나 불필요한 조건/비교가 많으면 한참 동안 고민하게 된다. 이상한 변수/함수명이나 현행화되지 않은 주석이 혼란을 낳기도 한다. 읽기 어렵고 긴 코드를 계속 보고 있자면 머리에 김이 피어오른다.</p><p>시스템도 다르지 않다. 기능이 많고 직관적이지 않은데다가 여러 기능이 베타적이지 않는 경우를 많이 본다. 이를 위한 매뉴얼을 만들고 읽어보라고 한다. 직관적인 시스템은 설명이 필요없다. 그걸 사용하는 사람은 금방 이해하게 되기 때문이다. 시스템 모니터링과 장애대응 시 복잡한 시스템은 복구 속도를 늦추고 개발자들을 우왕좌왕하게 만든다.</p><p>Go언어는 구글에서 C++의 복잡함을 극복하기 위해 만들어졌다. Goroutine에서 network I/O가 발생 시 별도 코드 작성 없이 epoll 등과 같은 non-blocking이 가능해진다. Java의 Netty를 좋아하지만 나는 더 단순하게 좋다. Goroutine을 실행하는 방법은 그냥 go func() {}이고 잘 종료하기 위해서는 WaitGroup을 이용한다. Java의 new Thread(runnable).start()보다 단순해서 좋다.</p><p>단순함은 여기서 그치지 않는다. Russ Cox는 단순함은 생산성을 올리고 신뢰성을 올린다고 말했다. 단순한 Software는 개발자들이 빨리 이해하고 쉽게 대화하고 누구나 잘 알게 된다.</p><p>금융 시스템은 복잡하다. 그렇기 때문에 더 단순해져야한다. 이는 개발자와 기획자, 그리고 사용자 모두를 위한 길이다. 회사에서 내가 주로 하는 일은 모호하거나 복잡한 일을 단순하게 바꾸는 일이다.</p><p>참고</p><p><a href="https://learning.acm.org/bytecast/ep78-russ-cox">https://learning.acm.org/bytecast/ep78-russ-cox</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6dff6cdc4985" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[프로그래밍 언어를 공부하면 무엇이 좋은가?]]></title>
            <link>https://jeongdowon.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EC%96%B8%EC%96%B4%EB%A5%BC-%EA%B3%B5%EB%B6%80%ED%95%98%EB%A9%B4-%EB%AC%B4%EC%97%87%EC%9D%B4-%EC%A2%8B%EC%9D%80%EA%B0%80-3654fca39fca?source=rss-ac0072c85d14------2</link>
            <guid isPermaLink="false">https://medium.com/p/3654fca39fca</guid>
            <category><![CDATA[개발자]]></category>
            <category><![CDATA[자바]]></category>
            <category><![CDATA[프로그래밍]]></category>
            <dc:creator><![CDATA[Dowon Jeong]]></dc:creator>
            <pubDate>Wed, 09 Jan 2019 13:28:14 GMT</pubDate>
            <atom:updated>2019-01-09T13:28:14.625Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*CfqRNS1qswg_ehHe" /><figcaption>Photo by <a href="https://unsplash.com/@toddquackenbush?utm_source=medium&amp;utm_medium=referral">Todd Quackenbush</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>프로그래밍 언어는 그닥 중요하지 않다는 말에 반은 동의하고 반은 동의할 수 없다. 전자는 소프트웨어는 언어와 독립적인 내용이 많기 때문이고 후자는 프로그램 자체가 언어로 표현되기 때문이다.</p><p>다른 언어를 사용할 때 그 언어의 철학과 디자인을 배우게 된다. 이것은 종종 이전에 다른언어로 짠 내 코드의 문제를 알게 해주고 나은 코드를 만드는데 도움을 주었다.</p><p><strong>쉽게말해, 자바만 잘 써도 훌륭하지만 다른 언어도 해보면 더 나은 자바 코드를 짤 수 있다라고 생각한다.</strong> 자기만의 편협된 습관이나 컨벤션을 깨뜨릴 수 있는 건 덤이다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3654fca39fca" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[다수 원소(Majority Element) 찾기]]></title>
            <link>https://jeongdowon.medium.com/%EB%8B%A4%EC%88%98-%EC%9B%90%EC%86%8C-majority-element-%EC%B0%BE%EA%B8%B0-d6b7f4d77f38?source=rss-ac0072c85d14------2</link>
            <guid isPermaLink="false">https://medium.com/p/d6b7f4d77f38</guid>
            <category><![CDATA[알고리즘]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[majority-vote]]></category>
            <category><![CDATA[다수원소찾기]]></category>
            <dc:creator><![CDATA[Dowon Jeong]]></dc:creator>
            <pubDate>Fri, 04 Jan 2019 09:59:51 GMT</pubDate>
            <atom:updated>2019-01-04T10:03:02.033Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4uCsJ3mpd6IAAR8XhoydFw.jpeg" /><figcaption>여기 갈비탕 고기 많이 준다. (을지로 우촌)</figcaption></figure><p>어떤 배열에 과반수 이상 존재하는 원소가 있다면 그 원소를 찾고 싶다. 어떻게 찾을 수 있을까? <a href="https://practice.geeksforgeeks.org/problems/majority-element/0">여기</a>서 직접 코딩 해보자.</p><h3>1. 무작정 루프 돌리기</h3><p>가장 직관적인 방법으로, 이중 반복 하므로 시간복잡도는 O(n²) 이고 공간복잡도는 O(1)이다.</p><h3>2. 정렬해서 찾기</h3><p>정렬하고 차례대로 현재 원소가 과반수를 넘었는지 확인하는 방법이다. 시간복잡도는 O(nlogn), 공간복잡도는 O(1)이다. 1번 방법보다 더 효율이 좋다.</p><h3>3. 해쉬맵 이용하기</h3><p>반복문을 돌면서 &lt;원소, 횟수&gt;를 기록해나간다. 횟수가 과반수를 넘었다면 바로 그 원소가 내가 찾는 원소이다. 시간복잡도는 O(n), 시간복잡도는 O(n) 이다. 메모리 효율을 포기하고 속도를 높혔다.</p><pre>from collections import Counter</pre><pre>for t in range(int(input())):<br>    _ = input()<br>    nums = list(map(int, input().split()))<br>    c = Counter()<br>    res = -1<br>    for num in nums:<br>        c[num] += 1<br>        if c[num] &gt; len(nums)//2:<br>            res = num<br>            break<br>    print(res)</pre><h3>4. 더 나은 방법</h3><p>3번 방법이 최선인가? ‘<a href="https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm">Boyer-Moore majority vote algorithm</a>’ 을 이용하는 방법이 있다. 결론부터 말하면 시간복잡도 O(n), 공간복잡도 O(1)이다. 아래 코드에서 find_candidate()가 핵심이라고 볼 수 있다. 이 함수는 다수 원소가 있다는 가정하에 정상적으로 동작하기 때문에 is_majority()로 검증이 필요하다.</p><p>간단하게 설명하면, ‘<strong>다수 원소의 출현횟수의 총합은 나머지 원소의 출현횟수보다 많다’</strong>라는 원리를 이용한 것이다.</p><pre>def find_candidate(nums: list)-&gt;int:<br>    cand = nums[0]<br>    cnt = 1<br>    for i in range(1, len(nums)):<br>        if nums[i] == cand:<br>            cnt += 1<br>        else:<br>            cnt -= 1<br>            if cnt == 0:<br>                cand = nums[i]<br>                cnt = 1<br>    return cand</pre><pre>def is_majority(nums: list, candidate: int)-&gt;bool:<br>    cnt = 0<br>    for num in nums:<br>        if num == candidate:<br>           cnt += 1<br>           if cnt &gt; len(nums)//2:<br>               return True<br>    return False<br>    <br>    <br>for t in range(int(input())):<br>    _ = input()<br>    nums = list(map(int, input().split()))<br>    candidate = find_candidate(nums)<br>    if is_majority(nums, candidate):<br>        print(candidate)<br>    else:<br>        print(-1)</pre><p>실무에서 쓰일 만한 내용일까 생각해봤다. 과반수 이상을 차지하는 무언가를 찾아야 할만 상황이 무엇이 있을까? 땅따먹기 게임에서 절반이상을 먹으면 게임이 종료되는 상황에 쓸 수 있을 것 같다. ㅋㅋㅋ</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d6b7f4d77f38" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Unicode와 UTF-8 간단히 이해하기]]></title>
            <link>https://jeongdowon.medium.com/unicode%EC%99%80-utf-8-%EA%B0%84%EB%8B%A8%ED%9E%88-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-b6aa3f7edf96?source=rss-ac0072c85d14------2</link>
            <guid isPermaLink="false">https://medium.com/p/b6aa3f7edf96</guid>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[unicode]]></category>
            <category><![CDATA[utf-8]]></category>
            <dc:creator><![CDATA[Dowon Jeong]]></dc:creator>
            <pubDate>Tue, 01 Jan 2019 12:06:40 GMT</pubDate>
            <atom:updated>2021-01-02T08:49:52.596Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Cxg016xTbDcghUeQ" /><figcaption>Photo by <a href="https://unsplash.com/@fotodisiac?utm_source=medium&amp;utm_medium=referral">Genie Austin</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>유니코드(Unicode)</h3><p>옛날옛날 컴퓨터가 세상에 나왔을 때는 ‘영어’와 몇가지 ‘특수문자’만 사용했고 이를 저장하기 위해서 1 byte면 충분했다. (0~255) 시간이 흘러 다른 국가 사람들이 컴퓨터를 이용하다보니 자국어도 컴퓨터로 표시하고 싶어졌다. 그래서 1 byte 안에 임의대로 알파벳 대신 자기나라 글자를 할당해서 그럭저럭 쓸 수는 있었다. 그러나 네트워크가 발전하고 다른 사람 홈페이지를 들어갔더니 글자가 와장창 깨지고 만다. 그리하여 국제적으로 전세계 언어를 모두 표시할 수 있는 표준코드를 만들기로 했다. 바로 유니코드(Unicode)다. 참고로, 한글 ‘가’는 유니코드로 ‘U+AC00’이다. 왜 그러냐고 이유는 묻지마라. 약속이다.</p><blockquote>유니코드는 글자와 코드가 1:1매핑되어 있는 ‘코드표&#39;이다. (<a href="https://ko.wikipedia.org/wiki/%EC%9C%A0%EB%8B%88%EC%BD%94%EB%93%9C_%EC%98%81%EC%97%AD">코드표</a>)</blockquote><h3>UTF-8</h3><p>유니코드를 통해 코드표가 정의되었다. 남은 것은 그 ‘코드&#39;가 컴퓨터에 어떻게 저장되어야 하는 것이다. 다른 말로 인코딩(encoding)이라고 하는데, 컴퓨터가 이해할 수 있는 형태로 바꿔주는 것이다. 예를 들어, 길동이가 자기만의 암호체계를 만들었는데 ‘가&#39;는 0001(=1)로, ‘나&#39;는 0010(=2)이라고 하자. 길동이가 ‘가나나가&#39;라고 말하면 컴퓨터에는 0001 0010 0010 0001로 저장한다. 글자당 1 byte로 할당해 4 byte로 저장할 수 있고 00010010 00100001처럼 2byte로 저장할 수도 있다. 이건 전적으로 길동이와 컴퓨터간의 약속이다. 길동이만 쓸 때는 문제가 없는데 전세계 사람들이 사용하려면 좀 더 잘 만들어야 할것이다.</p><blockquote>UTF-8은 유니코드를 인코딩(encoding)하는 방식이다. 전세계에서 사용하는 약속이다.</blockquote><p>UTF-8은 가변 인코딩방식이다. 쉬운 말로 하면 글자마다 byte 길이가 다르다는 것이다. ‘a’는 1 byte이고 ‘가&#39;는 3 byte이다. 가변을 구분하기 위해 첫 바이트에 표식을 넣었는데 2 byte는 110으로 시작하고 3바이트는 1110으로 시작한다. 나머지 바이트는 10으로 시작한다. 왜 그러냐고 묻는다면, 그냥 ‘약속이다’라고 말하고 싶다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A6GcpKbbG-u6ps66f_rEjg.png" /><figcaption>출처: 위키피디아</figcaption></figure><h3>코딩</h3><p>Go를 이용하면 다른 프로그래밍 언어보다 좀 더 직관적으로 확인 할 수 있다. Go는 에디터에서 작성한 모든 문자열을 UTF-8로 인코딩하는데 이 문자열을 반복문으로 처리할 때 첫 번째 인자로 글자시작 byte의 index를 가져온다. 타언어들의 경우, 문자열에 대한 글자의 index를 가져오는데 Go는 이 부분을 보다 명확하게 한 것이다. 두 번째 인자는 int32 (혹은 rune이라고도 한다) 타입의 실제 인코딩된 데이터이다.</p><pre><strong>package </strong>main<br><br><strong>import </strong>&quot;fmt&quot;<br><br><strong>func </strong>main() {<br><br>   word := <strong>&quot;abc가나다&quot;<br>   for </strong>i, r := <strong>range </strong>word {<br>      fmt.Printf(<strong>&quot;%d %d 0x%x %c\n&quot;</strong>, i, r, r, r)<br>   }<br>   fmt.Println()<br>   <strong>for </strong>i := 0; i &lt; len(word); i++ {<br>      fmt.Printf(<strong>&quot;%d(%c) &quot;</strong>, word[i], word[i])<br>   }<br>}</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*bqIpaKp1PtOEEWfdxdXqWw.png" /><figcaption>실행 결과</figcaption></figure><p>알파벳의 경우, UTF-8 인코딩 시 1 byte를 차지하므로 1씩 증가한다. 하지만 한글의 경우, 3 byte를 차지하므로 3씩 증가한다. int32는 총 4 byte로 유니코드의 모든 문자를 표현한다. 재미있는 건, word[i]로 접근하게 되면 uint8 타입의 데이터가 나오는데 바로 byte이다. 그래서 한글의 경우, 1 byte씩 읽게 되면 ASCII 코드를 읽게된다.</p><p><strong>유니코드는 국제표준 문자표이고 UTF-8은 인코딩 방식이다.</strong> 구글링 하다보면 이에 대한 굉장히 많은 자료가 있지만 오히려 그 방대한 내용때문에 기본적인 개념이 헷갈리기도 한다. 헷갈린 사람에게 조금이나마 도움이 되었으면 좋겠다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b6aa3f7edf96" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[알고리즘] Backtracking 이해하기]]></title>
            <link>https://jeongdowon.medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-13492b18bfa1?source=rss-ac0072c85d14------2</link>
            <guid isPermaLink="false">https://medium.com/p/13492b18bfa1</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[dfs]]></category>
            <category><![CDATA[백트래킹]]></category>
            <category><![CDATA[backtracking]]></category>
            <category><![CDATA[알고리즘]]></category>
            <dc:creator><![CDATA[Dowon Jeong]]></dc:creator>
            <pubDate>Sat, 29 Dec 2018 14:05:07 GMT</pubDate>
            <atom:updated>2019-01-01T06:32:56.254Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*e4rCQ1mwAhz1epuj" /><figcaption>Photo by <a href="https://unsplash.com/@rawpixel?utm_source=medium&amp;utm_medium=referral">rawpixel</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>알고리즘에서 <strong>백트래킹(Backtracking)</strong>이라는 말이 나온다. 이름만 들어서는 정확히 무엇을 말하는지 알기 어렵다. 뒤로 추척을 한다는 건가? 구글링을 해보면 ‘퇴각검색&#39;이라는 더 아리송한 단어가 나온다. 위키피디아 정의에 따르면 아래와 같다.</p><blockquote><strong>“Backtracking</strong> is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems…”</blockquote><p>백트래킹은 일반적인 알고리즘 중 하나이다. 마지막에 나온 말이 중요한데, <strong>CSP(Constrain Satisfaction Problems)을 해결하기 위해 쓰인다는 것이다.</strong> 백트래킹을 이해하려고 했더니 CSP를 이해해야 하는 상황이 되었다. 위키피디아 정의는 아래와 같다.</p><blockquote><strong>“Constraint satisfaction problems</strong> (<strong>CSPs</strong>) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations.”</blockquote><p>한국어로 하면 ‘조건 만족 문제&#39;인데, 일단은 넘어가고 이후에 다시 살펴보자. ‘The Algorithm Design Manual’ 책에는 백트레킹에 대해서 다음과 같이 말하고 있다.</p><blockquote>“A technique for listing all possible solutions for a combinatorial algorithm problem.”</blockquote><p>좀 더 이해하기 쉽다. 백트래킹은 어떤 테크닉인데 ‘조합 알고리즘 문제’에 대해 모든 가능한해를 나열하는 것이다. 그렇다. <strong>백트래킹은 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만이다</strong>. 모든 경우의 수를 모두 찾는 것보다 ‘경우에 따라&#39; 훨씬 빠를 수 있다. 왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문이다.</p><p>구체적인 예를 들어보자. 정렬되어 있지 않은 숫자 리스트 중에 특정 숫자를 찾는 것은 n을 리스트 길이라고 했을 때, O(n) 시간 복잡도를 갖는다. 이 경우에는 백트래킹은 의미가 없다. 한 개씩 모두 살펴볼 수 밖에 없기 때문이다. 반면 <a href="https://www.acmicpc.net/problem/9663">N-Queen 문제</a>의 경우는 다르다.</p><blockquote>N * N 체스판에 최대한 많은 Queen을 놓고 싶다. 다만, 서로를 공격하지 않게 올려놓고 싶다. 총 몇 가지 경우의 수가 있을까?</blockquote><p>체스를 잘 모르는 사람도 있으니 부연을 하자면, Queen은 동서남북 직진 뿐 아니라 대각선으로도 이동할 수 있다. 자 이제 어떻게 경우의 수를 셀 것인가? 가장 쉬운 방법은 모든 조합의 경우를 세는 것이다. 체스판 왼쪽부터 Queen을 차례대로 두면 상식적으로 한 컬럼에 하나의 Queen 밖에 둘 수 없다는 것을 쉽게 알 수 있다. (위아래로 움직이니깐) 다시 말하면, N * N 체스판에 N개의 Queen을 올려놓는 경우의 수를 계산해야 한다. 계산해보면,</p><blockquote><strong>모든 경우의 수 = 컬럼의 수 ^ 한 컬럼에 Queen을 놓는 경우의 수 = N ^ N (Power N of N)</strong></blockquote><p>시간 복잡도는 O(N^N)으로 엄청나게 많은 조합이 존재한다. N = 10이면 무려 100억개이다.</p><p>이제 백트래킹을 이용해보자. 한 컬럼에 Queen을 두었으면 오른쪽 컬럼에 가능한 자리에 Queen을 둔다. 또 다시 오른쪽 컬럼 중에서 가능한 자리에 Queen을 둔다. 이 과정을 반복한다. 만약에 N개의 Queen을 두었다면 카운트를 증가 시킨다. 이제부터가 중요한데, <strong>성공하기 직전으로 상태를 되돌린다(back)</strong>. 그리고 N번째 컬럼 중 다른 칸들을 시도한다. 만약에 없다면 N-1번째 컬럼에 있는 Queen을 들어서 다음으로 가능한 칸으로 옮긴다. 다시 N번째 컬럼에 Queen을 둘 수 있는 곳을 찾는다. N-1번째 컬럼의 모든 경우를 시도했다면, N-2번째로 되돌아가 다음으로 가능한 위치로 Queen을 옮긴다.</p><p>다시, 백트래킹의 정의로 되돌아가 N-Queen 문제에 대입해보자. Queen을 최대한 많이 두는 모든 경우의 수를 찾는다. 다만, 서로를 공격하지 않아야 하므로 k번째 컬럼에 넣는 Queen을 두려면 해당 위치에서 왼쪽과 왼쪽위 대각선, 왼쪽아래 대각선에 다른 Queen들이 없어야 한다. 이 조건은 앞에서 말한 한정 조건 (CSP)이 된다. 결과적으로, 한정조건을 이용한 검색은 모든 경우의 수를 검색하는 것보다 훨씬 경우의 수가 적다.</p><p>아래 코드는 1) 모든 경우를 탐색 2) 특정 조건 명시가 포함되어 있다. 모든 경우 탐색을 위하여 DFS를 사용하였고 특정 조건은 isValid()가 처리한다.</p><pre><strong>package </strong>main<br><strong>import </strong>(<br>   <strong>&quot;fmt&quot;<br></strong>)<br><strong>func </strong>main() {<br>   <strong>var </strong>N int<br>   fmt.Scanf(<strong>&quot;%d&quot;</strong>, &amp;N)<br>   grid := make([][]bool, N)<br>   <strong>for </strong>i := 0; i &lt; N; i++ {<br>      grid[i] = make([]bool, N)<br>   }<br>   fmt.Println(dfs(grid, 0))<br>}<br><br><strong>func </strong>dfs(grid [][]bool, x int) int {<br>   <strong>if </strong>x == len(grid) {<br>      <strong>return </strong>1<br>   }<br>   <strong>var </strong>cnt = 0<br>   <strong>for </strong>i := 0; i &lt; len(grid); i++ {<br>      <strong>if </strong>isValid(grid, x, i) {<br>         grid[i][x] = <strong><em>true<br>         </em></strong>cnt += dfs(grid, x+1)<br>         grid[i][x] = <strong><em>false<br>      </em></strong>}<br>   }<br>   <strong>return </strong>cnt<br>}<br><br><strong>func </strong>isValid(grid [][]bool, x, y int) bool {<br>   <strong>var </strong>diff int<br>   <strong>for </strong>j := x-1; j &gt;= 0; j-- {<br>      diff++<br>      <strong>if </strong>grid[y][j] || (y-diff &gt;= 0 &amp;&amp; grid[y-diff][j]) || (y+diff &lt; len(grid) &amp;&amp; grid[y+diff][j]) {<br>         <strong>return <em>false<br>      </em></strong>}<br>   }<br>   <strong>return <em>true<br></em></strong>}</pre><p>일반화 하면 아래와 같다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/786/1*Ivl32Ba6aUO04ysXyHq5wg.png" /><figcaption>The Algorithm Design Manual에서 인용</figcaption></figure><p>간단하게 백트래킹에 대해서 알아봤다. 조합의 숫자를 셀 때, 어떠한 조건들을 가지고 있다면, 모든 조합이 아닌 특정조건에 한정해서 조합을 카운트 할 수 있다. 검색 성능은 향상된다. 일반적으로 DFS(깊이 우선탐색)을 통하여 구현하는데 BFS(넓이 우선탐색)의 경우 상대적으로 많은 메모리가 필요하기 때문이다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=13492b18bfa1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[단어 개수 세는 프로그램 만들기]]></title>
            <link>https://jeongdowon.medium.com/%EB%8B%A8%EC%96%B4-%EA%B0%9C%EC%88%98-%EC%84%B8%EB%8A%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8-%EB%A7%8C%EB%93%A4%EA%B8%B0-e245e673100c?source=rss-ac0072c85d14------2</link>
            <guid isPermaLink="false">https://medium.com/p/e245e673100c</guid>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[go]]></category>
            <category><![CDATA[단어세기]]></category>
            <category><![CDATA[프로그래밍]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Dowon Jeong]]></dc:creator>
            <pubDate>Sun, 23 Dec 2018 07:34:49 GMT</pubDate>
            <atom:updated>2018-12-23T07:39:21.949Z</atom:updated>
            <content:encoded><![CDATA[<h3>단어 개수 세는 프로그램 만들기</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0Y70b_MUn7ApLYpG" /><figcaption>Photo by <a href="https://unsplash.com/@dearseymour?utm_source=medium&amp;utm_medium=referral">Ksenia Makagonova</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>책을 읽다보면 어떤 단어를 가장 많이 사용 하였는지 궁금할 때가 있다. 한 페이지 정도는 사람이 셀 수도 있다. 만약 한 권 혹은 여러 권의 책이라면 굉장히 오랜 시간이 걸릴 것이다. 나는 소프트웨어 개발자 임으로 직접 프로그래밍을 해보기로 했다.</p><p>프로그래밍을 하기 전에 어떤 프로그래밍 언어를 사용할지 골라야 한다. 나는 Go (혹은 Golang)를 사용하기로 하였다. Go 언어는 배우기 쉽고 가독성이 상대적으로 좋기 때문이다. (라고 썼지만 내가 좋아해서다 ^-^)</p><p>다음으로 책이 필요하다. 인터넷에 공개 되어있는 성경 파일을 발견하였고 그 중 창세기 1장을 복사해왔다. 각 절앞에 숫자가 있으므로 프로그래밍 시 제거해야한다.</p><blockquote>1태초에 하나님이 천지를 창조하시니라 2땅이 혼돈하고 공허하며 흑암이 깊음 위에 있고 하나님의 영은 수면 위에 운행하시니라 3하나님이 이르시되 빛이 있으라 하시니 빛이 있었고 4빛이 하나님이 보시기에 좋았더라 하나님이 빛과 어둠을 나누사 5하나님이 빛을 낮이라 부르시고 어둠을 밤이라 부르시니라 저녁이 되고 아침이 되니 이는 첫째 날이니라 <br>6하나님이 이르시되 물 가운데에 궁창이 있어 물과 물로 나뉘라 하시고 7하나님이 궁창을 만드사 궁창 아래의 물과 궁창 위의 물로 나뉘게 하시니 그대로 되니라 8하나님이 궁창을 하늘이라 부르시니라 저녁이 되고 아침이 되니 이는 둘째 날이니라 <br>9하나님이 이르시되 천하의 물이 한 곳으로 모이고 뭍이 드러나라 하시니 그대로 되니라 10하나님이 뭍을 땅이라 부르시고 모인 물을 바다라 부르시니 하나님이 보시기에 좋았더라 11하나님이 이르시되 땅은 풀과 씨 맺는 채소와 각기 종류대로 씨 가진 열매 맺는 나무를 내라 하시니 그대로 되어 12땅이 풀과 각기 종류대로 씨 맺는 채소와 각기 종류대로 씨 가진 열매 맺는 나무를 내니 하나님이 보시기에 좋았더라 13저녁이 되고 아침이 되니 이는 셋째 날이니라 <br>14하나님이 이르시되 하늘의 궁창에 광명체들이 있어 낮과 밤을 나뉘게 하고 그것들로 징조와 계절과 날과 해를 이루게 하라 15또 광명체들이 하늘의 궁창에 있어 땅을 비추라 하시니 그대로 되니라 16하나님이 두 큰 광명체를 만드사 큰 광명체로 낮을 주관하게 하시고 작은 광명체로 밤을 주관하게 하시며 또 별들을 만드시고 17하나님이 그것들을 하늘의 궁창에 두어 땅을 비추게 하시며 18낮과 밤을 주관하게 하시고 빛과 어둠을 나뉘게 하시니 하나님이 보시기에 좋았더라 19저녁이 되고 아침이 되니 이는 넷째 날이니라 <br>20하나님이 이르시되 물들은 생물을 번성하게 하라 땅 위 하늘의 궁창에는 새가 날으라 하시고 21하나님이 큰 바다 짐승들과 물에서 번성하여 움직이는 모든 생물을 그 종류대로, 날개 있는 모든 새를 그 종류대로 창조하시니 하나님이 보시기에 좋았더라 22하나님이 그들에게 복을 주시며 이르시되 생육하고 번성하여 여러 바닷물에 충만하라 새들도 땅에 번성하라 하시니라 23저녁이 되고 아침이 되니 이는 다섯째 날이니라 <br>24하나님이 이르시되 땅은 생물을 그 종류대로 내되 가축과 기는 것과 땅의 짐승을 종류대로 내라 하시니 그대로 되니라 25하나님이 땅의 짐승을 그 종류대로, 가축을 그 종류대로, 땅에 기는 모든 것을 그 종류대로 만드시니 하나님이 보시기에 좋았더라 26하나님이 이르시되 우리의 형상을 따라 우리의 모양대로 우리가 사람을 만들고 그들로 바다의 물고기와 하늘의 새와 가축과 온 땅과 땅에 기는 모든 것을 다스리게 하자 하시고 27하나님이 자기 형상 곧 하나님의 형상대로 사람을 창조하시되 남자와 여자를 창조하시고 28하나님이 그들에게 복을 주시며 하나님이 그들에게 이르시되 생육하고 번성하여 땅에 충만하라, 땅을 정복하라, 바다의 물고기와 하늘의 새와 땅에 움직이는 모든 생물을 다스리라 하시니라<br>29하나님이 이르시되 내가 온 지면의 씨 맺는 모든 채소와 씨 가진 열매 맺는 모든 나무를 너희에게 주노니 너희의 먹을 거리가 되리라 30또 땅의 모든 짐승과 하늘의 모든 새와 생명이 있어 땅에 기는 모든 것에게는 내가 모든 푸른 풀을 먹을 거리로 주노라 하시니 그대로 되니라 31하나님이 지으신 그 모든 것을 보시니 보시기에 심히 좋았더라 저녁이 되고 아침이 되니 이는 여섯째 날이니라</blockquote><p>책과 프로그래밍 언어가 준비되었다. 이제는 알고리즘을 고민해야 한다. 우선 생각나는 것을 적어보자.</p><ol><li>숫자를 제거한다. 성경에는 숫자는 장이나 절을 표시 하므로 굳이 셀 필요가 없다.</li><li>공백으로 단어를 구분하고 Hash Map을 이용해서 각 단어별 출현횟수를 기록한다. 단어의 개수가 n 이라고 하면 시간복잡도는 O(n) 이다.</li><li>공간복잡도는 모든 단어를 저장해야 하므로 단어의 개수를 n, 단어의 최대길이를 m이라고 할 때 O(n * m)이다. 한 가지 생각해봐야 할 점은, 유사한 단어를 모두 다른 단어로 저장해야 한다는 것이다. 예컨대 ‘생물과&#39;과 ‘생물을&#39;은 한 글자만 다르지만 다른 단어로 저장 해야만 한다.</li><li>여러 권의 책을 읽는 다면 메모리의 한계에 다다를 것이다. 적당히 읽고 기록하는 과정을 반복해야 한다. 물론 창세기 1장을 처리하는 것은 문제 없다.</li><li>Hash Map을 이용하지 말고 Trie를 이용하게 되면 read와 write의 성능이 O(1) → O(m)으로 떨어지는 문제가 있지만 공간복잡도를 낮출 수 있지 않을까? 저장해야 하는 데이터가 한글이므로 Trie의 각 노드는 ‘가&#39;부터 ‘핳&#39;까지 길이를 갖는 배열을 지니고 있어야 한다! 다행인건, 성경에서 나오는 단어의 길이는 아무리 길어봤자 10자를 넘지 않을 것이다.</li></ol><p>우선 Hash Map을 이용해서 간단하게 구현해보자.</p><pre><strong>import </strong>(<br>   &quot;bufio&quot;<br>   &quot;fmt&quot;<br>   &quot;os&quot;<br>   &quot;sort&quot;<br>   &quot;strings&quot;<br>)<br><br><strong>type </strong>Pair <strong>struct </strong>{<br>   Word string<br>   Count int<br>}<br><br><strong>func </strong>main() {<br>   bookString := readBook(&quot;genesis1.txt&quot;)<br>   words := strings.Split(bookString, &quot; &quot;)<br>   counter := countWords(words)<br>   showTopN(counter, 5)<br>}<br><br><strong>func </strong>countWords(words []string) <strong>map</strong>[string]int {<br>   counter := <strong>map</strong>[string]int{}<br>   <strong>for </strong>_, word := <strong>range </strong>words {<br>      counter[word]++<br>   }<br>   <strong>return </strong>counter<br>}<br><br><strong>func </strong>readBook(fileName string) string {<br>   <strong>var </strong>builder strings.Builder<br><br>   f, _ := os.Open(fileName)<br>   <strong>defer </strong>f.Close()<br>   sc := bufio.NewScanner(f)<br>   <strong>for </strong>sc.Scan() {<br>      builder.WriteString(sc.Text())<br>   }<br><br>   <strong>return </strong>builder.String()<br>}<br><br><strong>func </strong>showTopN(counter <strong>map</strong>[string]int, limit int) {<br>   pairs := make([]Pair, len(counter))<br>   <strong>for </strong>k, v := <strong>range </strong>counter {<br>      pairs = append(pairs, Pair{k , v})<br>   }<br>   sort.Slice(pairs, <strong>func</strong>(i, j int) bool {<br>      <strong>return </strong>pairs[i].Count &gt; pairs[j].Count<br>   })<br>   <strong>for </strong>i := 0; i &lt; limit; i++ {<br>      pair := pairs[i]<br>      fmt.Printf(&quot;%d. %s - %d번\n&quot;, i+1, pair.Word, pair.Count)<br>   }<br>}</pre><p>위 코드에는 숫자(절)를 제거하는 코드는 없는데 최대한 코드를 간단하게 표현하고 싶었다. 단어를 세는 로직은 map에 계속 더하는 것 외에는 없다. 오히려 TOP N을 표시하기 위해 count를 기준으로 정렬하는 과정에서 Pair라는 구조체를 추가 해야만 했다.</p><p>결과는 아래와 같다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/352/1*iQxu7Kf5kSWqS3IpG5ig1g.png" /><figcaption>top5 output</figcaption></figure><p>다음에는 Trie를 이용해서 구현해 볼 예정이다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e245e673100c" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>