<?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 Haeseok Lee on Medium]]></title>
        <description><![CDATA[Stories by Haeseok Lee on Medium]]></description>
        <link>https://medium.com/@haeseok?source=rss-2fd65d3e7098------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*eC7AV6ZVpOBs6Wr3F0reyA.jpeg</url>
            <title>Stories by Haeseok Lee on Medium</title>
            <link>https://medium.com/@haeseok?source=rss-2fd65d3e7098------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 13:22:23 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@haeseok/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[[프로그래머스] 동굴 탐험]]></title>
            <link>https://haeseok.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8F%99%EA%B5%B4-%ED%83%90%ED%97%98-a669d62f304d?source=rss-2fd65d3e7098------2</link>
            <guid isPermaLink="false">https://medium.com/p/a669d62f304d</guid>
            <category><![CDATA[카카오]]></category>
            <category><![CDATA[kakao]]></category>
            <category><![CDATA[프로그래머스]]></category>
            <category><![CDATA[python3]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Haeseok Lee]]></dc:creator>
            <pubDate>Sat, 25 Jul 2020 15:05:59 GMT</pubDate>
            <atom:updated>2021-05-30T06:36:44.716Z</atom:updated>
            <content:encoded><![CDATA[<h4>2020 카카오 인턴십 문제풀이 with Python3</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/1*1-mYKGXjF-g7EjX5klAddg.jpeg" /><figcaption>2020 카카오 인턴십</figcaption></figure><h3>문제링크</h3><p><a href="https://programmers.co.kr/learn/courses/30/lessons/67260?language=python3">코딩테스트 연습 - 동굴 탐험</a></p><h3>문제설명</h3><ul><li>0 번 부터 n-1 번까지 번호가 붙여져 있는 <strong>n개의 방으로 이루어진 동굴</strong>이 있다.</li><li>동굴에 들어가기 위한 <strong>유일한 입구는 0번 방</strong>이다.</li><li>각 방들은 <strong>양방향으로 통행이 가능</strong>하며 <strong>서로 다른 방을 연결하는 통로는 하나만 존재</strong>한다.</li><li>임의의 서로 다른 두 방 사이의 <strong>최단경로는 한 가지 경우</strong>밖에 없으며 두 방 사이에 <strong>이동이 불가능한 경우는 없다</strong>.</li><li><strong>방문했던 방은 재방문이 가능</strong>하다.</li><li><strong>적어도 한 번 모든 방을</strong> 방문해야 한다.</li><li>특정 방은 방문하기 전에 반드시 방문해야 하는 <strong>선방문 방</strong>이 정해져 있다. <br>( order 매개변수로 주어진다.)</li></ul><pre>order = [[8, 5], [6, 7], [4, 1]]</pre><pre><em># 8번방 방문 후에 5번방 방문   8 -&gt; 5<br># 6번방 방문 후에 7번방 방문   6 -&gt; 7<br># 4번방 방문 후에 1번방 방문   4 -&gt; 1</em></pre><ul><li>선방문 방과 후방문 방을 <strong>반드시 연속으로 방문해야할 필요는 없다.</strong></li></ul><pre>order = [[8, 5]]</pre><pre><em># 8번방 방문 후에 1번, 4번을 거쳐서 5번방 방문<br># 8 -&gt; 1 -&gt; 4 -&gt; 5</em></pre><ul><li>어떤 방을 방문하기 위한 <strong>선방문 방은 1개이거나 아예 없을 수도 있다.</strong> 다시말해, <strong>2개 이상인 경우는 주어지지 않는다.</strong></li></ul><pre>order = [[8, 5], [1, 5], [3, 5]]</pre><pre><em># 8번방 방문 후에 5번방 방문   8 -&gt; 5<br># 1번방 방문 후에 5번방 방문   1 -&gt; 5<br># 3번방 방문 후에 5번방 방문   3 -&gt; 5</em></pre><ul><li>어떤 임의의 방들에 대해서 <strong>선방문 해야되는 방이 겹치는 경우</strong>는 주어지지 않는다.</li></ul><pre>order = [[8, 5], [8, 4], [8, 1]]</pre><pre><em># 8번방 방문 후에 5번방 방문   8 -&gt; 5<br># 8번방 방문 후에 4번방 방문   8 -&gt; 4<br># 8번방 방문 후에 1번방 방문   8 -&gt; 1</em></pre><ul><li><strong>선방문인 방 이면서 동시에 후방문인 방인 경우</strong>는 주어지지 않는다.</li></ul><pre>order = [[8, 5], [5, 4], [4, 6]]</pre><pre><em># 8번방 방문 후에 5번방 방문   8 -&gt; 5<br># 5번방 방문 후에 4번방 방문   5 -&gt; 4<br># 4번방 방문 후에 6번방 방문   4 -&gt; 6</em></pre><ul><li><strong>규칙에 맞게 모든 방을 방문 할 수 있다면 </strong>true<strong> , 아니면 </strong>false<strong> 를 반환한다.</strong></li><li>다음은 문제 예시와 주어진 규칙에 맞게 모든 방을 방문하는 경우이다.</li></ul><pre>path = [[0, 1], [0, 3], [0, 7], [8, 1], [3, 6], [1, 2], [4, 7], [7, 5]]<br>order = [[8, 5], [6, 7], [4, 1]]</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*UTSyHoL6XIdYkup_U5RL5A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*zBbqurzKBrrRWgzyheF-fw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*Pkd_Z7gqC-Y24SfCDVX8Uw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*ZtALJYjonbQ6cPHOgcUn5w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*pfragrgfjW5JVyECUEUtZA.png" /></figure><h3>문제풀이</h3><h4>[풀이1] : 조건에 맞게 방을 체크해가며 탐색 (DFS)</h4><p>출발 가능한 방에서 시작하여 최대한 방문할 수 있는 방을 전부 방문 해본다.</p><p>출발이 가능한 첫번째 방은 동굴의 유일한 입구인0번 방이다.</p><p>단, 선방문 규칙으로 인해0번방에 바로 방문하지 못한다면 입구조차 들어가지 못하는 것임으로 바로 false를 리턴한다.</p><pre>order = [[3, 0], ...]<br><em># 3번방 방문 후에 0번방 방문   3 -&gt; 0<br># 하지만 0번방이 동굴의 입구임으로 0번방 이전에 다른 방을 방문하는 것은 불가능하다</em></pre><p>이 풀이의 핵심은 order 규칙에 의해 방문하지 못한 방은 따로 체크해두고 나중에 방문하는 것이다.</p><p>방문을 계속 진행 하면서, 조건이 만족되어 “체크해 둔 방”에 방문할 수 있게 된다면 그 방으로 점프해서 탐색을 진행한다. (선방문해야하는 방에 방문하게 되면 조건이 만족된다.)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*VgyzNMtVdU_IxRFH5OfcSg.png" /><figcaption>4번방을 방문하고 나서 체크해둔 1번방을 방문할 수 있게 되었다</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*y2eNXAG350Aiub6x4XkOKg.png" /><figcaption>1번방에서부터 계속 탐색을 진행한다.</figcaption></figure><p>더 이상 방문할 방이 없으면 재귀가 풀리면서 다시 원래위치에서 탐색을 진행한다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*5Gt-fR5AvCJxkmAQXasqUQ.png" /><figcaption>재귀가 풀리면서 자연스럽게 7번방의 오른쪽 방인 5번방 을 방문한다.</figcaption></figure><p>탐색을 마치고 나서 방문한 방의 개수가 전체방의 개수와 같다면 모든 방을 방문한 것임으로 true 를 반환하고 아니라면 false 를 반환한다.</p><h4>[풀이2] : 유향그래프를 만든 후 사이클 존재 여부 확인 (BFS, DFS)</h4><p>동굴이 0번방, 3번방, 6번방으로 구성되어 있고 6번방을 방문해야지만 3번방을 방문 할 수 있다고 가정한다.</p><pre>path = [[0, 3], [3, 6]]<br>order = [[6, 3]]</pre><p>6번방을 방문하기 위해서는 필연적으로 3번방을 방문해야 함으로 order 을 만족하는 경우는 없다는 것을 알 수 있다.</p><p>이 경우를 단방향 그래프로 표현해본다.</p><p>동굴내 방들을 나타내는 양방향 그래프를 위에서 아래를 향하는 단방향 그래프로 만들고 order 관계를 방향으로 나타내본다. (6번-&gt;3번)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*mPrONcXFqm2q0n0DT2fJoA.png" /><figcaption>6번방을 방문하기 전에 3번을 방문 했음으로 불가능하다</figcaption></figure><p>불가능한 경우는 그래프내에 원형으로 사이클이 생기는 것을 알 수 있다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*FJhJqNdWxk24NDBRB6x7Kg.png" /></figure><p>종합해보면 이 문제는 유향 그래프내에 사이클 유무 여부를 확인하는 문제로 환원될 수 있다.</p><p>사이클이 있다면 불가능한 경우임으로 false, 아니라면 모든 방을 방문할 수 있음으로 true 를 반환한다.</p><h3>Python3 코드</h3><h4>[풀이1] 코드</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/64718c2bc819286a3f4d7724f61fe1d8/href">https://medium.com/media/64718c2bc819286a3f4d7724f61fe1d8/href</a></iframe><h4>[풀이2] 코드</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/36cc60ba3cbeedc4586e3610b3dca81b/href">https://medium.com/media/36cc60ba3cbeedc4586e3610b3dca81b/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a669d62f304d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[프로그래머스] 경주로 건설]]></title>
            <link>https://haeseok.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B2%BD%EC%A3%BC%EB%A1%9C-%EA%B1%B4%EC%84%A4-6331021a7536?source=rss-2fd65d3e7098------2</link>
            <guid isPermaLink="false">https://medium.com/p/6331021a7536</guid>
            <category><![CDATA[카카오]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[kakao]]></category>
            <category><![CDATA[python3]]></category>
            <category><![CDATA[프로그래머스]]></category>
            <dc:creator><![CDATA[Haeseok Lee]]></dc:creator>
            <pubDate>Tue, 21 Jul 2020 16:46:24 GMT</pubDate>
            <atom:updated>2020-07-24T14:58:30.040Z</atom:updated>
            <content:encoded><![CDATA[<h4>2020 카카오 인턴십 문제풀이 with Python3</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/1*1-mYKGXjF-g7EjX5klAddg.jpeg" /><figcaption>2020 카카오 인턴십</figcaption></figure><h3>문제링크</h3><p><a href="https://programmers.co.kr/learn/courses/30/lessons/67259?language=python3">코딩테스트 연습 - 경주로 건설</a></p><h3>문제설명</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*0q_HTmaOyzClFu7mBBi9ig.png" /></figure><ul><li>비어있거나( 0으로 표현) 벽이 있는( 1 로 표현) N x N 크기의 정사각형 형태의 땅이 주어진다. 예를들어 위 예시의 경우 다음과 같이 입력이 주어진다.</li></ul><pre>[[0,0,0,0,0,0,0,1],<br>[0,0,0,0,0,0,0,0],<br>[0,0,0,0,0,1,0,0],<br>[0,0,0,0,1,0,0,0],<br>[0,0,0,1,0,0,0,1],<br>[0,0,1,0,0,0,1,0],<br>[0,1,0,0,0,1,0,0],<br>[1,0,0,0,0,0,0,0]]</pre><ul><li>(0, 0) 칸부터 출발하여 도착점인 (N-1, N-1) 칸까지 경주로를 건설하고자 할때 <strong>직선도로는 100원</strong>, <strong>코너는 500원</strong>의 건설비용이 발생한다. 직선도로와 코너의 판단기준은 다음 예시사진과 같다.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*DrrSVjIlbpAlMYpLaP1MOA.png" /></figure><ul><li>경주로를 건설하는데 필요한 <strong>최소 비용을 계산</strong>한다.</li></ul><h3>문제풀이</h3><p>정사각형 형태의 땅을 모두 탐색하고 가능한 경주로를 만들어봐야 최소비용 경주로를 찾아낼 수 있는 <strong>완전탐색 문제</strong>이다.</p><p>먼저 N x N 크기의 정사각형 땅에 경주로를 건설할 수 있는 모든 경우의 수를 찾아본다. 이때 모든 경주로를 만들어보기 위해 완전탐색 알고리즘 중에 하나인 <strong>BFS 알고리즘</strong>을 적용할 수 있다.</p><p>(0, 0) 칸 부터 시작하여 오른쪽 (0, 1) , 왼쪽 (0, -1) , 아래쪽 (1 , 0) , 위쪽 (-1, 0) 칸으로 이동하며 경주로를 만들어간다. 주의할 점은 맨처음 칸에서 <strong>출발시 경주로 건설방향</strong>은 오른쪽 R 또는 아래쪽 D 방향, 두 가지 경우가 모두 가능하다. 때문에 경우를 나누어 두 번 탐색한다.</p><p>현재 칸에서 새로운 좌표의 칸으로 이동시, 이동 가능한 칸이라면 (이동했다는 의미로) check 배열에 표시한다. 그 다음 지금까지 만든 경주로의 건설비용을 계산한다.</p><p>건설비용은 다음과 같은 방법으로 계산한다. 건설방향이 좌우에서 좌우, 상하에서 상하로 바뀌었다면 직선경로를 건설한 것임으로 100원으로 계산한다. 하지만 좌우에서 상하, 상하에서 좌우로 바뀌었다면 코너경로 + 직선경로를 건설한 것임으로 600원으로 계산한다.</p><p>기존 BFS 알고리즘으로는 한번 방문한 칸은 다시 방문하지 못한다. 이 때문에 탐색시, 건설 최소비용인 경주로를 방문하지 않고, 방문하지 않았던 칸만 방문하며 비용을 계산하는 문제가 발생한다.</p><p>이를 해결하기 위해 방문여부를 저장하는check 배열에 현재까지 계산한 최소 건설비용을 저장하여 <strong>메모이제이션</strong>을 한다.</p><p>이로써 이후에 같은 칸을 방문시 건설 비용을 비교할 수 있게하고 기존 건설비용보다 비용이 적게든다면 다시 방문할 수 있게한다. 최종적으로는 check배열의 (N-1, N-1) 칸에 경주로의 최소건설비용이 저장된다.</p><h3>Python3 Tip</h3><p>배열의 맨 앞 데이터를 pop하는 연산(FIFO)이 많은 문제에서는 deque 자료형을 사용하는 것을 권장한다. 기본 자료형인 List를 활용한 pop(0) 연산은 O(n)의 시간복잡도를 가지는 반면에 deque의 popleft() 연산은 O(1)의 시간 복잡도를 가진다. 다시말해 후자가 훨씬 빠르다.</p><p><a href="https://stackoverflow.com/questions/32543608/deque-popleft-and-list-pop0-is-there-performance-difference">deque.popleft() and list.pop(0). Is there performance difference?</a></p><h3>Python3 코드</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1092e098794045387f826b98e192cb66/href">https://medium.com/media/1092e098794045387f826b98e192cb66/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6331021a7536" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[프로그래머스] 보석쇼핑]]></title>
            <link>https://haeseok.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%B3%B4%EC%84%9D%EC%87%BC%ED%95%91-a901de0ce34?source=rss-2fd65d3e7098------2</link>
            <guid isPermaLink="false">https://medium.com/p/a901de0ce34</guid>
            <category><![CDATA[프로그래머스]]></category>
            <category><![CDATA[kakao]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[python3]]></category>
            <category><![CDATA[카카오]]></category>
            <dc:creator><![CDATA[Haeseok Lee]]></dc:creator>
            <pubDate>Wed, 15 Jul 2020 10:02:18 GMT</pubDate>
            <atom:updated>2020-07-17T04:14:01.934Z</atom:updated>
            <content:encoded><![CDATA[<h4>2020 카카오 인턴십 문제풀이 with Python3</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/1*1-mYKGXjF-g7EjX5klAddg.jpeg" /><figcaption>2020 카카오 인턴십</figcaption></figure><h3>문제링크</h3><p><a href="https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3">코딩테스트 연습 - 보석 쇼핑</a></p><h3>문제설명</h3><ul><li>이름이 다른 여러 종류의 보석들이 번호 순으로 놓여있는 진열대에 보관되어 있다.</li><li>진열대의 번호는 1번부터 시작하며 어떤 보석이 담겨있는지는 gems 매개변수로 주어진다.</li></ul><pre>진열대 번호 : 1 2 3 4 5 6 7 8<br>보석의 종류 : D R R D D E S D</pre><ul><li><strong>“진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간”</strong>을 찾아서 리턴한다.</li></ul><p>위 예시에서 “모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간”은 D, R, E, S 보석을 모두 포함하는 3번 부터 7번 진열대임으로 [3, 7] 이 답이 된다.</p><h3>문제풀이</h3><p>배열의 처음부터 끝까지 순차적으로 탐색하는 <strong>탐색문제</strong>이다.</p><p>gems 배열의 크기는 최대 100000 이기 때문에 O(n^2)이상인 탐색 알고리즘으로는 시간 초과가 발생하여 문제를 풀 수 없다. 효율성 테스트가 존재하는 문제이기 때문에 알고리즘을 최적화하지 않는다면 더더욱 통과하기가 힘들것이다.</p><p>그러므로 O(n) 으로 탐색할 수 있는 <strong>투 포인터 알고리즘</strong>을 사용해야 한다.</p><ol><li>먼저 배열 인덱스를 저장하는 start 변수와 end 변수를 선언한다.</li></ol><p>2. 배열의 start 와 end 구간이 <strong>“모든 종류의 보석을 포함하는 구간”</strong>이 될 때 까지 end 인덱스를 증가시킨다.</p><p>※ “배열의 start 와 end 구간” 이 “모든 종류의 보석을 포함하는 구간&quot; 인지 여부를 판단하는 문제는 효율성을 위해 <strong>딕셔너리 자료구조</strong>를 사용한다.</p><pre>진열대 번호 : 1 2 3 4 5 6 7 8<br>인덱스 번호 : 0 1 2 3 4 5 6 7<br>보석의 종류 : D R R D D E S D</pre><pre>start = 0   end = 0   구간안에있는 보석 : []<br>start = 0   end = 1   구간안에있는 보석 : [D]<br>start = 0   end = 2   구간안에있는 보석 : [D, R]<br>start = 0   end = 3   구간안에있는 보석 : [D, R, R]<br>start = 0   end = 4   구간안에있는 보석 : [D, R, R, D]<br>start = 0   end = 5   구간안에있는 보석 : [D, R, R, D, D]<br>start = 0   end = 6   구간안에있는 보석 : [D, R, R, D, D, E]<br>start = 0   end = 7   구간안에있는 보석 : [D, R, R, D, D, E, S]</pre><p>3. <strong>“구간 중 가장 짧은 구간”</strong> 을 구해야 하기 때문에 start 인덱스를 하나씩 증가시켜보며 구간의 길이를 줄여본다. 줄어든 구간이 <strong>“모든 종류의 보석을 적어도 1개 이상 포함”</strong> 한다는 조건을 만족시키면 현재start , end 를 저장하고, 조건이 만족되지 않을 때까지 구간의 길이를 줄인다.</p><pre>진열대 번호 : 1 2 3 4 5 6 7 8<br>인덱스 번호 : 0 1 2 3 4 5 6 7<br>보석의 종류 : D R R D D E S D</pre><pre>start = 0   end = 0   구간안에있는 보석 : []<br>start = 0   end = 1   구간안에있는 보석 : [D]<br>start = 0   end = 2   구간안에있는 보석 : [D, R]<br>start = 0   end = 3   구간안에있는 보석 : [D, R, R]<br>start = 0   end = 4   구간안에있는 보석 : [D, R, R, D]<br>start = 0   end = 5   구간안에있는 보석 : [D, R, R, D, D]<br>start = 0   end = 6   구간안에있는 보석 : [D, R, R, D, D, E]<br>start = 0   end = 7   구간안에있는 보석 : [D, R, R, D, D, E, S] 조건만족: O<br>start = 1   end = 7   구간안에있는 보석 : [D, R, R, D, D, E, S] 조건만족: O<br>start = 2   end = 7   구간안에있는 보석 : [R, R, D, D, E, S]    조건만족: O<br>start = 3   end = 7   구간안에있는 보석 : [R, D, D, E, S]       조건만족: O<br>start = 4   end = 7   구간안에있는 보석 : [D, D, E, S]          조건만족: X</pre><p>4. 현재 구간이 조건을 만족시키지 않는다면 다시 end 인덱스를 증가시키면서 구간을 탐색한다.</p><p>5. 위 과정을 반복한다.</p><p>6. 구간을 전부 탐색했다면 탐색을 종료하고 조건을 만족하는 구간들 중에 <strong>길이가 가장 짧은 구간의 </strong>start<strong> , </strong>end<strong> </strong>를 리턴한다.</p><h3>Python3 코드</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5f84326a54171ed130954bc26a45a743/href">https://medium.com/media/5f84326a54171ed130954bc26a45a743/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a901de0ce34" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[프로그래머스] 수식 최대화]]></title>
            <link>https://haeseok.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%98%EC%8B%9D-%EC%B5%9C%EB%8C%80%ED%99%94-eaa534d55316?source=rss-2fd65d3e7098------2</link>
            <guid isPermaLink="false">https://medium.com/p/eaa534d55316</guid>
            <category><![CDATA[python3]]></category>
            <category><![CDATA[프로그래머스]]></category>
            <category><![CDATA[카카오]]></category>
            <category><![CDATA[pyhon]]></category>
            <dc:creator><![CDATA[Haeseok Lee]]></dc:creator>
            <pubDate>Sun, 12 Jul 2020 16:50:03 GMT</pubDate>
            <atom:updated>2020-07-24T15:04:40.039Z</atom:updated>
            <content:encoded><![CDATA[<h4>2020 카카오 인턴십 문제풀이 with Python3</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/1*1-mYKGXjF-g7EjX5klAddg.jpeg" /><figcaption>2020 카카오 인턴십</figcaption></figure><h3>문제링크</h3><p><a href="https://programmers.co.kr/learn/courses/30/lessons/67257?language=python3">코딩테스트 연습 - 수식 최대화</a></p><h3>문제설명</h3><ul><li>- , + , * 3개의 연산자와 숫자로만 이루어진 수식이 주어진다.</li><li><strong>올바른 중위표기법으로 표현된 수식</strong>만 주어진다. 다시말해 잘못된 수식은 입력으로 주어지지 않는다.</li></ul><p>402+-561* 과 같은 수식은 입력으로 주어지지 않는다.</p><ul><li>3개의 연산자는 동일한 우선순위를 가질 수 없으며 <strong>각각 다른 우선순위</strong>를 가진다.</li></ul><p>- &gt;+ &gt;* (가능) <br>* &gt;- &gt; + (가능)<br>* ,- &gt; + (불가능) <br>* &gt;- , + (불가능)</p><ul><li>3개의 연산자가 가질 수 있는 <strong>모든 우선순위 조합</strong>(3개의 연산자는 3!개 = 6개의 우선순위 조합을 가진다)을 가지고 수식을 계산한다.</li></ul><p>수식이 300-400*900+100-20+100 이고 우선순위가 - &gt;+ &gt;* 일때 계산 순서는 다음과 같다</p><p>(300-400)*900+(100-20)+100<br>-100*(900+80+100)<br>(-100*1080)<br>-108000</p><p>우선순위 조합은 6개가 있으므로 같은 수식에 대하여 위와 같이 6번 연산을 하고 결과값을 구해 이전 결과값과 비교해야 한다.</p><ul><li><strong>계산한 결과값의 절댓값</strong>을 받을 수 있는 상금으로 한다.</li></ul><p>-108000 이 계산값이면 실제 비교하는 값은 절댓값인 108000 이 된다.</p><ul><li>받을 수 있는 상금들 중에 <strong>가장 큰 값</strong>을 구하고 리턴한다.</li></ul><h3>문제풀이</h3><p>연산자의 우선순위에 따라 주어진 수식을 부분 수식으로 쪼개고 부분 수식들의 결과값을 다시 합쳐 최종 결과값을 만들어 결과를 구하는 <strong>분할 정복 문제</strong>이다.</p><p>분할 정복 문제의 특성상 재귀로 풀면 더 간단하게 코드를 작성할 수 있다.</p><p>문제의 접근법은 다음과 같다. 우선순위가 - &gt;+ &gt;* 라고 가정 했을때 * 연산을 하기 위해서는 + 연산의 결과값이 먼저 필요하다고 생각할 수 있다. 동일하게 + 연산을 하기 위해서는 — 연산의 결과값이 먼저 필요하다.</p><p>이런 이유로 인해 먼저 * 을 기준으로 수식을 쪼갠다. * 연산자는 우선순위가 가장 낮기 때문에 — , + 를 먼저 계산한 결과값들을 가지고 마지막에 계산한다. 쪼개진 수식은 다시 같은 이유로 그 다음 낮은 우선순위를 가지는 + 로 쪼갠다.</p><p>+ , * 로 쪼개진 수식들은 <strong>최종적으로</strong> — <strong>연산만 가진 수식</strong>이 되거나 <strong>그냥 숫자만 있는 수식</strong>이 되는데 이때 수식을 계산하고 값을 리턴한다. (그냥 숫자만 있는 수식은 그대로 리턴한다)</p><p><strong>재귀가 풀리면서 받아온</strong> — <strong>연산의 결과값으로</strong> + <strong>연산을 하고</strong> + <strong>연산을 한 결과값들을 가지고</strong> * <strong>연산을 수행한다.</strong></p><p>최종적으로 연산한 결과값의 절댓값을 구하고 다른 우선순위 조합으로 계산한 결과값과 비교하여 더 큰 값만 저장한다.</p><p>6번의 연산을 통해 가장 큰 값을 구했다면 그 값을 리턴한다.</p><h3>Python3 Tip</h3><p>문자열로 표현된 파이썬 식을 인수로 받아 결과값은 내주는 파이썬 내장함수 eval() 이 문자열로 된 수식을 계산할때 유용하게 사용될 수 있다.</p><pre>&gt;&gt;&gt; eval(&#39;3 + 4&#39;)<br>7</pre><p>리스트에 특정 구분자를 포함해 문자열로 변환해주는 join() 함수도 계산한 결과값을 합칠 때 유용하다.</p><pre>&gt;&gt;&gt; &#39; + &#39;.join([&#39;4 * 5&#39;, &#39;6&#39;, &#39;10&#39;, &#39;300&#39;])<br>&#39;4 * 5 + 6 + 10 + 300&#39;</pre><h3>Python3 코드</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/451f00fcbb18fa0e7e02693f2a443126/href">https://medium.com/media/451f00fcbb18fa0e7e02693f2a443126/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eaa534d55316" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[프로그래머스] 키패드 누르기 (문제풀이)]]></title>
            <link>https://haeseok.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%82%A4%ED%8C%A8%EB%93%9C-%EB%88%84%EB%A5%B4%EA%B8%B0-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-b4f24077bcfb?source=rss-2fd65d3e7098------2</link>
            <guid isPermaLink="false">https://medium.com/p/b4f24077bcfb</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[카카오]]></category>
            <category><![CDATA[프로그래머스]]></category>
            <category><![CDATA[python3]]></category>
            <dc:creator><![CDATA[Haeseok Lee]]></dc:creator>
            <pubDate>Sun, 12 Jul 2020 13:52:50 GMT</pubDate>
            <atom:updated>2020-07-13T11:28:40.103Z</atom:updated>
            <content:encoded><![CDATA[<h3>[프로그래머스] 키패드 누르기</h3><h4>2020 카카오 인턴십 문제풀이 with Python3</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/1*1-mYKGXjF-g7EjX5klAddg.jpeg" /><figcaption>2020 카카오 인턴십</figcaption></figure><h3>문제링크</h3><p><a href="https://programmers.co.kr/learn/courses/30/lessons/67256">코딩테스트 연습 - 키패드 누르기</a></p><h3>문제설명</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*lcQZpSCi0Zi8UBOjU766XA.png" /></figure><ul><li>맨 처음에 왼손은 * 에 위치하고 있고 오른손은 # 에 위치하고 있다.</li><li>손가락은 상하좌우로 움직일 수 있으며 키패드 한칸은 길이가 1이다.</li><li>왼손만 1 4 7 키패드에 접근할 수 있다.</li><li>오른손만 3 6 9 키패드에 접근할 수 있다.</li><li>가운데 키패드는 현재 위치에서 가까운 손가락만 누를 수 있다. <br>단, 거리가 같다면 매개변수 hand에 따라 다르게 누른다.</li><li>순서대로 누를 번호가 담긴 배열 numbers 와 왼손잡이인지 오른손잡이인 지를 나타내는 hand 가 주어지고, 각 번호를 누른 손가락이 왼손인지 오른손인지 판단한다.</li></ul><h3>문제풀이</h3><p>순서대로 누를 번호가 담긴 배열 numbers 를 처음부터 끝까지 탐색하면서 주어진 규칙에 맞게 키패드를 눌러야 하는 손가락을 판단하는 단순 구현 문제이다.</p><p>키패드를 누른 손가락은 전에 누른 위치에서 다음 위치로 이동하기 때문에 누를때 마다 <strong>왼손과 오른손의 위치를 저장해줘야한다.</strong></p><p>가운데 키패드를 누를 때, 눌러야 하는 키패드와 가까운 손가락을 찾아야 한다. 이 때, <strong>왼손과 키패드간에 거리, 오른손과 키패드간의 거리를 계산</strong>하여 두 손가락 중 가까운 손가락을 판단한다. 손가락과 키패드간에 거리가 같다면 문제에서 주어진대로 hand 에 따라 사용할 손가락을 결정한다.</p><p>키패드간 거리는 <strong>가로길이차이 + 세로길이차이</strong>로 계산한다. <br>(예: 2 키패드 와 9 키패드는 세로 2칸 가로 1칸이 차이가 나므로 거리는 3이다)</p><p>키패드간 거리를 편하게 구하기 위해 <strong>키패드마다 좌표를 딕셔너리 형태로 저장</strong>하여 거리를 계산 했고 계산 함수를 따로 만들어서 재사용했다.</p><h3><strong>Python3 코드</strong></h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4e19507cde24d9a8dabdf72902b33517/href">https://medium.com/media/4e19507cde24d9a8dabdf72902b33517/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b4f24077bcfb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[1. [디자인 패턴] Strategy pattern]]></title>
            <link>https://haeseok.medium.com/1-%EB%94%94%EC%9E%90%EC%9D%B8-%ED%8C%A8%ED%84%B4-strategy-pattern-13c690a5bc12?source=rss-2fd65d3e7098------2</link>
            <guid isPermaLink="false">https://medium.com/p/13c690a5bc12</guid>
            <dc:creator><![CDATA[Haeseok Lee]]></dc:creator>
            <pubDate>Thu, 09 Jan 2020 05:35:06 GMT</pubDate>
            <atom:updated>2020-01-28T12:23:05.949Z</atom:updated>
            <content:encoded><![CDATA[<h3>[디자인 패턴] 스트래티지 패턴 Strategy Pattern</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BX05xGJBQnCGhRQR52rClQ.jpeg" /><figcaption>“모든 오리는 물에 뜹니다. 가짜 오리도 뜨죠”</figcaption></figure><p>프로젝트 구조</p><pre><strong>strategy_pattern/<br>    duck/</strong><br>        behavior.py<br>        duck.py<br>        fly_behavior.py<br>        quack_behavior.py<br>    main.py</pre><p>duck.py 구현</p><pre>from abc import ABCMeta, abstractmethod<br>from <strong>.</strong>behavior import FlyBehavior, QuackBehavior</pre><pre><br>class Duck(metaclass = ABCMeta):</pre><pre>    def __init__(self):<br>        super()<strong>.</strong>__init__()<br>        # 각각의 행동객체들은 행동 알고리즘들 중에 골라서 가져오게 됩니다.<br>        self<strong>.</strong>fly_behavior = None<br>        self<strong>.</strong>quack_behavior = None</pre><pre>    @abstractmethod<br>    def display(self):<br>        # display 메소드는 Duck을 상속한 모든 클래스들에서 구현해야합니다.<br>        pass</pre><pre>    def perform_fly(self):<br>        self<strong>.</strong>fly_behavior<strong>.</strong>fly()</pre><pre>    def perform_quack(self):<br>        self<strong>.</strong>quack_behavior<strong>.</strong>quack()<br>   <br>    def setFlyBehavior(self, fb):<br>        self<strong>.</strong>fly_behavior = fb</pre><pre>    def setQuackBehavior(self, qb):<br>         self<strong>.</strong>quack_behavior = qb</pre><pre>    def swim(self):<br>        print(&#39;모든 오리는 물에 뜹니다. 가짜 오리도 뜨죠&#39;)</pre><p>behavior.py 구현</p><pre>from abc import ABCMeta, abstractmethod</pre><pre>class FlyBehavior(metaclass = ABCMeta):</pre><pre>    @abstractmethod<br>    def fly(self):<br>        pass</pre><pre><br>class QuackBehavior(metaclass = ABCMeta):</pre><pre>    @abstractmethod<br>    def quack(self):<br>        pass</pre><p>fly_behavior.py 구현</p><pre>from <strong>.</strong>behavior import FlyBehavior</pre><pre># 나는 행동에 대한 알고리즘들을 정의합니다 (알고리즘군을 형성)</pre><pre>class FlyWithWings(FlyBehavior):</pre><pre>    def fly(self):<br>        print(&quot;&gt; 저는 날고 있어요&quot;)<br></pre><pre>class FlyNoWay(FlyBehavior):<br>    <br>    def fly(self):<br>        print(&quot;&gt; 저는 날지 못해요&quot;)</pre><pre><br>class FlyRocketPowered(FlyBehavior):</pre><pre>    def fly(self):<br>        print(&quot;&gt; 로켓 추진으로 날아갑니다&quot;)</pre><p>quack_behavior.py 구현</p><pre>from <strong>.</strong>behavior import QuackBehavior</pre><pre># 소리내는 행동에 대한 알고리즘들을 정의합니다 (알고리즘군을 형성)</pre><pre>class Quack(QuackBehavior):</pre><pre>    def quack(self):<br>        print(&quot;&gt; 꽥!&quot;)<br></pre><pre>class MuteQuack(QuackBehavior):<br>  <br>    def quack(self):<br>        print(&quot;&gt; 조용!&quot;)<br></pre><pre>class Squeak(QuackBehavior):<br>   <br>    def quack(self):<br>        print(&quot;&gt; 삑!&quot;)</pre><p>main.py 구현</p><pre>from duck<strong>.</strong>duck import Duck<br>from duck<strong>.</strong>fly_behavior import(<br>    FlyWithWings,<br>    FlyNoWay,<br>    FlyRocketPowered)<br>from duck<strong>.</strong>quack_behavior import(<br>    Quack,<br>    MuteQuack)</pre><pre><br>class MallardDuck(Duck):</pre><pre>    def __init__(self):<br>        super()<strong>.</strong>__init__()<br>        self<strong>.</strong>fly_behavior = FlyWithWings()<br>        self<strong>.</strong>quack_behavior = Quack()</pre><pre>    def display(self):<br>        print(&quot;저는 청둥오리 입니다&quot;)</pre><pre><br>class ModelDuck(Duck):</pre><pre>    def __init__(self):<br>        super()<strong>.</strong>__init__()<br>        self<strong>.</strong>fly_behavior = FlyNoWay()<br>        self<strong>.</strong>quack_behavior = MuteQuack()</pre><pre>    def display(self):<br>        print(&quot;저는 모형오리 입니다&quot;)</pre><pre>def main():</pre><pre>    mallard_duck = MallardDuck()<br>    mallard_duck<strong>.</strong>display()<br>    mallard_duck<strong>.</strong>perform_fly()<br>    mallard_duck<strong>.</strong>perform_quack()</pre><pre>    print(&#39;-&#39;*30)</pre><pre>    model_duck = ModelDuck()<br>    model_duck<strong>.</strong>display()<br>    model_duck<strong>.</strong>perform_fly()<br>    model_duck<strong>.</strong>perform_quack()</pre><pre>    # 동적으로 같은 행동 알고리즘군의 다른 클래스를 할당할 수 있습니다<br>    model_duck<strong>.</strong>setFlyBehavior(FlyRocketPowered())<br>    model_duck<strong>.</strong>perform_fly()<br></pre><pre>if __name__ == &#39;__main__&#39;:<br>    main()</pre><blockquote><strong><em>객체지향 원칙</em></strong></blockquote><blockquote>“바뀌는 부분은 캡슐화 한다”</blockquote><blockquote>“구현이 아닌 인터페이스에 맞춰서 프로그래밍 한다”</blockquote><blockquote>“상속보다는 구성을 활용한다”</blockquote><p>✔︎ 오리의 행동들을(날수있음, 날지못함, 꽥 소리내기, 삑 소리내기, 소리내지못함) Duck 클래스에서 분리해냈습니다. 즉, <strong>달라지는 부분</strong>을 찾아서 나머지 코드에 영향을 주지 않도록 <strong>캡슐화</strong> 했습니다. 이렇게 되면 코드가 바뀌어도 유연성이 향상됩니다.</p><p>✔︎ 오리의 행동들을 분리한 뒤 각 행동들을 특정 종류(나는 행동, 소리 내는 행동)로 분류합니다. 분류한 특정 종류의 행동들을 <strong>인터페이스</strong> (FlyBehavior, QuackBehavior)에 표현합니다.</p><p>하지만 구체적인 행동 구현, 다시말해 알고리즘은 각각의 <strong>인터페이스</strong>를 바탕으로 만들어진 구상 클래스들(FlyWithWings, FlyNoWay, Quack, MuteQuack …)에서 구현합니다. 이제부터 Duck의 행동들은 별도의 클래스들에 들어가 있게 되며 Duck 클래스는 행동을 구체적으로 구현하는 방법에 대해서 알 필요가 없어졌습니다.</p><p>✔︎ 별도의 클래스로 구현된 행동들을(날수 있음, 날지 못함, 꽥 소리내기, 삑 소리내기, 소리내지 못함) 활용해 보겠습니다. Duck을 상속받은 ModelDuck(클라이언트)은 FlyNoWay(날지 못함), MuteQuack(소리내지 못함) 구상 클래스들을 가지게 됩니다. (가짜오리는 날 수 없고 소리도 낼 수 없겠죠?) 이렇게 “A에는 B가 있다” “클래스와 클래스를 합친다”는 상속이 아닌 <strong>구성을 이용</strong>하는 것입니다. 구성을 사용함으로써 실행시에 동적으로 행동을 바꿀 수 있게 해주며 재사용성을 높여줍니다.</p><blockquote><strong><em>객체지향 패턴</em></strong></blockquote><blockquote>“스트래티지 패턴 : <strong>알고리즘군을 정의</strong>하고 각각을 <strong>캡슐화 </strong>하여 바꿔 쓸 수 있게 만든다”</blockquote><p>✔︎ 스트래티지 패턴을 사용하면 알고리즘을 사용하는 클라이언트와는 독립적으로 알고리즘을 변경 할 수 있습니다.</p><p>※ 본 게시글은 <a href="https://www.wickedlysmart.com/head-first-design-patterns/">Head First Design Patterns</a> 책의 내용을 참고 하였습니다.</p><p>※ 소스코드는 <a href="https://github.com/haeseoklee/design_pattern">GitHub</a>에서 확인할 수 있습니다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=13c690a5bc12" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>