<?xml version="1.0" encoding="utf-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom">
    <channel>
        <title>sophia-0717.log</title>
        <link>https://velog.io/</link>
        <description>Tempest Data Analyst</description>
        <lastBuildDate>Sun, 20 Nov 2022 06:59:18 GMT</lastBuildDate>
        <docs>https://validator.w3.org/feed/docs/rss2.html</docs>
        <generator>https://github.com/jpmonette/feed</generator>
        <image>
            <title>sophia-0717.log</title>
            <url>https://velog.velcdn.com/images/sophia-0717/profile/0123ab5f-d937-49d5-bc68-df521468c6d8/image.jpg</url>
            <link>https://velog.io/</link>
        </image>
        <copyright>Copyright (C) 2019. sophia-0717.log. All rights reserved.</copyright>
        <atom:link href="https://v2.velog.io/rss/sophia-0717" rel="self" type="application/rss+xml"/>
        <item>
            <title><![CDATA[Python Algorithms - DFS/BFS - "Population Migration"]]></title>
            <link>https://velog.io/@sophia-0717/Python-Algorithms-DFSBFS-Population-Migration</link>
            <guid>https://velog.io/@sophia-0717/Python-Algorithms-DFSBFS-Population-Migration</guid>
            <pubDate>Sun, 20 Nov 2022 06:59:18 GMT</pubDate>
            <description><![CDATA[<p>*<em>Problem: *</em>
<code>How many times population migration occur in given conditions?</code>
<code>인구이동이 다음과 같은 조건일 때 얼마나 많이 일어나는가?</code></p>
<p><strong>Conditions:</strong></p>
<ol>
<li>They open the border when two countries share the border and the difference of population is greater and equal than L, and is less and equal than R. </li>
<li>In population migration, the population in each country is (the total population / the number of countries ). Don&#39;t round up. </li>
<li>Afterward, the border is closed.</li>
</ol>
<p><strong>Solutions:</strong></p>
<pre><code class="language-python">from collections import deque

#Get input n(size of land), l and r.
n, l, r = map(int, input().split())

#Get information of population (n X n).
population = []
for _ in range(n):
    population.append(list(map(int, input().split())))

#Define directions, left and right, and up and down.
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

result = 0 

def process(x, y, index):

    #Create a list containing (x, y) coordinate and border information.
    united = []
    united.append((x, y))

    #Define queue data structure for BFS.
    q= deque()
    q.append((x, y))
    union[x][y] = index  #The index(number) of current union.
    summary = population[x][y]  #The total population of current union. 
    coutnt = 1  #The number of countries of union.

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            #Check if the countries share the borders and check if the union are not processed yet. 
            if 0 &lt;= nx and nx &lt; n and 0 &lt;= ny and ny &lt; n and union[nx][ny] == -1:
            #Define the difference of population. 
            difference = abs(population[nx][ny] - population[x][y])
                if l &lt;= difference &lt;= r:
                  q.append((nx, ny))
                  #Add in union.
                  union[nx][ny] = index
                  summary += population[nx][ny]
                  count += 1
                  united.append((nx, ny))
    #Distribute population. 
    for i, j in united:
        population[i][j] = summary // count
    return count

total count = 0

#Repeate a loop until population migration do not occur.
while True:
    union = [[-1] * n for _ in range(n)]
    index = 0
    for i in range(n):
        for j in range(n):
            if union[i][j] == -1:  #If the country is not processed. 
                process(i, j, index)
                index += 1

    if index == n * n:  #After the migration ends. 
         break
       total_count += 1

#Print the total count of the migration. 
print(total_count)</code></pre>
]]></description>
        </item>
        <item>
            <title><![CDATA[Python Algorithms - DFS/BFS - "Escape From the Maze"]]></title>
            <link>https://velog.io/@sophia-0717/Python-Algorithms-DFSBFS-Escape-From-the-Maze</link>
            <guid>https://velog.io/@sophia-0717/Python-Algorithms-DFSBFS-Escape-From-the-Maze</guid>
            <pubDate>Sat, 12 Nov 2022 23:47:04 GMT</pubDate>
            <description><![CDATA[<p><strong>Problem:</strong>
<code>What is the minimum number of movements for escape from the maze?</code>
<code>미로를 탈출하기 위해 최소한으로 얼마나 움직여야 하는가?</code></p>
<p><strong>Conditions:</strong>
<code>His coordinate is (1, 1) and the exit locates at (N, M). He can move one step at a time. During the movement,  he has to avoid monsters, whose node is coded as 1.</code></p>
<pre><code class="language-python">from collections import deque

#Get input, N and M, separated by space.
n, m = map(int, input().split())

#Get 2 dimensional list of input.
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

#Define directions (Left, Right, Up, Down)    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 0]

#Define a function, bfs.
def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    #While-loop until queue is empty.
    while queue:
        x, y = queue.popleft()

        #Location (nx, ny) distanced from current position.
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i}

            #Ignore if the location is off-limit. 
            if nx &lt; 0 or ny &lt; 0 or nx &gt;= n or ny &gt;= m:
            continue

            #Ignore when he meets a wall.
            if graph[nx][ny] == 0:
            continue

            #If visited the node, plus 1 distance
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    #Return the shortest distance to the most downright node.
    return graph[n-1][m-1]

print(bfs(0,0))</code></pre>
]]></description>
        </item>
        <item>
            <title><![CDATA[Python Algorithms - DFS/BFS - "Freeze beverages"]]></title>
            <link>https://velog.io/@sophia-0717/Python-Algorithms-DFSBFS-Freezing-beverages</link>
            <guid>https://velog.io/@sophia-0717/Python-Algorithms-DFSBFS-Freezing-beverages</guid>
            <pubDate>Sat, 12 Nov 2022 03:34:08 GMT</pubDate>
            <description><![CDATA[<p><strong>Problem:</strong>
<code>How many frozen beverages(icecream) can you produce when given following ice frames?</code>
<code>얼음 틀이 주어졌을 때 얼마나 많은 아이스크림을 구할 수 있는가?</code></p>
<p><strong>Example:</strong>
4 X 5 ice frame makes 3 icecreams in total.</p>
<p>00110
00011
11111
00000
<img src="https://velog.velcdn.com/images/sophia-0717/post/ffb329fb-90ef-468c-bce8-ca94c8036d88/image.png" alt=""></p>
<pre><code class="language-python">#Get input N and M. 
n, m = map(int, input().split())

#Get a sequential numbers of input and 
#put it into 2 dimensional list, &quot;graph&quot;. 
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

#Define a function named &quot;dfs&quot;.
def dfs(x, y):
    #Return False if x and y are out of range N X M. 
    if x &lt;= -1 or x &gt;= n or y &lt;= -1 or y &gt;= m:
        return False

    #If the node (x, y) is not &quot;visited&quot;, code it to 1.
    if graph[x][y] ==0:
        graph[x][y] = 1

        #Call the &quot;dfs&quot; function recursively and check the surrounding nodes 
        #whether they are visited.
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)

        #Return True if they are visited. 
        return True
    return False

result = 0
#In a for-loop of N X M, if the node(i, j) was visited, count 1 up for result. 
for i in rangae(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1
print(result)</code></pre>
]]></description>
        </item>
        <item>
            <title><![CDATA[Python Algorithms - Greedy - "Card Game"]]></title>
            <link>https://velog.io/@sophia-0717/Python-Algorithms-Greedy-Card-Game</link>
            <guid>https://velog.io/@sophia-0717/Python-Algorithms-Greedy-Card-Game</guid>
            <pubDate>Sat, 05 Nov 2022 22:50:27 GMT</pubDate>
            <description><![CDATA[<p><strong>Problme:</strong>
<code>Pick a card which has the greatest number.</code>
<code>가장 높은 숫자가 쓰인 카드를 뽑아라.</code></p>
<p><strong>Rules:</strong></p>
<ol>
<li>The arrangement of cards are N rows X M columns.</li>
<li>Pick a row.</li>
<li>Select the lowest card number in the row. </li>
<li>What you will finally choose is the greatest number among cards, considering that you get the lowest card number in every row. </li>
</ol>
<p><strong>Solution:</strong>
<code>Find the lowest number in every row, and then pick the greatest number among them.</code></p>
<pre><code class="language-python">#Get how many rows and how many columns there are.(n X m)
n, m = map(int, input().split())

#Initialize the result.
result = 0

#In the for-loop, get the input cards, 
#and compare the minimum number of input cards with the result. 
#The result will be reset if it finds smaller numbers.
for _ in range(n):
    cards = list(map(int, input().split()))
    if result &lt; min(cards):
        result = min(cards)
    else: pass

print(result)</code></pre>
]]></description>
        </item>
        <item>
            <title><![CDATA[Python Algorithms - Greedy  - "law of great numbers"]]></title>
            <link>https://velog.io/@sophia-0717/Python-Algorithms-Greedy-law-of-great-numbers</link>
            <guid>https://velog.io/@sophia-0717/Python-Algorithms-Greedy-law-of-great-numbers</guid>
            <pubDate>Sat, 05 Nov 2022 07:44:11 GMT</pubDate>
            <description><![CDATA[<p><strong>Problem:</strong>
<code>Get the greatest sum of numbers by adding given N numbers M times. But, the greatest number, among the numbers, can be added not over K times in a row.</code>
<code>큰 수의 법칙에 따라 가장 큰 수의 합을 구해라.</code></p>
<pre><code class="language-python">#input (ex: 5 8 3, 2 4 5 4 6)
n, m, k = map(int, input().split())
data = list(map(int, input().split()))

#Get the greatest number and the second greatest number
first = max(data)
data.remove(first)
second = max(data)

#Initialize the result
result = 0

# sum = (2) * (3) * 6 + (2) * 5  
result = (m//k) * k * first + (m%k) * second

print(result)</code></pre>
]]></description>
        </item>
        <item>
            <title><![CDATA[Python Algorithms - Greedy - "Muji's Mukbang Live"]]></title>
            <link>https://velog.io/@sophia-0717/Python-Algorithms-Greedy-Mujis-Mukbang-Live</link>
            <guid>https://velog.io/@sophia-0717/Python-Algorithms-Greedy-Mujis-Mukbang-Live</guid>
            <pubDate>Sat, 05 Nov 2022 03:04:33 GMT</pubDate>
            <description><![CDATA[<p><strong>Problem:</strong>
<code>Which food number does Muji have to restart to eat, when a network disconnection happens?</code>
<code>무지가 먹방 라이브 도중 네트워크 장애가 발생하면 재시작을 위해 먹어야할 음식의 번호는 무엇인가?</code></p>
<p><strong>Rules:</strong></p>
<ol>
<li>Muji starts to eat food #1, and the rotate disk brings food to Muji in increasing order. </li>
<li>When Muji eats the last # of food, the disk brings #1 again.</li>
<li>It allows 1 second for one bite of food, and because the disk rotates at every second, Muji has to eat the next food with the eaten food being left. </li>
<li>It takes no time to bring the food for the disk.</li>
</ol>
<p><code>The network disconnection shut down Muji&#39;s broadcasting for k seconds, and Muji wants to know which food # he has to restart to eat.</code>  </p>
<p><strong>Example:</strong></p>
<table>
<thead>
<tr>
<th align="left">food_times</th>
<th align="left">k</th>
<th align="left">result</th>
</tr>
</thead>
<tbody><tr>
<td align="left">[3, 1, 2]</td>
<td align="left">5</td>
<td align="left">1</td>
</tr>
</tbody></table>
<pre><code class="language-python">import heapq

def solution(food_times, k):

#if eating the all food takes longer than k, return -1
    if sum(food_times) &lt;= k:
        return -1

    q = []
# Put tuples, (food_times, #), into q during the loop.
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i+1))

# Initialize the value. 
    sum_value = 0    #Time spent for eating the food
    previous = 0     #Time spent for eating, just before
    length = len(food_times)     #the number of food left</code></pre>
<div><p align="center"><img src="https://velog.velcdn.com/images/sophia-0717/post/337c36fc-8d31-42ed-9085-e682964cc7fa/image.png" width="50%" height="50%"></img></p></div>

<pre><code class="language-python"># While-loop when the eating time is less equal than k seconds,
    while sum_value + ((q[0][0] - previous) * length) &lt;= k:
        now = heapq.heappop(q)[0]    #Current eating time
        sum_value += (now - previous) * length
        length -= 1    #Subtract 1 for eaten food
        previous = now   #reset &quot;previous&quot;

# Return the food # to restart eating. 
    result = sorted(q, key=lambda x: x[1])
    return result[(k - sum_value) % length][1]</code></pre>
]]></description>
        </item>
        <item>
            <title><![CDATA[Python Algorithms - Greedy -"Coin Machine"]]></title>
            <link>https://velog.io/@sophia-0717/Python-Algorithms-Coin-Machine</link>
            <guid>https://velog.io/@sophia-0717/Python-Algorithms-Coin-Machine</guid>
            <pubDate>Thu, 03 Nov 2022 04:42:02 GMT</pubDate>
            <description><![CDATA[<p>*<em>Problem: *</em>
<code>The coin machine will give you the currency in the least amount of coins.</code></p>
<p><code>최소의 동전 개수로 거스름돈을 거슬러 주는 머신이 있다.</code></p>
<pre><code class="language-python">#Define the bill(&#39;money&#39;) and the default amount of coins(&#39;count&#39;).
money = 1260
count = 0

#Define a list of coin types.
coin_types = [500, 100, 50, 10]

#During a loop, the machine will give you coins 
#in a descending order 
#and record the number of coins in the &#39;count&#39; variable.
for coin in coin_types:
    count += (money // coin)
    money %= coin

#print the answer.
print(count)</code></pre>
]]></description>
        </item>
    </channel>
</rss>