<h3>코딩 테스트 준비 일지 3 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">프로그래머스</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42842">카펫</a></li><li>난이도 : 중</li></ul><h6>문제 설명</h6>Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.<img src="https://image.until.blog/sin0105/article/1716879329667" alt="until-326">Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.</li><li>노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.</li><li>카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.</li></ul><h5>입출력 예</h5>brown yellow return 10 2 [4, 3] 8 1 [3, 3] 24 24 [8, 6]<h3>문제 풀이 접근</h3>이 문제의 권장 풀이 시간은 1시간이었는데, 한번 풀이를 잘못 들어가서 1시간을 그냥 날리고 리셋해서 총 1시간 25분 정도 걸린것 같다. 방향을 잘못잡은 풀이는 최대한 이쁜 사각형만을 찾아서 감싸서 가로 세로 값 리턴해야지! 라는 안일한 생각으로 잘못 잡았다. 여기서 말한 최대한 이쁜 사각형이라는 것은 [18, 6] 이 주어졌을 때, [8, 3] 이 실제로 정답이나, 나는 가로 세로의 차이가 가장 적은 값인 [6, 4] 를 정답으로 판단해서 오류가 발생했던 문제였다. 직사각형이 정답이 될 수 있음을 무시하고, 정사각형에 최대한 가까운 것이 정답이라고 생각한 것에 대한 오류였다. 이렇게 문제를 풀면 풀리긴한다. 다만, 이 문제의 질문목록에 자주 올라오는 TC 4 6 7 나의 경우는 9 까지 패스할 수 없었다. 결론, 완벽한 정답이 아니다. ( 여기까지 했을때 1시간 지나버려서 리셋했다. )다시 문제를 읽고 공식을 작성해보았고, 이런식을 세웠다. 1. Brown = (Yellow 의 열 * 2 ) + { 2 ( Yellow + 2) } 충족 2. Yellow = ( Yellow 가로 값 * 세로 값 ) 충족이게 왜 이렇게 세워지냐면, 위의 [18, 6] 일 때, 6 이 Yellow 값인데, 3*2 인 Yellow 를 Brown이 감싸는 것에대해서 오류가 발생한다. Yellow 값 또한, 약수로 분해했다. [1, 6] , [2, 3], [3, 2], [6, 1] 총 4개의 집합이 나온다. 여기서 중복되는 조합은 필요없고, 가로가 세로보다 길기 때문에 [1, 6] =&gt; [6, 1] , [2, 3] =&gt; [3, 2] 로 변경해서 필터링해서 패스했다.결국 크게 보면 아래와 같이 3단계로 풀이가 정의된다. 1. Yellow 의 값을 약수 분해하라 2. Brown 공식과 Yellow 공식에 맞지 않으면 패스해라. 3. 최종적으로 나온 가로, 세로는 Yellow 의 가로 세로 값이기 때문에, 가로세로 두께인 2씩 더해서 출력하라. ( 세로의 경우 위 1 아래 1 , 가로의 경우 왼쪽 1 오른쪽 1 개씩 더있기 때문에, )<h3>방향 잘못 잡은 코드 작성 ( C# )</h3><pre spellcheck="false"><code>using System;

public class Solution {
 public int[] solution(int brown, int yellow) {
 int[] answer = new int[2];
 
 Tuple&lt;int, int&gt; pair = new Tuple&lt;int, int&gt;(0,0);
 int diffRecordValue = int.MaxValue;

 for(int i = 1; i &lt; 2000000; ++i)
 {
 if (i &gt; (yellow)) break;

 // yellow는 무조건 사각형이라는 가정, 정사각형, 직사각형 모두
 int balance = yellow % i;

 if (balance != 0) continue;
 // 사각형이 아니고 남으면 패스

 int div = yellow / i; // 나눠진 수

 int diffValue = Math.Abs(i - div);// 절댓값으로 차이를 구함. =&gt; 가장 가로세로 차이가 없는 이쁜 사각형을 구하기 위함.

 if (diffRecordValue &lt; diffValue) continue;
 diffRecordValue = diffValue;

 if ( i &gt; div )
 pair = new Tuple&lt;int, int&gt;(i, div);
 else
 pair = new Tuple&lt;int, int&gt;(div,i); 
 
 // 더 큰수가 가로
 }

 answer[0] = (pair.Item1) + 2;
 answer[1] = (pair.Item2) + 2;
 return answer;
 }
}</code></pre><h3>방향 잘못 잡은 결과 </h3><img src="https://image.until.blog/sin0105/article/1716880342820" alt="until-330"><h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

public class Solution {
 public int[] solution(int brown, int yellow) {
 int[] answer = new int[2];
 
 // 공식
 // Brown = ( Yellow열 * 2 ) + 2 ( Yellow + 2 ) 성립

 // 분해된 수를 먼저 담아놓는다. 
 List&lt;Tuple&lt;int,int&gt;&gt; combinationList =new List&lt;Tuple&lt;int, int&gt;&gt;();

 for(int i = 1; i &lt;= yellow; ++i)
 {
 // Yellow 수 까지 분해해서 약수를 담아놓는다.
 int balance = yellow % i;
 if (balance != 0) continue; // 나누어 떨어지지 않으면 담을 필요 없다. 

 int div = yellow / i;
 if (combinationList.Exists(rhs =&gt; rhs.Item1 == div &amp;&amp; rhs.Item2 == i) == true) continue;
 if (combinationList.Exists(rhs =&gt; rhs.Item1 == i &amp;&amp; rhs.Item2 == div) == true) continue;
 // 중복된 애들 필터링 

 if (div &gt; i)
 combinationList.Add(new Tuple&lt;int, int&gt;(div, i));
 else
 combinationList.Add(new Tuple&lt;int, int&gt;(i,div));
 }

 // 이제 루프 돌면서 공식에 충족하는 애들을 추린다
 // Brown = ( Yellow + 2 ) + 2 ( Yellow + 2 ) 성립
 // Yellow = div * i 가 Yellow 성립

 for (int i = 0; i &lt; combinationList.Count; ++i)
 {
 var keyPair = combinationList[i];
 if (brown != (2* keyPair.Item1) + (2 * (keyPair.Item2 + 2))) continue;
 if (yellow != (keyPair.Item1 * keyPair.Item2)) continue;

 answer[0] = keyPair.Item1 + 2;
 answer[1] = keyPair.Item2 + 2;
 break;
 } 
 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1716880421097" alt="until-331">

코딩테스트 항해99 클럽 - 3일차 

[코딩테스트 일지 - 99클럽] 3일차 - 카펫

<h3>코딩 테스트 준비 일지 8 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/evaluate-boolean-binary-tree/description/">Evaluate Boolean Binary Tree</a></li><li>난이도 : 중하</li></ul>You are given the <code spellcheck="false">root</code> of a full binary tree with the following properties:<ul class="tight" data-tight="true"><li>Leaf nodes have either the value <code spellcheck="false">0</code> or <code spellcheck="false">1</code>, where <code spellcheck="false">0</code> represents <code spellcheck="false">False</code> and <code spellcheck="false">1</code> represents <code spellcheck="false">True</code>.</li><li>Non-leaf nodes have either the value <code spellcheck="false">2</code> or <code spellcheck="false">3</code>, where <code spellcheck="false">2</code> represents the boolean <code spellcheck="false">OR</code> and <code spellcheck="false">3</code> represents the boolean <code spellcheck="false">AND</code>.</li></ul>The evaluation of a node is as follows:<ul class="tight" data-tight="true"><li>If the node is a leaf node, the evaluation is the value of the node, i.e. <code spellcheck="false">True</code> or <code spellcheck="false">False</code>.</li><li>Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.</li></ul>Return the boolean result of evaluating the <code spellcheck="false">root</code> node.A full binary tree is a binary tree where each node has either <code spellcheck="false">0</code> or <code spellcheck="false">2</code> children.A leaf node is a node that has zero children.Example 1:<img src="https://assets.leetcode.com/uploads/2022/05/16/example1drawio1.png" alt=""><pre spellcheck="false"><code>Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The above diagram illustrates the evaluation process.
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.</code></pre>Example 2:<pre spellcheck="false"><code>Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.
</code></pre>Constraints:<ul class="tight" data-tight="true"><li>The number of nodes in the tree is in the range <code spellcheck="false">[1, 1000]</code>.</li><li><code spellcheck="false">0 &lt;= Node.val &lt;= 3</code></li><li>Every node has either <code spellcheck="false">0</code> or <code spellcheck="false">2</code> children.</li><li>Leaf nodes have a value of <code spellcheck="false">0</code> or <code spellcheck="false">1</code>.</li><li>Non-leaf nodes have a value of <code spellcheck="false">2</code> or <code spellcheck="false">3</code>.</li></ul><h3>문제 풀이 접근</h3>이 문제는 단순 경로 탐색처럼 진행하면 되는 문제처럼 보였는데, 탐색 이후 처리가 더 중요했던 문제였다.이 문제를 봤을때, 딱 해결 방법이 DFS로 하는것이 좋아보여서, DFS 말고 다른 방법은 고려하지 않았다. 딱 문제의 생김새가 부모의 Root 노드가 0,1 이 아니고 2,3 이면서 left, right 가 null 일때를 참고해서 계산한 후에 내 root 의 value 값을 갱신하면 되는것 처럼 생겼다.다행히 풀이 방법이 틀리지 않아서 문제를 용이하게 풀었으나, 중간에 조금 해맸다. 받은 데이터의 value는 어차피 중요하지 않아서 덮어씌워도 됐었는데, stack 으로 탐색한 경로를 수집하다가 나중에 다 수집하고나서 결과를 연산하는 방식으로 하니까 아무래도 연산하는 순서나 이런 부분에서 꼬이는 것이 많이 있었다. 그래서 이 방법은 시원하게 폐기하고 stack 지워버리고 재귀로 해결했다.문제를 푸는 플로우는 다음과 같다. 1. DFS를 만들고, 바로 left, right 순으로 순회시킨다. 예외 처리로는 left,right 가 모두 null 인 경우로 처리한다. 2. 이후 left, right 순으로 순회한 다음 root.value 가 2,3 인 경우 OR, AND 의 경우 값만 처리해주고 결과를 bool 값으로 리턴한다. 3. 추가로 첫 입력 데이터 root 가 0, 1 으로 하나만 들어오는 경우의 값도 처리하여 종료해준다. ( 이때는 바로 root.Value 를 Convert.ToBoolean()으로 변수를 컨버팅해서 반환하면 된다)<h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public int val;
 * public TreeNode left;
 * public TreeNode right;
 * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
 public class Solution
 {
 public bool EvaluateTree(TreeNode root)
 {
 if (root.left == null &amp;&amp; root.right == null)
 return Convert.ToBoolean(root.val);

 bool dd = DFS(root);
 return dd;
 }

 public bool DFS(TreeNode root) 
 {
 if (root.left == null &amp;&amp; root.right == null)
 return false;

 DFS(root.left);
 DFS(root.right);

 if (root.left == null &amp;&amp; root.right == null)
 return false;

 switch(root.val)
 {
 case 2:
 root.val = (root.left.val == 0 &amp;&amp; root.right.val == 0) ? 0 : 1;
 break;
 case 3:
 root.val = (root.left.val == 1 &amp;&amp; root.right.val == 1) ? 1 : 0;
 break;
 }

 return Convert.ToBoolean(root.val);
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717353024205" alt="until-399"><h3>프로젝트에서 바로 돌릴 수 있는 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;

namespace CodingTestProj
{
 public class TreeNode
 {
 public int val;
 public TreeNode left;
 public TreeNode right;
 public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
 {
 this.val = val;
 this.left = left;
 this.right = right;
 }
 }

 /* Condition 
 * 1 . FULL BT
 * 
 * 
 * 
 * 
 */

 internal class Program
 {
 static void Main(string[] args)
 {
 TreeNode node1 = new TreeNode(3);
 TreeNode node2 = new TreeNode(3);
 TreeNode node3 = new TreeNode(2);
 TreeNode node4 = new TreeNode(0);
 TreeNode node5 = new TreeNode(0);
 TreeNode node6 = new TreeNode(3);
 TreeNode node7 = new TreeNode(2);
 TreeNode node8 = new TreeNode(1);
 TreeNode node9 = new TreeNode(3);
 TreeNode node10 = new TreeNode(1);
 TreeNode node11 = new TreeNode(1);
 TreeNode node12 = new TreeNode(2);
 TreeNode node13 = new TreeNode(1);
 TreeNode node14 = new TreeNode(1);
 TreeNode node15 = new TreeNode(1);


 node1.left = node2;
 node1.right = node3;

 node2.left = node4;
 node2.right = node5;

 node3.left = node6;
 node3.right = node7;

 // 4 , 5 X
 node6.left = node8;
 node6.right = node9;

 node7.left = node10;
 node7.right = node11;

 node9.left = node12;
 node9.right = node13;

 node12.left = node14;
 node12.right = node15;

 Solution solution = new Solution();
 solution.EvaluateTree(node1);
 }
 }

 public class Solution
 {
 public bool EvaluateTree(TreeNode root)
 {
 if (root.left == null &amp;&amp; root.right == null)
 return Convert.ToBoolean(root.val);

 bool dd = DFS(root);
 return dd;
 }

 public bool DFS(TreeNode root) 
 {
 if (root.left == null &amp;&amp; root.right == null)
 return false;

 DFS(root.left);
 DFS(root.right);

 if (root.left == null &amp;&amp; root.right == null)
 return false;

 switch(root.val)
 {
 case 2:
 root.val = (root.left.val == 0 &amp;&amp; root.right.val == 0) ? 0 : 1;
 break;
 case 3:
 root.val = (root.left.val == 1 &amp;&amp; root.right.val == 1) ? 1 : 0;
 break;
 }

 return Convert.ToBoolean(root.val);
 }
 }
}</code></pre>

코딩테스트 항해99 클럽 - 8일차 - Beginner

[코딩테스트 일지 - 99클럽] 8일차 - Evaluate Boolean Binary Tree

<h3>코딩 테스트 준비 일지 10 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">프로그래머스</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42860">조이스틱</a></li><li>난이도 : 상</li><li>풀이시간 : 03 h ++</li></ul><h6>문제 설명</h6>조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA조이스틱을 각 방향으로 움직이면 아래와 같습니다.<pre spellcheck="false"><code>▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)</code></pre>예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.<pre spellcheck="false"><code>- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.</code></pre>만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.<h5>제한 사항</h5><ul class="tight" data-tight="true"><li>name은 알파벳 대문자로만 이루어져 있습니다.</li><li>name의 길이는 1 이상 20 이하입니다.</li></ul><h5>입출력 예</h5>name return "JEROEN" 56 "JAN" 23<h3>문제 풀이 접근</h3>이번 문제풀이는.. 도저히 미들러의 문제가 아니었다. 라고 생각이 들었다. 먼저 글자수대로 A를 준다는 것에도 잘 이해를 못했고, 이동하는것도 이해못했고, 그냥 모든걸 이해할 수 없던 문제였다.이 문제의 어려운 부분은 커서 이동의 최적화였다. 여러 사람들의 문제풀이가 있으나, 대부분의 문제풀이는 식과 Math.Min 을 이용하여 최소 이동을 구하는 것이었다. 커서 상하 이동은 단순히 아스키코드 개념을 알면 Math.Min(element - 'A' , 'Z' - element + 1) 과 같은 방식으로 충분히 구할 수 있는 것을 확인할 수 있다.이제 커서 이동이 가장 문제인데, 커서 이동은 준비 과정이 있다.가장 단순한 커서 이동은 오른쪽으로 이동하는 것인데, 이 이동은 정말 단순하다. 왼쪽 끝에서 오른쪽 끝으로 쭉 이동하는 것이다. 그래서 이런 식이 나온다. int move = name.Length -1; &lt;&lt; 이걸 기준으로 잡는다.그 이후에 어떻게 하느냐, 이제 왼쪽으로 가는것이 최적인지 오른쪽으로 가는것이 최적인지 정하는 것이다. 결국 나는 이 문제를 최대 55점 까지는 받고 풀이를 보았으나, 처음 보았을 때, 이게 무슨 말도 안되는 식인지 이해가 안갔다.나는 움직일 때마다, 인덱스를 저장해주고, 그 이동값에 대해서 계속 결과 반환값인 answer에 더해준다고 생각했으나, 많은 사람들의 풀이는 그 방식이 아니었다.이 문제에서 최소 커서를 조작하는 것이 핵심이므로, 1) 길이대로 오른쪽으로 이동하는 경우 2) 오른쪽으로 가다가, A 연속을만나 원점으로 돌아가서 맨 뒤에서 해결하는 방식 3) 맨뒤부터 순회해서 A 연속을 만나 원점으로 돌아가서 맨 앞에서 주르륵 해결하는 방식저 3 가지를 비교해서 최솟값을 건들면된다. PPAAAPER 라고 있을때, 3가지의 moveCount 를 만들 수 있다.1) length -1 = 7 2) PPAAAPER , PP 다음 ' A ' 를 만나 i 를 다시 원점으로 돌리고 A 연속의 뒤로 돌아가서 우측으로 이동하는 방식 =&gt; (2 * i) + (string.Length - nextIndex) 3) PPAAAPER , PPAAA 'P' 이쪽 P 부터 시작해 오른쪽 끝으로 순회하고 다시 A 연속의 왼쪽 지점으로 돌아와서 오른쪽으로 순회하는 방식 =&gt; i + 2 * (string.Length - nextIndex)<h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
public class Solution {
public int solution(string name)
{
int answer = 0;
FindCountUpDown(ref name,ref answer);
MoveCount(ref name, ref answer);
return answer;
} public void FindCountUpDown(ref string name,ref int answer)
 // Up Down 하는 수들만 모아서 반환
 {
 for (int i = 0; i &amp;lt; name.Length; ++i)
 {
 char target = name[i];
 answer += Math.Min(target - 'A', 'Z' - target + 1) ;
 }
 }
 public void MoveCount(ref string name, ref int answer)
 {
 int move = name.Length - 1; // 최대값

 for (int i = 0; i &amp;lt; name.Length; ++i)
 {
 if (i == name.Length - 1) continue;

 int nextIndex = i + 1;
 while(nextIndex &amp;lt; name.Length &amp;amp;&amp;amp; name[nextIndex] == 'A')
 nextIndex++;

 move = Math.Min(move, (2 * i) + (name.Length) - nextIndex);
 move = Math.Min(move, i + 2* ((name.Length) - nextIndex));
 }
 answer += move;
 }}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717520902703" alt="until-408">

코딩테스트 항해99 클럽 - 10일차

[코딩테스트 일지 - 99클럽] 10일차 - 조이스틱

CodingTest

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/86491">최소직사각형</a></li><li>사용언어 : C#</li><li>난이도 : 하 ~ 중</li><li>풀이시간 : 45m 48s</li><li>유형 : 문제이해, 2차원 배열</li></ul><h6>문제 설명</h6>명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.명함 번호 가로 길이 세로 길이 1 60 50 2 30 70 3 60 30 4 80 40가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.<hr><h5>제한사항</h5><ul><li>sizes의 길이는 1 이상 10,000 이하입니다.<ul><li>sizes의 원소는 [w, h] 형식입니다.</li><li>w는 명함의 가로 길이를 나타냅니다.</li><li>h는 명함의 세로 길이를 나타냅니다.</li><li>w와 h는 1 이상 1,000 이하인 자연수입니다.</li></ul></li></ul><hr><h5>입출력 예</h5>sizes result [[60, 50], [30, 70], [60, 30], [80, 40]] 4000 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133<hr><h5>입출력 예 설명</h5>입출력 예 #1 문제 예시와 같습니다.입출력 예 #2 명함들을 적절히 회전시켜 겹쳤을 때, 3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.입출력 예 #3 명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.<h3>문제 풀이 접근</h3>이 문제는, 가로x세로에서 모든 사각형을 포함하는 것 중 가장 작은 사각형을 만들면 되는 문제다. 문제에서 명함을 회전해서 포함한다. 라는 힌트를 줬기 때문에, 가로 &lt; 세로 의 케이스는 무조건 가로와 세로를 바꾸어주면 된다.문제를 잘못 읽어서 가로, 세로를 쌍으로보고 인덱스를 찾은 뒤 해당 인덱스 가로*세로 하면서 시간을 썻는데, 이 방법은 틀리다. 가로 세로는 따로 봐야한다.이 문제의 플로우는, 1. 받은 2차원 배열을 체크하여 가로 &lt; 세로의 케이스를 찾는다. 2. 그 다음 변경해서 list에 넣어준다. 3. 포함하는 것 중 가장 작은 최소 직사각형을 뽑는것이 주 목적이니, maxWidth, maxHeight 값은 Int32 표현범위중 제일 큰 값을 설정해놓는다. 4. list를 Loop 하면서 순회하는 원소 기준으로 list를 FindAll 함수를 이용해 찾는다. 이렇게 찾은 갯수가 현재 리스트 카운트와 동일하면 현재 원소는 가로 원소일땐 가로를 포함, 세로 원소일땐 세로를 포함한다. 리스트 내 고로 제일 큰 값이다. 5. 이 값 중 최소 직사각형을 뽑는 것이 목적이기 때문에 maxWidth &gt;= Width 를 비교하여 현재 저장된 원소보다 작다면 값을 넣어준다. 6. 이렇게 구해낸 maxWidth, maxHeight를 사각형의 크기를 구하는 공식에 따라 곱해서 반환한다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

public class Solution {
 public int solution(int[,] sizes) {
 int answer = 0;
 List&lt;Tuple&lt;int, int&gt;&gt; list = new List&lt;Tuple&lt;int, int&gt;&gt;();

 for(int i = 0; i &lt; sizes.GetLength(0); ++i)
 {
 int width = sizes[i, 0];
 int height = sizes[i, 1];

 if(width &lt; height)
 {
 int temp = height;
 height = width;
 width = temp;
 }

 list.Add(new Tuple&lt;int, int&gt;(width, height));
 }

 int maxWidth = Int32.MaxValue;
 int maxHeight = Int32.MaxValue;

 for(int i = 0; i &lt; list.Count; ++i)
 {
 var element = list[i];
 var width = element.Item1;
 var height = element.Item2;

 var countfst = list.FindAll(rhs =&gt; rhs.Item1 &lt;= width).Count;
 var countsnd = list.FindAll(rhs =&gt; rhs.Item2 &lt;= height).Count;

 if(list.Count == countfst)
 {
 if(maxWidth &gt;= width)
 maxWidth = width;
 }

 if(list.Count == countsnd)
 {
 if (maxHeight &gt;= height)
 maxHeight = height;
 }
 }

 answer = maxWidth * maxHeight;
 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724258703183" alt="until-1261">

혼자서 다시푸는 코딩테스트 준비 일지 - 16

코딩테스트 준비 - 최소직사각형

<h3>코딩 테스트 준비 일지 5 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">프로그래머스</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/43165">타겟 넘버</a></li><li>난이도 : 중</li></ul>n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.<pre spellcheck="false"><code>-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3</code></pre>사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>주어지는 숫자의 개수는 2개 이상 20개 이하입니다.</li><li>각 숫자는 1 이상 50 이하인 자연수입니다.</li><li>타겟 넘버는 1 이상 1000 이하인 자연수입니다.</li></ul><h5>입출력 예</h5>numbers target return[1, 1, 1, 1, 1] 3 5[4, 1, 2, 1] 4 2<h5>입출력 예 설명</h5>입출력 예 #1문제 예시와 같습니다.입출력 예 #2<pre spellcheck="false"><code>+4+1-2+1 = 4
+4-1+2-1 = 4</code></pre><ul class="tight" data-tight="true"><li>총 2가지 방법이 있으므로, 2를 return 합니다.</li></ul><h3>문제 풀이 접근</h3>결과적으로 오늘 혼자 풀었느냐 하면 아니다.문제를 보자마자, 핵심 키워드를 확인을 해보니 DFS/BFS 였다. 문제에서 나타난 핵심은 1. 순서는 그대로다. 2. 타겟 넘버에 맞다면, 여기서 카운트 하나 올리고, 총 카운트를 리턴한다. 이 문제를 풀면서 어느정도 트리를 생각하여 계속 트리를 그리고 왜 스왑이 없지? 경로들은 어떻게 담지? 하면서 문제에서도 요구하지 않은 사양에 빠져있었다.그리하여 문제 푸는시간이 약 1시간 40분 정도 걸렸고, 같은 반에 있으신 분께 도움을 받았다. 도움 받고 다시 문제 푸는 방식을 정립하고 아래와 같이 나왔다.<ol class="tight" data-tight="true"><li>경로를 담을 필요는 없다.</li><li>스왑도 생각하지마라. 왜 생각하는겨</li><li>+ - 경우를 더하면서 재귀돌리면 된다.</li></ol><h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
public class Solution
{
public int solution(int[] numbers, int target)
{
int answer = 0;
calc(numbers, 0, 0, target, ref answer);
return answer;
}
public static void calc(int[] arr, int sum, int depth, int target, ref int answer)
{
if((arr.Length == depth) &amp;&amp; (sum == target))
{
++answer;
return;
} // 뎁스가 마지막에 도달했으며, 여기서 타겟넘버와 값이 같을때, ++ 한다 if (arr.Length &amp;lt;= depth)
 return; // 뎁스가 길이를 넘어갔을때, 종료한다.

 calc(arr, sum + arr[depth], depth + 1, target, ref answer); 
 // + 의 경우
 calc(arr, sum + (arr[depth] * -1), depth + 1, target, ref answer);
}}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717077690298" alt="until-369">

코딩테스트 항해99 클럽 - 5일차

[코딩테스트 일지 - 99클럽] 5일차 - 타겟 넘버

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/explore/">LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/valid-parentheses/">Valid Parentheses</a></li><li>사용언어 : C#</li><li>난이도 : 하</li><li>풀이시간 : 33m</li><li>유형 : 스택, 문자열 </li></ul>Given a string&nbsp;<code spellcheck="false">s</code>&nbsp;containing just the characters&nbsp;<code spellcheck="false">'('</code>,&nbsp;<code spellcheck="false">')'</code>,&nbsp;<code spellcheck="false">'{'</code>,&nbsp;<code spellcheck="false">'}'</code>,&nbsp;<code spellcheck="false">'['</code>&nbsp;and&nbsp;<code spellcheck="false">']'</code>, determine if the input string is valid.An input string is valid if:<ol><li>Open brackets must be closed by the same type of brackets.</li><li>Open brackets must be closed in the correct order.</li><li>Every close bracket has a corresponding open bracket of the same type.</li><li></li></ol>Example 1:<pre spellcheck="false"><code>Input: s = "()"
Output: true
</code></pre>Example 2:<pre spellcheck="false"><code>Input: s = "()[]{}"
Output: true
</code></pre>Example 3:<pre spellcheck="false"><code>Input: s = "(]"
Output: false
</code></pre>&nbsp;Constraints:<ul><li><code spellcheck="false">1 &lt;= s.length &lt;= 104</code></li><li><code spellcheck="false">s</code>&nbsp;consists of parentheses only&nbsp;<code spellcheck="false">'()[]{}'</code>.</li></ul><h3>문제 풀이 접근</h3>이 문제는, 여러 케이스를 생각해서 이렇게 풀었는데, 케이스 바로나왔으면 10분만에 풀었을 것 같다. 헷갈렸던 점은, 1. '(' 가 나오면 무조건 뒤에 ')' 나오도록 하는가? 2. 속괄호가 없을까? [()] 이런거.. 1,2번이 모두 참이고 맞다면 문제는 10분도 필요없다 5분컷인데, s[index] ,s[index+1] 해서 비교하면 되는거라.. 해보니까 속괄호도 있고, 처음에 닫힌 브라킷으로 주는 경우도 있고해서 여러 예외가 필요했다.문제 해결 플로우는, 1. 여는 브라킷 ' ( ' , ' [ ' , ' { ' 등이 나오면 Stack에 Push한다. 2. 이후 닫는 브라킷 ' ) ' , ' ] ' , ' } ' 이 나오면 Peek 으로 체크하고 Pop 한다. 3. 이 모든 과정을 수행해서 짝이 맞는다면 Stack 은 비어있는게 정상. 남아있다면 어딘가 닫히는게 없거나, 열리는게 없는데 닫히는 문자를 가져오거나 둘중하나. 고로 false 다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System.Collections.Generic;

public class Solution {
 public bool IsValid(string s)
 {
 bool answer = false;
 Stack&lt;Char&gt; st = new Stack&lt;Char&gt;();

 if ((s.Length == 0) || (s[0] == ')') || (s[0] == '}') || (s[0] == ']'))
 return false;


 for (int i = 0; i &lt; s.Length; ++i)
 {
 var elem = s[i];

 if (elem == '(' || elem == '{' || elem == '[')
 {
 st.Push(elem);
 continue;
 }

 if (elem == ')' || elem == '}' || elem == ']')
 {
 char sElem;

 if(st.Count == 0)
 st.Push(elem);

 sElem = st.Peek();

 if (sElem == '(' &amp;&amp; elem == ')')
 {
 st.Pop();
 continue;
 }

 if (sElem == '[' &amp;&amp; elem == ']')
 {
 st.Pop();
 continue;
 }

 if (sElem == '{' &amp;&amp; elem == '}')
 {
 st.Pop();
 continue;
 }

 break;
 }
 }

 answer = st.Count == 0 ? true : false;

 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1722400493650" alt="until-1157"><h3>1,2 번 가설 테스트 코드 (C#) - 실패</h3><pre spellcheck="false"><code>public class Solution {
 public bool IsValid(string s) {

 for(int i = 0; i &lt; s.Length-1; ++i)
 {
 var elem = s[i];
 var elemNext = s[i+1];
 
 if((elem == '(') &amp;&amp; (elemNext == ')') == false)
 return false;
 
 if((elem == '[') &amp;&amp; (elemNext == ']') == false)
 return false;
 
 if((elem == '{') &amp;&amp; (elemNext == '}') == false)
 return false;
 }
 
 return true;
 }
}</code></pre><img src="https://image.until.blog/sin0105/article/1722400531315" alt="until-1158">

혼자서 다시푸는 코딩테스트 준비 일지 - 6

코딩테스트 준비 - Valid Parentheses

[자료구조와실습]

<h2>1. 그래프 Graph</h2><blockquote>연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조</blockquote>객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다.<img src="https://image.until.blog/white/article/1727168137992.png" alt="until-1471"><h2>2. 그래프 용어 정리</h2>그래프에서 두 정점 V1과 V2를 연결하는 간선 (V1, V2)가 있을 때, 두 정점 V1과 V2를 인접(adjacent)되어 있다고 하고, 간선 (V1, V2)는 정점 V1과 V2에 부속(incident)되어 있다고 한다.<ul><li>이때 인접(adjacent)은 정점과 정점의 관계이다. </li></ul><img src="https://image.until.blog/white/article/1727168915549.png" alt="until-1473"><ul><li>다음과 같은 그래프에서 정점 1과 인접한 정점은 4와 3이고, 정점 1에 부속되어 있는 간선은 (1, 4)와 (1, 3)이다.</li></ul><hr>[용어 설명용 그림]<img src="https://image.until.blog/white/article/1727169964100.png" alt="until-1476"><h3>2.1. 차수 degree</h3><blockquote>정점에 부속되어 있는 간선의 수, 즉 한 정점에 인접한 정점의 개수이다.</blockquote><ul><li>무방향 그래프<ul><li>무방향 그래프에서 정점 1의 차수는 2, 정점 3의 차수는 3이다.</li></ul></li><li>방향 그래프<ul><li><code spellcheck="false">방향 그래프의 정점의 차수 = 진입차수 + 진출 차수</code><ul><li>진입차수(in-degree) : 정점을 머리로 하는 간선의 수</li><li>진출 차수(out-degree) : 정점을 꼬리로 하는 간선의 수</li></ul></li><li>방향 그래프에서 정점 4의 진입차수는 1, 진출차수는 2이다. 따라서 정점 4의 전체 차수는 (진출차수+진입차수) 이므로 3이다.</li></ul></li></ul><h3>2.2. 경로 path</h3><blockquote>그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것, 즉 정점 V1에서 V2까지 간선으로 연결된 정점을 순서대로 나열한 리스트</blockquote><ul><li>무방향 그래프에서 정점 1에서 정점 2까지는 1-3-2 경로와 1-3-4-2 경로, 1-4-2 경로, 1-4-3-2 경로가 있다.</li></ul><h3>2.3. 경로 길이 path length</h3><blockquote>경로를 구성하는 간선의 수</blockquote><h3>2.4. 단순 경로 simple path</h3><blockquote>모두 다른 정점으로 구성된 경로</blockquote><ul><li>무방향 그래프에서 정점 1부터 정점 2까지의 경로 1-4-2는 단순경로이고, 경로 1-4-3-1-4-2는 단순경로가 아니다.</li></ul><h3>2.5. 사이클 cycle</h3><blockquote>단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로</blockquote><ul><li>무방향 그래프에서 단순경로 1-3-2-4-1과 방향 그래프에서 단순경로 1-3-1은 사이클이 된다.</li></ul><h3>2.6. DAG Directed Acyclic Graph</h3><blockquote>방향 그래프이면서 사이클이 없는 그래프</blockquote><h3>2.7. 연결 그래프 connected graph</h3><blockquote>서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프, 즉 떨어져있는 정점이 없는 그래프</blockquote>그래프에서 두 정점 V1과 V2까지의 경로가 있으면 정점 V1과 V2가 연결(connected)되었다고 한다. 따라서 트리는 사이클이 없는 연결 그래프라고 할 수 있다.<h3>2.8. 단절 그래프 disconnected graph</h3><blockquote>연결되지 않은 정점이 있는 그래프</blockquote>[연결 그래프와 단절 그래프]<img src="https://image.until.blog/white/article/1727172439548.png" alt="until-1477"><h2>3. 그래프의 종류</h2><h3>3.1. 무방향 그래프 undirected graph</h3><blockquote>두 정점을 연결하는 간선에 방향이 없는 그래프</blockquote>정점 V1과 정점 V2를 연결하는 간선을 (V1, V2)로 표현한다. (V1, V2)와 (V2, V1)은 같은 간선을 의미한다. (순서가 없음)<img src="https://image.until.blog/white/article/1727176582469.png" alt="until-1479"><h3>3.2. 방향 그래프 directed graph, 다이그래프 digraph</h3><blockquote>간선에 방향이 있는 그래프</blockquote>정점 V1에서 정점 V2를 연결하는 간선 즉, V1 -&gt; V2를 &lt;V1, V2&gt;로 표현한다. 이때, V1를 꼬리(tail), V2를 머리(head)라고 한다. &lt;V1, V2&gt;, &lt;V2, V1&gt;은 서로 다른 간선을 의미하므로 표시에 유의해야한다.<img src="https://image.until.blog/white/article/1727176601391.png" alt="until-1480"><h3>3.3. 완전 그래프 complete graph</h3><blockquote>각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프</blockquote>정점이 n개인 무방향 그래프에서의 최대 간선 수는 <code spellcheck="false">n(n-1)/2</code>개이고, 정점이 n개인 방향 그래프는 두 정점에 대해서 방향이 다른 두 개의 간선을 연결할 수 있으므로 최대 간선 수는 <code spellcheck="false">n(n-1)</code>개이다.<h3>3.4. 부분 그래프 subgraph</h3><blockquote>원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프</blockquote>이때, G2는 G1의 부분그래프이다.V(G') ⊆ V(G), E(G') ⊆ E(G)<img src="https://image.until.blog/white/article/1727177438157.png" alt="until-1481"><h3>3.5. 가중 그래프 weight graph, 네트워크 network</h3><blockquote>정점을 연결하는 간선에 가중치(weight)를 할당한 그래프</blockquote><img src="https://image.until.blog/white/article/1727177628840.png" alt="until-1482">

#1. 그래프

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/">LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/">Count Pairs Whose Sum is Less than Target</a></li><li>사용언어 : C#</li><li>난이도 : 최하</li><li>풀이시간 : 1m 49s</li><li>유형 : 반복문, 사칙연산</li></ul>Given a 0-indexed integer array <code spellcheck="false">nums</code> of length <code spellcheck="false">n</code> and an integer <code spellcheck="false">target</code>, return the number of pairs <code spellcheck="false">(i, j)</code> where <code spellcheck="false">0 &lt;= i &lt; j &lt; n</code> and <code spellcheck="false">nums[i] + nums[j] &lt; target</code>. &nbsp;Example 1:<pre spellcheck="false"><code>Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 &lt; 1 and nums[0] + nums[1] = 0 &lt; target
- (0, 2) since 0 &lt; 2 and nums[0] + nums[2] = 1 &lt; target 
- (0, 4) since 0 &lt; 4 and nums[0] + nums[4] = 0 &lt; target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.
</code></pre> Example 2:<pre spellcheck="false"><code>Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 &lt; 1 and nums[0] + nums[1] = -4 &lt; target
- (0, 3) since 0 &lt; 3 and nums[0] + nums[3] = -8 &lt; target
- (0, 4) since 0 &lt; 4 and nums[0] + nums[4] = -13 &lt; target
- (0, 5) since 0 &lt; 5 and nums[0] + nums[5] = -7 &lt; target
- (0, 6) since 0 &lt; 6 and nums[0] + nums[6] = -3 &lt; target
- (1, 4) since 1 &lt; 4 and nums[1] + nums[4] = -5 &lt; target
- (3, 4) since 3 &lt; 4 and nums[3] + nums[4] = -9 &lt; target
- (3, 5) since 3 &lt; 5 and nums[3] + nums[5] = -3 &lt; target
- (4, 5) since 4 &lt; 5 and nums[4] + nums[5] = -8 &lt; target
- (4, 6) since 4 &lt; 6 and nums[4] + nums[6] = -4 &lt; target
</code></pre>Constraints:<ul><li><code spellcheck="false">1 &lt;= nums.length == n &lt;= 50</code></li><li><code spellcheck="false">-50 &lt;= nums[i], target &lt;= 50</code></li></ul><h3>문제 풀이 접근</h3>문제의 내용이 어렵지 않다. 제약조건 또한 어렵지 않다. 반복문 두개로 타겟 넘버와 비교하여 풀이할 수 있는 내용이다. <h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class Solution {
 public int CountPairs(IList&lt;int&gt; nums, int target) {
 
 int answer = 0;
 
 for(int i = 0; i &lt; nums.Count; ++i)
 {
 for(int j = i + 1; j &lt; nums.Count; ++j)
 {
 int fst = nums[i];
 int snd = nums[j];
 
 if(fst + snd &lt; target)
 ++answer;
 }
 }
 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724176666815" alt="until-1258">

혼자서 다시푸는 코딩테스트 준비 일지 - 14

코딩테스트 준비 - Count Pairs Whose Sum is Less than Target

<h3>코딩 테스트 준비 일지 9 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/">Reverse Odd Levels of Binary Tree</a></li><li>난이도 : 중상</li><li>풀이시간 : 01 h 51 m</li></ul>Given the <code spellcheck="false">root</code> of a perfect binary tree, reverse the node values at each odd level of the tree.<ul class="tight" data-tight="true"><li>For example, suppose the node values at level 3 are <code spellcheck="false">[2,1,3,4,7,11,29,18]</code>, then it should become <code spellcheck="false">[18,29,11,7,4,3,1,2]</code>.</li></ul>Return the root of the reversed tree.A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.The level of a node is the number of edges along the path between it and the root node.&nbsp;Example 1:<img src="https://assets.leetcode.com/uploads/2022/07/28/first_case1.png" alt=""><pre spellcheck="false"><code>Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation: 
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
</code></pre>Example 2:<img src="https://assets.leetcode.com/uploads/2022/07/28/second_case3.png" alt=""><pre spellcheck="false"><code>Input: root = [7,13,11]
Output: [7,11,13]
Explanation: 
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
</code></pre>Example 3:<pre spellcheck="false"><code>Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation: 
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.
</code></pre>Constraints:<ul class="tight" data-tight="true"><li>The number of nodes in the tree is in the range <code spellcheck="false">[1, 214]</code>.</li><li><code spellcheck="false">0 &lt;= Node.val &lt;= 105</code></li><li><code spellcheck="false">root</code> is a perfect binary tree.</li></ul><h3>문제 풀이 접근</h3>이 문제를 접했을 때, 바로 생각난 방식은 DFS 재귀 순회였고, depth % 2 == 0 일때, left, right 의 노드를 스위칭 하는 방식으로 생각해서 코드 구현을 작업했다. 결론으로 말하자면 이 문제는 dfs, bfs 모두 사용해도 상관없으며, 심지어 reverse 돌리는 것도 따로 저장해서 bfs 두번 돌리면서 역순 정렬해도 무방한 문제다. (유투브에 있는 대부분의 풀이 동영상이 이런 방식을 채택하고 있다. )이 문제를 풀면서 단순히 왼, 오의 값을 변경하는데 초점을 맞춰버려서 시간을 오래걸리고 제대로 된 구현을 하는것이 힘들었다. 결국 다른 사람의 풀이를 보면서 어떻게 풀어야 깔끔하고 빠르게 풀지를 체크해 보았는데, 이미 문제에서 힌트는 전부 주어지고 있었다. 완벽한 2진 트리를 준다는 것. 결국 여기서 알 수 있는 정보는 왼쪽 끝단, 오른쪽 끝단 이 둘은 서로 매칭되며, 왼쪽 끝의 오른쪽 노드와 오른쪽 끝의 왼쪽노드도 매칭된다. 결국, 모든 노드는 매칭이 된다는 것이다.플로우는 아래와 같다. 1. Left는 Left 쪽으로 계속 뻗어나간다. 2. 마찬가지로 Right는 Right 쪽으로 계속 뻗어나간다. 3. 이후 그 다음 왼쪽 끝에서 오른쪽 노드, 오른쪽 끝에서 왼쪽노드 처럼 안쪽으로 조여가며 매칭된 것을 뒤집어 준다.<h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public int val;
 * public TreeNode left;
 * public TreeNode right;
 * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */

public class Solution {

 public TreeNode ReverseOddLevels(TreeNode root) {
 DFS(ref root.left,ref root.right, true);
 return root;
 }
 public void DFS(ref TreeNode rootLeft, ref TreeNode rootRight, bool isOdd)
 {
 if(rootLeft == null)
 return;
 
 if(isOdd == true)
 {
 int temp = rootLeft.val;
 rootLeft.val = rootRight.val;
 rootRight.val = temp;
 }
 
 DFS(ref rootLeft.left, ref rootRight.right,!isOdd);
 DFS(ref rootLeft.right,ref rootRight.left, !isOdd);
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717425050186" alt="until-403">

코딩테스트 항해99 클럽 - 9일차

[코딩테스트 일지 - 99클럽] 9일차 - Reverse Odd Levels of Binary Tree

<h3>코딩 테스트 준비 일지 16 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" class="no-underline hover:text-blue-s dark:hover:text-dark-blue-s truncate cursor-text whitespace-normal hover:!text-[inherit]" href="https://leetcode.com/problems/iterator-for-combination/">Iterator for Combination</a></li><li>난이도 : 중</li><li>풀이시간 : 2h 11m</li></ul>Design the <code spellcheck="false">CombinationIterator</code> class:<ul class="tight" data-tight="true"><li><code spellcheck="false">CombinationIterator(string characters, int combinationLength)</code> Initializes the object with a string <code spellcheck="false">characters</code> of sorted distinct lowercase English letters and a number <code spellcheck="false">combinationLength</code> as arguments.</li><li><code spellcheck="false">next()</code> Returns the next combination of length <code spellcheck="false">combinationLength</code> in lexicographical order.</li><li><code spellcheck="false">hasNext()</code> Returns <code spellcheck="false">true</code> if and only if there exists a next combination.</li></ul>&nbsp;Example 1:<pre spellcheck="false"><code>Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next(); // return "ab"
itr.hasNext(); // return True
itr.next(); // return "ac"
itr.hasNext(); // return True
itr.next(); // return "bc"
itr.hasNext(); // return False
</code></pre>&nbsp;Constraints:<ul class="tight" data-tight="true"><li><code spellcheck="false">1 &lt;= combinationLength &lt;= characters.length &lt;= 15</code></li><li>All the characters of <code spellcheck="false">characters</code> are unique.</li><li>At most <code spellcheck="false">104</code> calls will be made to <code spellcheck="false">next</code> and <code spellcheck="false">hasNext</code>.</li><li>It is guaranteed that all calls of the function <code spellcheck="false">next</code> are valid.</li></ul><h3>문제 풀이 접근</h3>금일 문제 역시 한번에 이해하긴 어려웠다. 그도그럴게 문제형식이 오늘은 달랐다. 매일 Main 함수에 클래스 생성해서 호출하면 나와있는 그대로 수행하게하면 됐지만, 오늘은 클래스를 디자인해서 기능을 구현하는 것이었다. 뭐.. 아마 저쪽 릿코드 내부 기능엔 생성자 만들고 Next,HasNext,Next 뭐 떡칠일거같다. for문이나 이런걸로 돌렸겠지..문제풀이의 핵심은 문제에도 기재되어 있듯이 "조합" , 조합이 제일 중요하다. 그리고 "사전적인" 이것도 제일 중요하다 &lt; 이거 때문에 고려안해서 타임리밋 쫘라락 떴다. 난 인덱스 바꿔가면서 순서도 다 돌려서 맞는거만 쓸줄 알았지.. 위 얘기가 뭐냐면 이런것이다. APPLE 가 있고 예를 들자. APPLE, 3 을 준다고하면 첫번째 A 선택하고 PPLE, 두번째 P 선택하고 APLE, 세번째 P 선택하고 APLE, 네번째 L 선택하고 APPE, 다섯번째 E 선택하고 APPL 다돌면 대강 뭐 아래와 같은 문자열들이 나올것이다.APP,APL,APE,ALE,PLE,PEA,PAE,PPA,PPL,PPE 등등 이런것들이 나올텐데, 어차피 여기서 다 사전적인 의미로 정렬 어쩌구를 해버리면 APL, PAL,LPA 다 똑같은거라.. 다돌 필요는 없다. 끄냥 맨앞 인덱스 기준으로 하나잡고 DFS해버리면 다 나온다. 아무튼 이렇게 조합을 만들고, 나머지는 쉽다. Next는 List 에 있는거 인덱스대로 뿌려주면되고, 없으면 안주면되고, HasNext도 List에 인덱스용으로 놔둔 Int 변수가 Count 보다 높으면 False 주고 인덱스 찍을거 있으면 True 주면 끝이다. <h3>실패한 코드</h3><pre spellcheck="false"><code>public class CombinationIterator
 {

 public List&lt;string&gt; list = new List&lt;string&gt;();
 // 메소드 

 public string originalString = string.Empty;
 public int m_iReturnIndex = 0;
 public int m_isplitLength = 0;

 public CombinationIterator(string characters, int combinationLength)
 {
 // 스트링 문자열 하나, 조합 수 

 originalString = characters;
 m_isplitLength = combinationLength;

 for (int i = 0; i &lt; originalString.Length; ++i)
 {
 int index = i;
 List&lt;int&gt; InputIndex = new List&lt;int&gt;();
 InputIndex.Add(i);
 string combiStr = originalString[index].ToString();

 dfsCombination(combiStr, 1, InputIndex);
 }
 }

 public void dfsCombination(string combi, int depth, List&lt;int&gt; IndexList)
 {
 if (depth &gt;= m_isplitLength )
 {
 char[] chars = combi.ToCharArray();
 Array.Sort(chars);
 combi = new String(chars);

 if (list.Contains(combi) == false)
 {
 list.Add(combi);
 }

 return;
 }

 for (int i = 0; i &lt; originalString.Length; ++i)
 {
 if (IndexList.Contains(i) == true) continue; // 이미 조합으로 만들어낸 인덱스는 만들지 않는다.

 string newString = (combi + originalString[i]);
 List&lt;int&gt; newInputIndex = new List&lt;int&gt;();
 newInputIndex.AddRange(IndexList);
 newInputIndex.Add(i);

 dfsCombination(newString, depth + 1, newInputIndex);
 }
 }

 public string Next()
 {

 if (list.Count - 1 &lt; m_iReturnIndex)
 return "";

 string returnStr = list[m_iReturnIndex];
 ++m_iReturnIndex;

 return returnStr;
 }

 public bool HasNext()
 {

 if (list.Count &lt;= m_iReturnIndex)
 return false;

 return true;
 }
 }

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj.Next();
 * bool param_2 = obj.HasNext();
 */</code></pre><h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class CombinationIterator
 {

 public List&lt;string&gt; list = new List&lt;string&gt;();
 // 메소드 

 public string originalString = string.Empty;
 public int m_iReturnIndex = 0;
 public int m_isplitLength = 0;

 public CombinationIterator(string characters, int combinationLength)
 {
 // 스트링 문자열 하나, 조합 수 

 originalString = characters;
 m_isplitLength = combinationLength;
 dfsCombination("" , 0);
 }

 public void dfsCombination(string combi, int start)
 {
 if (combi.Length &gt;= m_isplitLength)
 {
 char[] chars = combi.ToCharArray();
 Array.Sort(chars);
 combi = new String(chars);

 if (list.Contains(combi) == false)
 {
 list.Add(combi);
 }

 return;
 }

 for (int i = start; i &lt; originalString.Length; ++i)
 {
 dfsCombination(combi + originalString[i], i+1);
 }
 }

 public string Next()
 {

 if (list.Count - 1 &lt; m_iReturnIndex)
 return "";

 string returnStr = list[m_iReturnIndex];
 ++m_iReturnIndex;

 return returnStr;
 }

 public bool HasNext()
 {

 if (list.Count &lt;= m_iReturnIndex)
 return false;

 return true;
 }
 }

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj.Next();
 * bool param_2 = obj.HasNext();
 */</code></pre><h3>코드 결과 </h3><img src="https://image.until.blog/sin0105/article/1718634922979" alt="until-534">

코딩테스트 항해99 클럽 - 16일차

[코딩테스트 일지 - 99클럽] 16일차 - Iterator for Combination

<h3>🥅 들어가며</h3>코딩 테스트 준비를 하다보면 배열과 관련해서 구간 합(Range Sum)에 대한 문제를 마주하게 된다.구간합이란 간단하게 말하면 배열의 특정 구간 내의 원소들의 합을 구하는 문제이다. 굳이 코딩 테스트가 아니어도 특정 기간의 통계량을 계산하는 여러 현실 문제에 대해 구간 합은 자주 쓰이는 개념이다. 이러한 구간합을 어떻게 효율적으로 구할 수 있는지 알아보자.<h3>➕ 합 배열의 개념 및 구간 합의 계산</h3>구간합을 시간 복잡도를 고려하여 가장 효율적으로 계산하는 방법은 합배열(Prefix Sum) 이다. 합배열이란 배열의 누적 합을 저장하는 배열이다. 배열 A가 {1, 2, 3, 4, 5} 라면 합배열 S는 {1, 3, 6, 10, 15} 인 식이다. 수식으로는 다음과 같다.<img src="https://image.until.blog/woonideveloper423/article/1718540749059" alt="until-512">이렇게 구한 합배열 S를 이용하여 배열 A의 구간합을 쉽게 구할 수 있다. 예를 들어 배열 A의 인덱스 (i,j)의 구간 합을 구한다 하면 0~j까지의 누적 합에서 0~(i-1)의 누적 합을 빼면 된다. 이를 합배열을 사용한 수식으로 표현하면 다음과 같다.<img src="https://image.until.blog/woonideveloper423/article/1718540793537" alt="until-513"><h3>❓합 배열을 사용해서 구간 합을 구하는 것이 왜 효율적일까?</h3>합 배열을 사용하지 않고 구간합을 계산하는 방법은 구간의 모든 원소를 직접 더하는 방법이다. 다만 이는 시간 복잡도가 O(n) 이며 구간의 크기나 구간의 합을 구하는 개수 등이 클수록 연산 시간은 이에 비례하여 늘어난다. 따라서 시간 제한을 고려한다면 적절한 방법이 아니다.<pre spellcheck="false"><code class="language-java">int rangeSum(int[] numbers, int start, int end) { // 구간 합 수동 구
 int sum = 0;
 for (int i = start; i &lt;= end; i++) { // 시간 복잡도(O(n))
 sum += numbers[i];
 }
 return sum;
}
int result = rangeSum(numbers, 2, 4); // 구간 합을 여러개 구해야 한다면 메서드를 여러 번 실행해야 함
</code></pre>따라서 다음과 같이 합배열을 생성한 후 이미 생성된 합배열의 인덱스를 사용해서 구간 합을 구하는 것이 시간 복잡도 O(1) 로 훨씬 효율적이다.<pre spellcheck="false"><code class="language-java">// 합배열 생성
int[] prefixSum = new int[numbers.length];
prefixSum[0] = numbers[0];
for (int i = 1; i &lt; numbers.length; i++) {
prefixSum[i] = prefixSum[i-1] + numbers[i];
}// 구간 합
int rangeSum(int[] prefixSum, int i, int j) {
if (i == 0) {
return prefixSum[j];
} else {
return prefixSum[j] - prefixSum[i-1]; // 합배열 사용해서 계산 -&gt; 이미 생성된 배열의 요소로 계산 하므로 시간 복잡도O(1)
}
}</code></pre><h3>📚 참고자료</h3><ul class="tight" data-tight="true"><li><a target="_blank" rel="noopener noreferrer nofollow" href="https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/dashboard">https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/dashboard</a></li></ul>

합 배열 및 구간 합 알고리즘에 대해 알아보자

[Algorithm] 합배열(Prefix Sum)과 구간 합(Range Sum)

<h1>Lombok 이란</h1>Lombok은 자바 언어에서 반복적으로 작성해야하는 코드를 자동으로 생성해주는 라이브러리이다 예를 들면 dto작성할때.....Getter, Setter, Constructor, toString 등의 메소드를 자동으로 생성해서 개발자가 직접 작성하지 않아도 되도록 도와준다Lombok을 사용하기 위해서는 라이브러리를 프로젝트에 추가해야한다<h2>라이브러리 의존성 추가</h2><h3>Maven을 사용하는 경우</h3><code spellcheck="false">pom.xml</code> 파일에 다음과 같은 의존성을 추가해준다.<pre spellcheck="false"><code>&lt;dependencies&gt;
 &lt;dependency&gt;
 &lt;groupId&gt;org.projectlombok&lt;/groupId&gt;
 &lt;artifactId&gt;lombok&lt;/artifactId&gt;
 &lt;version&gt;1.18.26&lt;/version&gt;
 &lt;scope&gt;provided&lt;/scope&gt;
 &lt;/dependency&gt;
&lt;/dependencies&gt;</code></pre><h3>Gradle을 사용하는 경우</h3><code spellcheck="false">build.gradle</code> 파일에 다음과 같은 의존성을 추가해준다.<pre spellcheck="false"><code>dependencies {
compileOnly 'org.projectlombok:lombok:1.18.26'
annotationProcessor 'org.projectlombok:lombok:1.18.20'
}</code></pre>근데 Lombok을 사용할 때 주의해야 할 점이 있는데Lombok이 생성해주는 코드는 컴파일시 자동으로 생성되기 때문에 IDE에서는 확인이 안된다 따라서 Lombok을 사용할 때는 IDE에서 Lombok의 기능을 지원해주는 플러그인을 설치해주는게 좋음<h1>Lombok 어노테이션 종류</h1>Lombok에서 제공하는 어노테이션은 종류가 많은데 그중 주요 어노테이션은 아래와 같다<ul class="tight" data-tight="true"><li><code spellcheck="false">@Getter</code>: Getter 메소드 생성</li><li><code spellcheck="false">@Setter</code>: Setter 메소드 생성</li><li><code spellcheck="false">@ToString</code>: toString 메소드 생성</li><li><code spellcheck="false">@EqualsAndHashCode</code>: equals, hashCode 메소드 생성</li><li><code spellcheck="false">@Data</code>: Getter, Setter, equals, hashCode, toString 메소드 생성</li><li><code spellcheck="false">@AllArgsConstructor</code>: 모든 필드(멤버변수)를 인자로 받는 생성자 생성</li><li><code spellcheck="false">@NoArgsConstructor</code>: 인자가 없는 "쌩" 기본 생성자 생성</li><li><code spellcheck="false">@RequiredArgsConstructor</code>: final 필드를 인자로 받는 생성자 생성</li></ul><h1>Lombok 사용 예시</h1><h2><code spellcheck="false">@Data</code></h2>의존성을 추가한 후, Lombok을 사용하고자 하는 클래스 상단에 <code spellcheck="false">@Data</code> 어노테이션을 추가하면 자동으로 Getter, Setter, Constructor, toString 등이 생성된다<pre spellcheck="false"><code class="language-java">package com.project.test618.dto;
import lombok.Data;

@Data
public class MemberDTO {
String user_id;
String password;
String name;
String email;
int age;
}</code></pre><pre spellcheck="false"><code class="language-java">package com.project.test618;
import com.project.test618.dto.MemberDTO;

public class MemberTest {
public static void main(String[] args) {

MemberDTO dto = new MemberDTO();
 dto.setUser_id("park1234");
 dto.setPassword("test1234");
 dto.setName("박아무개");
 dto.setEmail("park1234@email.com");
 dto.setAge(23);
}}</code></pre><code spellcheck="false">MemberDTO</code> 에서 <code spellcheck="false">@Data</code> 어노테이션을 사용한뒤 dto객체를 불러와 접근했을때 getter,setter를 직접 적지 않아도 사용이 가능한것을 확인했다<h2><code spellcheck="false">@Builder</code></h2><code spellcheck="false">@Builder</code> 어노테이션을 사용하여 빌더 패턴을 쉽게 구현할 수 있다<pre spellcheck="false"><code class="language-java">// MemberDTO.java
package com.project.test618.dto;
import lombok.Builder;
import lombok.Data;

@Builder
@Data
public class MemberDTO {
String user_id;
String password;
String name;
String email;
int age;
}</code></pre><code spellcheck="false">@Builder</code> 어노테이션을 사용하여 dto에서 빌더 패턴을 구현하였고 이제 빌더를 사용하여 객체를 생성할 수 있음<pre spellcheck="false"><code>package com.project.test618;
import com.project.test618.dto.MemberDTO;

public class MemberTest {
public static void main(String[] args) {

MemberDTO dto = MemberDTO.builder()
.user_id("park1234")
.password("test1234")
.name("박아무개")
.build();
}
}</code></pre>빌더 패턴을 사용하면 필요한 속성만 설정하여 객체를 만들수있음!! 그리고 사용될 속성이 많은 경우에 가독성이 좋아진다는 장점이 있다<h2>@AllArgsConstructor, @NoArgsConstructor</h2>Lombok은 <code spellcheck="false">@AllArgsConstructor</code>, <code spellcheck="false">@NoArgsConstructor</code> 어노테이션을 제공하고 있다. <code spellcheck="false">@AllArgsConstructor</code> 어노테이션을 사용하면 모든 필드를 인자로 받는 생성자, 또는 인자가 없는 생성자를 자동으로 생성할 수 있다<pre spellcheck="false"><code class="language-java">package com.project.test618.dto;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

@Data
@NoArgsConstructor
@AllArgsConstructor

public class MemberDTO {
String user_id;
String password;
String name;
String email;
int age;
}</code></pre>위에서 <code spellcheck="false">@AllArgsConstructor</code> ,<code spellcheck="false">@NoArgsConstructor</code> 를 사용해서 만든 자바코드를 원래대로 풀어서 쓰면 아래처럼 되는것이다<pre spellcheck="false"><code class="language-java">package com.project.test618.dto;
public class MemberDTO {
String user_id;
String password;
String name;
String email;
int age;

public MemberDTO() {};
public MemberDTO(String user_id,String password, String name, String email, int age) {
this.user_id = user_id;
this.password = password;
this.name = name;
this.email = email;
this.age = age;
}}</code></pre>

Lombok을 사용해보자

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=cpp">같은 숫자는 싫어</a></li><li>사용언어 : C++</li><li>난이도 : 하 </li><li>풀이시간 : 15m</li><li>유형 : 큐, 스택</li></ul><h6>문제 설명</h6>배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,<ul><li>arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.</li><li>arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.</li></ul>배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.<h5>제한사항</h5><ul><li>배열 arr의 크기 : 1,000,000 이하의 자연수</li><li>배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수</li></ul><hr><h5>입출력 예</h5>arr answer [1,1,3,3,0,1,1] [1,3,0,1] [4,4,4,3,3] [4,3]<h5>입출력 예 설명</h5>입출력 예 #1,2 문제의 예시와 같습니다.<h3>문제 풀이 접근</h3>이 문제는, 문제 풀이 접근이랄게 크게 없다. 요구하는 건 한가지로, 내 앞의 숫자와 연속되지 않게만 해달라. 이게 끝이다. 처음에는 자주쓰는 vector로 풀었지만, 유형이 큐, 스택이어서 문제 의도에 맞게 한번더 풀어보았다.<h3>정답 작성 코드 (C++) - vector 풀이</h3><pre spellcheck="false"><code>#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt; 

using namespace std;

vector&lt;int&gt; solution(vector&lt;int&gt; arr) 
{
 vector&lt;int&gt; answer;

 answer.push_back(arr[0]);
 
 for(int i = 1; i &lt; arr.size(); ++i)
 {
 if(arr[i-1] == arr[i])
 continue;
 
 answer.push_back(arr[i]);
 }
 

 return answer;
}</code></pre><h3>정답 작성 코드 (C++) - stack 풀이 , 리버스 함수 이용</h3><pre spellcheck="false"><code>#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;stack&gt;
#include &lt;algorithm&gt;

using namespace std;

vector&lt;int&gt; solution(vector&lt;int&gt; arr) 
{
 vector&lt;int&gt; answer;
 stack&lt;int&gt; st;
 
 st.push(arr[0]);
 
 int counter = 1;
 
 while(counter &lt; arr.size())
 {
 int topValue = st.top();
 
 if(arr[counter] == topValue)
 {
 ++counter;
 continue;
 } 
 
 st.push(arr[counter]);
 ++counter;
 }
 
 while(true)
 {
 if(st.empty() == true)
 break;
 
 int value = st.top();
 st.pop();
 answer.push_back(value);
 }
 
 reverse(answer.begin(),answer.end());
 return answer;
}</code></pre><h3>정답 작성 코드 (C++) - stack 풀이 , 리버스 함수 만들어서 풀이 </h3><pre spellcheck="false"><code>#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;stack&gt;
#include &lt;algorithm&gt;

using namespace std;

vector&lt;int&gt; solution(vector&lt;int&gt; arr) 
{
 vector&lt;int&gt; answer;
 stack&lt;int&gt; st;
 
 st.push(arr[0]);
 
 int counter = 1;
 
 while(counter &lt; arr.size())
 {
 int topValue = st.top();
 
 if(arr[counter] == topValue)
 {
 ++counter;
 continue;
 }
 
 
 st.push(arr[counter]);
 
 ++counter;
 }
 
 vector&lt;int&gt; dummy;
 while(true)
 {
 if(st.empty() == true)
 break;
 
 int value = st.top();
 st.pop();
 
 dummy.push_back(value);
 }
 
 for(int i = dummy.size()-1; i &gt;= 0 ; --i)
 {
 answer.push_back(dummy[i]);
 }
 
 return answer;
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1721969744120" alt="until-956">

혼자서 다시푸는 코딩테스트 준비 일지 - 4

코딩테스트 준비 - 같은 숫자는 싫어

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/21736">21736.헌내기는 친구가 필요해</a></li><li>사용언어 : C#</li><li>난이도 : 중하</li><li>풀이시간 : 미측정</li><li>유형 : DFS, BFS, 그래프 이론</li></ul><h2>문제</h2>2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에&nbsp;가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.&nbsp;도연이가 다니는 대학의 캠퍼스는 N×M<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi><mo>×</mo><mi>M</mi></mrow><annotation encoding="application/x-tex">N \times M</annotation></semantics></math>N×M 크기이며&nbsp;캠퍼스에서 이동하는&nbsp;방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x, y<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math>y)에 있다면 이동할 수 있는 곳은 (x+1<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">x+1</annotation></semantics></math>x+1, y<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math>y), (x<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x, y+1<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>y</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">y+1</annotation></semantics></math>y+1), (x−1<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">x-1</annotation></semantics></math>x−1, y<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math>y), (x<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x, y−1<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>y</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">y-1</annotation></semantics></math>y−1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.<h2>입력</h2>첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math>N (1≤N≤600$ 1 \leq N \leq 600<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">)</mo><mo separator="true">,</mo><mi>M</mi></mrow><annotation encoding="application/x-tex">), M</annotation></semantics></math>),MM$ (1≤M≤600$ 1 \leq M&nbsp;\leq 600$)이 주어진다.둘째 줄부터 N<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math>N개의 줄에는 캠퍼스의 정보들이 주어진다. <code spellcheck="false">O</code>는 빈 공간, <code spellcheck="false">X</code>는 벽, <code spellcheck="false">I</code>는 도연이, <code spellcheck="false">P</code>는 사람이다. <code spellcheck="false">I</code>가 한 번만 주어짐이 보장된다.<h2>출력</h2>첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 <code spellcheck="false">TT</code>를 출력한다.<h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>3 5
OOOPO
OIOOX
OOOXP</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>1</code></pre><h2>예제 입력 2 복사</h2><pre spellcheck="false"><code>3 3
IOX
OXP
XPP</code></pre><h2>예제 출력 2 복사</h2><pre spellcheck="false"><code>TT</code></pre><h3>문제 풀이 접근</h3>이 문제의 요구사항은 문제가 제시해준 칸을 구성하고, 제시해준 좌표에서 원하는 문자를 찾아서 카운팅을 할 수 있는가를 요구하는 문제였다. 크게 설명할 것은 없으니 플로우도 간단하다. 1. 주어진 값으로 맵을 만든다. 2. 주어진 좌표로 시작좌표를 설정한다. 3. DFS,BFS등 편한 방식으로 탐색하고 P를 발견했을 때, 변수를 하나 올려준다.이 문제는 최단거리도 아니니, DFS로 풀어도 될것 같았지만, 난 BFS로 풀었다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;

/*
 * Difficulty : Easy ~ 
 * URL : https://www.acmicpc.net/problem/21736
 */


namespace CodingTestProj
{
 internal class Program
 {
 static void Main(string[] args)
 {
 //Case 0 _ Short
 Solution solution = new Solution();
 solution.solve();
 }
 }

 public class Solution
 {
 public int n;
 public int m;

 public char[,] maps;
 public bool[,] visited;

 public int[] dx = new int[4] { 0, 0, -1, 1 };
 public int[] dy = new int[4] { 1, -1, 0, 0 };

 public int startPosX;
 public int startPosY;

 int ret;
 public void solve()
 {
 ret = 0;

 string[] inputs = Console.ReadLine().Split(' ');

 n = Int32.Parse(inputs[1]);
 m = Int32.Parse(inputs[0]);
 // 좌우 바꾸기

 maps = new char[m, n];
 visited = new bool[m, n];

 for (int i =0; i &lt; m;++i)
 {
 string inputLine = Console.ReadLine();

 for(int j = 0; j &lt; inputLine.Length; ++j)
 {
 char chr = inputLine[j];

 maps[i, j] = chr;

 if(chr == 'I')
 {
 startPosX = i;
 startPosY = j;
 }

 if (chr == 'X')
 {
 visited[i, j] = true;
 }
 }
 }

 BFS();

 Console.Write(ret == 0 ? "TT" : ret.ToString());
 }

 public void BFS()
 {
 var q = new Queue&lt;Tuple&lt;int, int&gt;&gt;();

 q.Enqueue(new Tuple&lt;int, int&gt;(startPosX, startPosY));

 while(q.Count &gt; 0)
 {
 var dequeue = q.Dequeue();

 var posX = dequeue.Item1;
 var posY = dequeue.Item2;

 if (visited[posX, posY] == true)
 continue;

 visited[posX, posY] = true;

 if (maps[posX, posY] == 'P')
 ++ret;

 for(int i = 0; i &lt; 4; ++i)
 {
 int newPosX = posX + dx[i];
 int newPosY = posY + dy[i];

 if (isCheckSafeArea(newPosX, newPosY) == false)
 continue;

 if (visited[newPosX, newPosY] == true)
 continue;

 q.Enqueue(new Tuple&lt;int,int&gt;(newPosX ,newPosY));
 }
 }
 }

 public bool isCheckSafeArea(int posX, int posY)
 {
 if (posX &lt; 0 || posX &gt; (m - 1) || posY &lt; 0 || posY &gt; (n - 1))
 return false;

 return true;
 }
 }
}
</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1727360445289.png" alt="until-1567">

혼자서 다시푸는 코딩테스트 준비 일지 - 26

코딩테스트 준비 - 헌내기는 친구가 필요해

요즘 같이 신입들이 설 자리가 굉장히 없는 각박한 시기에, 얼마 전 운이 좋게 신입으로 게임 회사에 면접을 보게 되었습니다 🤣🤣🤣그런데 면접 중 다음과 같은 질문을 받을 수 있었는데, ‘포트폴리오를 확인해 보면 스프링 부트를 주로 사용해 왔는데, 스프링 부트는 보통 내장되어 있는 웹 서버로 Tomcat을 사용하는데도 불구하고 Nginx를 사용한 이유가 있을까요?’이러한 질문을 주셨는데 당시 많이 긴장되어 있는 상황이기도 하였고, 당장 생각나는 것은"저희가 프로젝트 환경상, EC2 한 대에서 프론트엔드와 백엔드를 함께 배포해야 하는 상황이었습니다. 따라서 하나의 도메인으로 모든 요청과 응답이 이루어지는데, 요청이 들어올 때 리버스 프록시 기능을 사용하기 위해 Nginx가 필요하기도 하였고, 보안적인 측면에서도 HTTPS를 사용해야 하기 때문에 Nginx를 사용했습니다."지금은 글로 작성하니까 나름 그럴싸하게 작성했지만, 실제로 대답할 때는 조금 어색하게 표현한 것 같아 후회가 듭니다.😅면접을 볼 때에는 당장 생각나는 것이 이것밖에 없었지만, 뒤늦게 면접관님의 의도를 떠올릴 수 있었습니다. 아마도 Nginx를 사용한 이유, 즉 웹 서버(WS)와 웹 애플리케이션 서버(WAS)의 차이점을 분명하게 이해하고 사용한 것인지를 물어보려고 하셨던 게 아닐까 하는 생각이 들었습니다.그래서 이제는 비슷한 질문을 받더라도 더 이상 실수하지 않게 다시 한 번 학습하고 리마인드를 해보려고 합니다.<hr>웹 서버(Web Server)는 웹 클라이언트(예: 웹 브라우저)로부터 HTTP 요청을 받아 정적 콘텐츠(HTML, CSS, JavaScript, 이미지 등)를 제공하는 소프트웨어입니다.<h2>웹 서버의 주요 역할</h2><h3>주요 기능</h3><ol><li>정적 콘텐츠 제공:<ul><li>HTML, CSS, JavaScript 파일 및 이미지 등과 같은 정적 파일을 클라이언트에 제공합니다. Q. 프론트엔드, 백엔드가 구분되어 사용되는 것이 보통입니다. HTML, CSS, JS 파일은 웹 서버에서 언제 어떤 상황에서 클라이언트에게 제공되는가 ? <ul><li>상황: 사용자가 웹 브라우저를 통해 특정 웹 페이지를 요청하는 경우<ul><li>사용자가 브라우저에서 <code spellcheck="false">http://example.com</code>을 입력하면, 브라우저는 해당 URL에 대한 HTTP 요청을 웹 서버로 보냅니다.</li><li>웹 서버(ex. Nginx)는 요청된 URL을 기반으로 적절한 파일을 찾아 클라이언트에 반환합니다. 여기서 정적 파일 제공이 이루어집니다.</li><li>예를 들어, Nginx와 같은 웹 서버가 <code spellcheck="false">/usr/share/nginx/html</code> 디렉토리에 웹페이지 파일을 저장하고 있다면, 다음과 같은 과정이 진행됩니다:<ul><li>사용자가 <code spellcheck="false">http://example.com/index.html</code>을 요청합니다.</li><li>웹 서버는 요청된 파일 경로를 확인하고, <code spellcheck="false">/var/www/html/index.html</code> 파일을 찾아 응답으로 반환합니다.</li></ul></li><li>HTML 파일 반환: 웹 서버는 <code spellcheck="false">index.html</code> 파일을 클라이언트(브라우저)에 반환합니다. 브라우저는 HTML 파일을 파싱하여 페이지의 기본 구조를 렌더링합니다.</li><li>CSS와 JavaScript 파일 요청: HTML 파일이 로드되면서, 페이지 내에 포함된 CSS 및 JavaScript 파일에 대한 추가 요청이 발생합니다. 예를 들어, HTML 파일에 다음과 같은 링크가 포함되어 있을 수 있습니다:<pre spellcheck="false"><code class="language-html">&lt;link rel="stylesheet" href="styles.css"&gt;
&lt;script src="app.js"&gt;&lt;/script&gt;</code></pre><ul><li>브라우저는 <code spellcheck="false">styles.css</code>와 <code spellcheck="false">app.js</code> 파일을 추가로 요청합니다.</li><li>웹 서버는 동일한 방식으로 이 파일들을 찾아 클라이언트에 반환합니다. </li></ul></li></ul></li><li>구체적인 예시사용자가 <code spellcheck="false">http://example.com</code>에 접속하면 다음과 같은 요청과 응답 흐름이 발생합니다:<ol><li>브라우저 요청: <code spellcheck="false">GET /index.html</code></li><li>웹 서버 응답: <code spellcheck="false">/var/www/html/index.html</code> 파일 반환</li><li>브라우저 요청: <code spellcheck="false">GET /styles.css</code></li><li>웹 서버 응답: <code spellcheck="false">/var/www/html/styles.css</code> 파일 반환</li><li>브라우저 요청: <code spellcheck="false">GET /app.js</code></li><li>웹 서버 응답: <code spellcheck="false">/var/www/html/app.js</code> 파일 반환 </li></ol></li></ul>이 과정을 통해 사용자는 웹 페이지를 볼 수 있게 되며, CSS로 스타일링된 페이지와 JavaScript로 동작하는 기능을 사용할 수 있게 됩니다. </li></ul></li><li>HTTP 요청 처리 및 응답:<ul><li>클라이언트의 HTTP 요청을 처리하고, 적절한 응답을 생성하여 반환합니다. </li></ul></li><li>URL 매핑 및 라우팅:<ul><li>요청 URL을 기반으로 적절한 파일이나 서비스로 요청을 라우팅합니다. 이는 리버스 프록시의 역할로, 클라이언트의 요청을 받아 적합한 백엔드 서버로 전달하고 결과를 다시 클라이언트에게 반환합니다. </li></ul></li><li>로드 밸런싱:<ul><li>여러 서버 간에 트래픽을 분산시켜 고가용성을 유지하고 성능을 향상시킵니다. </li></ul></li><li>보안 기능:<ul><li>SSL/TLS를 통한 데이터 암호화, IP 필터링, 사용자 인증 등 다양한 보안 기능을 제공합니다.</li></ul></li></ol><h3>웹 서버의 예시</h3><ul><li>Apache HTTP Server:<ul><li>오픈 소스 웹 서버로, 다양한 플랫폼에서 사용되며, 매우 널리 사용됩니다.</li></ul></li><li>Nginx:<ul><li>고성능 웹 서버로, 특히 높은 동시 연결 수를 처리할 수 있어 정적 파일 제공 및 리버스 프록시로 자주 사용됩니다.</li></ul></li></ul><hr>웹 애플리케이션 서버(Web Application Server, WAS)는 웹 서버와는 달리, 동적 콘텐츠를 생성하고 웹 애플리케이션의 비즈니스 로직을 처리하는 소프트웨어입니다. WAS는 클라이언트의 요청을 받아들여 데이터베이스와 상호 작용하고, 그 결과를 동적 웹 페이지 형태로 클라이언트에 반환합니다.<h2>웹 애플리케이션 서버의 주요 역할</h2><ol><li>비즈니스 로직 처리:<ul><li>클라이언트 요청을 처리하는 비즈니스 로직을 실행합니다. 예를 들어, 사용자의 로그인, 상품 검색, 주문 처리 등의 작업을 수행합니다. → 서블릿 기반 </li></ul></li><li>동적 콘텐츠 생성:<ul><li>JSP, 서블릿, EJB 등과 같은 기술을 사용하여 동적인 웹 페이지를 생성합니다. 클라이언트의 요청에 따라 실시간으로 콘텐츠를 생성하여 응답합니다. </li></ul></li><li>데이터베이스 연동:<ul><li>데이터베이스와 상호 작용하여 데이터를 조회, 삽입, 업데이트, 삭제하는 작업을 수행합니다. 이를 통해 클라이언트가 요청한 데이터를 처리하고 반환합니다. </li></ul></li><li>세션 관리:<ul><li>사용자 세션을 관리하여 사용자 상태를 유지하고, 인증 및 권한 부여를 처리합니다. 이를 통해 사용자의 로그인 상태를 유지하거나, 사용자별로 다른 콘텐츠를 제공할 수 있습니다. </li></ul></li><li>트랜잭션 관리:<ul><li>데이터베이스 트랜잭션을 관리하여 데이터의 일관성과 무결성을 보장합니다. 여러 작업이 하나의 트랜잭션으로 묶여 일관성 있게 처리되도록 합니다. </li></ul></li></ol><h3>웹 애플리케이션 서버의 예시</h3><ul><li>Apache Tomcat:<ul><li>오픈 소스 서블릿 컨테이너로, 서블릿과 JSP 기반의 웹 애플리케이션을 실행합니다.</li></ul></li></ul><hr><h2>정리</h2><img src="https://image.until.blog/thingk0/article/1716860951310" alt="until-318"><h3>이유 1: 정적 콘텐츠 제공</h3><ul><li>Nginx는 정적 콘텐츠(예: 이미지, CSS, JavaScript 파일 등)를 매우 효율적으로 제공할 수 있습니다. 이를 통해 스프링 부트 애플리케이션이 정적 리소스를 제공하는 부담을 줄이고, 동적 콘텐츠 제공에 집중할 수 있게 합니다.<blockquote>하지만, 보통 프론트엔드와 API 서버 조합으로 많이 사용하기 때문에, 사실상 정적 콘텐츠 제공에는 큰 메리트를 느끼기 어려웠습니다. 그러나 프론트엔드가 SPA일 경우에는 매우 유용하다고 생각합니다.</blockquote></li></ul><h3>이유 2: 리버스 프록시</h3><ul><li>리버스 프록시로서 Nginx는 클라이언트 요청을 스프링 부트 애플리케이션으로 전달합니다. 이를 통해 애플리케이션 서버를 보호하고, 로드 밸런싱 및 SSL 종료(SSL termination) 등의 기능을 제공합니다.<blockquote>실제로 제가 Nginx를 사용하는 가장 주된 이유는, 보통 프로젝트를 진행할 때 서버 인스턴스를 하나만 사용할 수 있는 상황이 많아서, 어쩔 수 없이 서버 안에서 프론트엔드, 인프라, 백엔드를 모두 배포해야 했기 때문입니다.이러한 이유로 Nginx의 리버스 프록시 기능은 매우 유용하고 필요했습니다. 그래서 다행히도 면접에서 가장 먼저 떠올린 리버스 프록시를 답변할 수 있었습니다 !!</blockquote></li></ul><h3>이유 3: 로드 밸런싱</h3><ul><li>로드 밸런싱을 통해 여러 대의 스프링부트 인스턴스에 트래픽을 분산시킬 수 있습니다. 이를 통해 고가용성과 성능을 향상시킬 수 있습니다.<blockquote>면접 중 로드 밸런싱 관련 질문을 받았고, 당연히 Nginx를 통해 로드 밸런싱이 가능하다는 것은 알고 있었습니다.하지만 더 좋은 답변을 위해서는 추후에 블루-그린 배포를 적용하거나 스케일 아웃을 염두에 두었을 때, 로드 밸런싱 기능이 필요하기 때문에 Nginx가 필요하다는 답변을 떠올리지 못했다는 것이 뒤늦은 후회로 남네요..🥲</blockquote></li></ul><h3>이유 4: SSL/TLS 처리</h3><ul><li>SSL/TLS 처리를 Nginx가 담당함으로써 스프링부트 애플리케이션은 암호화된 트래픽을 직접 처리하지 않아도 되므로, 성능과 보안 측면에서 유리합니다.</li></ul><h3>이유 5: 보안</h3><ul><li>보안 설정 및 접근 제어를 Nginx 레벨에서 관리함으로써 애플리케이션의 보안성을 향상시킬 수 있습니다. IP 제한, DDoS 방어, WAF(Web Application Firewall) 등을 설정할 수 있습니다.</li></ul><h3>이유 6: 고성능</h3><ul><li>고성능의 Nginx는 적은 리소스로 많은 요청을 처리할 수 있어, 특히 많은 동시 접속이 발생하는 상황에서 유리합니다.<blockquote>“ Nginx는 비동기 이벤트 기반으로 설계되어, 적은 리소스로도 많은 수의 동시 연결을 효율적으로 처리할 수 있고 다중 워커 프로세스를 통해 병렬로 작업을 수행하여 성능을 극대화하며 메모리를 효율적으로 사용하여 더 많은 요청을 처리할 수 있습니다. "라고도 대답할 수 있다면 아마 만점짜리 답변이겠죠..?</blockquote></li></ul><hr>즉, 저는 리버스 프록시와 보안 부분에서는 어느 정도 정답에 가까운 대답을 했다고 생각해요 ! 하지만 기억을 되돌려보면, 로드 밸런싱 부분에 대해서도 잠깐 질문을 받았는데, 급히 다른 질문으로 넘어갔던 것이 아쉽고... Nginx를 통해 로드 밸런싱, 성능, 그리고 정적 콘텐츠 제공에 대해서도 답변을 할 수 있었다면 더 좋았을 것 같아요.다음에 비슷한 질문을 받는다면, 기존 답변에 보완해서 더욱 멋진 답변을 해보도록 하겠습니다. 😃

최근 게임 회사 면접에서 스프링 부트와 Nginx 사용 이유에 대한 질문을 받았습니다. 이번 포스팅에서는 웹 서버와 웹 애플리케이션 서버의 차이를 명확히 이해하고, Nginx 사용 이유를 깊이 있게 다뤄봅니다.

WAS가 있음에도 불구하고, 웹서버인 Nginx 를 사용하는 이유 - 개발자 면접 리마인드

<h3>코딩 테스트 준비 일지 19 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" class="no-underline hover:text-blue-s dark:hover:text-dark-blue-s truncate cursor-text whitespace-normal hover:!text-[inherit]" href="https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/">Minimum Add to Make Parentheses Valid</a></li><li>난이도 : 하</li><li>풀이시간 : 1h 11m</li></ul>A parentheses string is valid if and only if:<ul class="tight" data-tight="true"><li>It is the empty string,</li><li>It can be written as&nbsp;<code spellcheck="false">AB</code>&nbsp;(<code spellcheck="false">A</code>&nbsp;concatenated with&nbsp;<code spellcheck="false">B</code>), where&nbsp;<code spellcheck="false">A</code>&nbsp;and&nbsp;<code spellcheck="false">B</code>&nbsp;are valid strings, or</li><li>It can be written as&nbsp;<code spellcheck="false">(A)</code>, where&nbsp;<code spellcheck="false">A</code>&nbsp;is a valid string.</li></ul>You are given a parentheses string&nbsp;<code spellcheck="false">s</code>. In one move, you can insert a parenthesis at any position of the string.<ul class="tight" data-tight="true"><li>For example, if&nbsp;<code spellcheck="false">s = "()))"</code>, you can insert an opening parenthesis to be&nbsp;<code spellcheck="false">"(()))"</code>&nbsp;or a closing parenthesis to be&nbsp;<code spellcheck="false">"())))"</code>.</li></ul>Return&nbsp;the minimum number of moves required to make&nbsp;<code spellcheck="false">s</code>&nbsp;valid.Example 1:<pre spellcheck="false"><code>Input: s = "())"
Output: 1
</code></pre>Example 2:<pre spellcheck="false"><code>Input: s = "((("
Output: 3
</code></pre>Constraints:<ul class="tight" data-tight="true"><li><code spellcheck="false">1 &lt;= s.length &lt;= 1000</code></li><li><code spellcheck="false">s[i]</code>&nbsp;is either&nbsp;<code spellcheck="false">'('</code>&nbsp;or&nbsp;<code spellcheck="false">')'</code>.</li></ul><h3>문제 풀이 접근</h3>금일 문제 풀이 키워드는 String, Stack 이었는데, 괄호를 어떻게 최단움직임으로 완벽하게 쌍을 맞춰주냐 그게 핵심 문제였다.크게 생각할 것은 없고, 문제를 2가지 방법을 생각했는데, 1. String 의 s[i] , s[i-1] 의 '(' ,')' 일 경우를 체크해서 answer를 하나 올리고 추후 연산에 넣는다. 2. Stack을 이용하여 '(' 일 경우 Push 하고, 가지고 있는 '(' 를 그다음 s[i] 가 ')' 괄호가 온다면 하나씩 Pop 해주는 것이다. 1번의 경우 여러 TC에서 막힐 소지가 있었다. 루프 카운터가 넘어가거나 하는 경우는 체크할 수 없기 때문이다. 2번의 경우가 Stack의 LIFO 성격을 이용해 하나씩 빼고 Answer + stack.Count() 를 더하면 원하는 값이나온다. ( 이 방법을 사용한다면, 사실 꼭 Stack을 이용하지 않아도 된다. )<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class Solution
 {
 public int MinAddToMakeValid(string s)
 {
 int answer = 0;

 if (s == string.Empty)
 return answer;

 Stack&lt;char&gt; stack = new Stack&lt;char&gt;();

 for(int i = 0; i &lt; s.Length; ++i)
 {
 if (s[i] == '(')
 stack.Push(s[i]);

 if(stack.Count() &lt;= 0 &amp;&amp; s[i] == ')')
 {
 ++answer;
 }

 if(stack.Count() &gt; 0 &amp;&amp; s[i] == ')')
 {
 stack.Pop();
 }
 }

 return stack.Count()+ answer;
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1719302424840" alt="until-677">

코딩테스트 항해99 클럽 - 19일차

[코딩테스트 일지 - 99클럽] 19일차 - Minimum Add to Make Parentheses Valid

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42577">전화번호 목록</a></li><li>사용언어 : C++</li><li>난이도 : 중 or 중상</li><li>풀이시간 : 55m</li><li>유형 : 해시 , 정렬</li></ul><h6>문제 설명</h6>전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.<ul><li>구조대 : 119</li><li>박준영 : 97 674 223</li><li>지영석 : 11 9552 4421</li></ul>전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.<h5>제한 사항</h5><ul><li>phone_book의 길이는 1 이상 1,000,000 이하입니다.<ul><li>각 전화번호의 길이는 1 이상 20 이하입니다.</li><li>같은 전화번호가 중복해서 들어있지 않습니다.</li></ul></li></ul><h5>입출력 예제</h5>phone_book return["119", "97674223", "1195524421"] false["123","456","789"] true["12","123","1235","567","88"] false<h5>입출력 예 설명</h5>입출력 예 #1 앞에서 설명한 예와 같습니다.입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.<h3>문제 풀이 접근</h3>이 문제는, 해시로 푸는것이 의도일 수도 있지만, 문자열 정렬의 기본 원리만 알면 쉽게 풀 수 있다. 단순히 문제를 풀기위해, StartsWith, Substr 잘라서 equal 등으로 하면 답을 구할 수는 있으나, 효율성 3,4 TC 에서 Time Limit으로 문제를 해결할 수 없다.그래서 할 수 있는 대표적인 방법이 Sort()로 푸는 방법인데, 문자열에서의 정렬과 수의 정렬 원리는 다르다.수의 정렬 케이스에서는 아래와 같이 정렬한다. - 정렬 전 : { 1, 19 , 119 , 91 , 112 } - 정렬 후 : { 1, 19 , 91 , 112 , 119 }문자열의 정렬 케이스에서는 아래와 같이 정렬한다. - 정렬 전 : { 1, 19 , 119 , 91 , 112 } - 정렬 후 : { 1, 112 , 119 , 19 , 91 }수의 정렬은 값을 기준으로 정렬하는 것 같으로 보이고, 문자열의 정렬 기준은 문자열 인덱스의 사전 순을 기준으로 정렬한다. 그리하여, Index 와 Index+1 만 비교하면, 정렬 상 내가 접두사인지 보장된다.<h3>정답 작성 코드 (C++) - 문제가 C# 지원 안한다.</h3><pre spellcheck="false"><code class="language-cpp">#include &lt;string&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

using namespace std;

bool isCompare(string fst, string snd)
{
 bool answer = false;
 
 for (int i = 0; i &lt; fst.size(); ++i)
 {
 if (fst[i] != snd[i])
 {
 answer = true;
 return answer;
 }
 }
 
 return answer;
}

bool solution(vector&lt;string&gt; phone_book) {
 
 bool answer = false;
 sort(phone_book.begin(), phone_book.end());
 
 for(int i = 0; i &lt; phone_book.size()-1; ++i)
 {
 if(isCompare(phone_book[i],phone_book[i+1]) == false)
 return false;
 }

 return true;
}</code></pre><h3> 코드 결과</h3><img src="https://image.until.blog/sin0105/article/1721661187849" alt="until-914">

혼자서 다시푸는 코딩테스트 준비 일지 - 2

코딩테스트 준비 - 전화번호 목록

<h1>개요</h1>Notion Database를 CMS로 활용하여 손쉽게 블로그를 만들고자 하였고, 블로그를 만들며 겪언던 이슈들을 정리하고자 한다.<h1>사용한 라이브러리</h1><ul><li><a target="_blank" rel="noopener noreferrer nofollow" href="https://github.com/makenotion/notion-sdk-js">notion-sdk-js (official)</a></li><li><a target="_blank" rel="noopener noreferrer nofollow" href="https://github.com/NotionX/react-notion-x">react-notion-x (unofficial)</a></li></ul>notion-sdk-js는 data-fetching을 담당하는 라이브러리고, react-notion-x는 불러온 데이터를 노션과 유사한 화면으로 손쉽게 리액트에 그려주는 라이브러리이다.react-notion-x에서 제공하는 <code spellcheck="false">&lt;NotionRenderer /&gt;</code> 컴포넌트에 노션 페이지의 데이터가 담긴 <code spellcheck="false">recordMap</code> 이라는 객체를 <code spellcheck="false">props</code>로 내려주면 되는데, 이 <code spellcheck="false">recordMap</code>을 가져오기 위해서는 공식 API가 아닌 notion-sdk-js에서 제공하는 방법이 아닌, react-notion-x 라이브러리 안에 담겨 있는 notion-client라는 unoffical API를 사용해야 한다.따라서, 일반적인 경우에는 notion-sdk-js를 사용하지 않아도 노션 페이지 데이터를 가져와 화면에 뿌려줄 수 있다. 그럼에도 나는 두 라이브러리를 혼용해서 사용했는데, 이유는 아래에서 설명하겠다.<h1>시작하기</h1>우선 나는 화면 렌더링에 필요한 <code spellcheck="false">recordMap</code> 을 제외하면, 모든 필요한 데이터는 official API (notion-sdk-js)를 통해 가져왔다. 예를 들어, 데이터베이스 내의 모든 태그 항목이라던가, Page의 unique Id, 최근 Page 등을 가져오는데 사용했다.사실 그냥 데이터만 가져와서 화면에 보여줄 거라면 react-notion-xd의 readme만 잘 읽어도 구현할 수 있다. 내가 글을 쓰는 이유는 헤맸던 점들을 공유하기 위해서다.<blockquote>💡 Good to Know:<ul><li>notion-sdk-js는 서버사이드(node.js)에서만 동작한다.</li><li>database는 page의 묶음, page는 blocks의 묶음, block들이 페이지 내부에서 실제 보여지는 데이터들이다.</li></ul></blockquote><h2>1. 타입 설정</h2>Notion API를 사용하면 데이터베이스를 하나 정하고, 그 데이터베이스내에 항목들을 설정하여 데이터들을 가져올 텐데, 타입스크립트를 사용해서 내가 지정한 데이터베이스에 어떠한 이름의 항목들이 있고, 그 항목들은 무슨 속성을 가지는지 설정이 필요했다.<pre spellcheck="false"><code class="language-typescript">// database에 정해진 속성 이름들
type DatabaseProperties =
 &nbsp;| "title"
 &nbsp;| "post"
 &nbsp;| "create_date"
 &nbsp;| "author"
 &nbsp;| "tag";
​
// notion sdk에서 type 추출.....
export type PostResult = Extract&lt;QueryDatabaseResponse["results"][number],{ properties: Record&lt;string, unknown&gt; }&gt;;
​
type PropertyValueMap = DatabaseObjectResponse["properties"] &amp; PageObjectResponse["properties"];
type PropertyValue = PropertyValueMap[string];
type PropertyValueType = PropertyValue["type"];
​
type ExtractedPropertyValue&lt;T extends PropertyValueType&gt; = Extract&lt;
 &nbsp;PropertyValue,
 { type: T }
&gt;;
// ...
​
export type RichText = ExtractedPropertyValue&lt;"rich_text"&gt;;
export type Date = ExtractedPropertyValue&lt;"date"&gt;;
export type Title = ExtractedPropertyValue&lt;"title"&gt;;
export type MultiSelect = ExtractedPropertyValue&lt;"multi_select"&gt;;
export type Files = ExtractedPropertyValue&lt;"files"&gt;;
export type Id = ExtractedPropertyValue&lt;"unique_id"&gt;;
​
// notion api custom response
export type BlogDatabaseObjectResponse = PostResult &amp; {
 &nbsp;properties: {
 &nbsp; &nbsp;post: IDatabaseProperty.Title;
 &nbsp; &nbsp;create_date: IDatabaseProperty.Date;
 &nbsp; &nbsp;author: IDatabaseProperty.RichText;
 &nbsp; &nbsp;tag: IDatabaseProperty.MultiSelect;
 &nbsp; &nbsp;// ...
 };
};</code></pre>위와 같이 타입 파일을 따로 만들어 관리했다.<h2>2. Private Page 이미지 문제</h2><img src="https://image.until.blog/love/article/1722432451503" alt="until-1167">notion의 데이터베이스가 private page에 설정되어 있는 경우에, 이미지를 가져올 수 없는 문제가 있었다. 이유는 다음과 같다. private page의 이미지 url은 signed되어, 다른 도메인에서 접근시 인가 에러를 발생시킨다.<blockquote>참조: <a target="_blank" rel="noopener noreferrer nofollow" href="https://github.com/NotionX/react-notion-x/issues/529">https://github.com/NotionX/react-notion-x/issues/529</a></blockquote>하지만! notion official API를 사용하면 외부에서 접근할 수 있는 URL을 반환해준다.따라서 다음과 같이 함수를 작성하여 <code spellcheck="false">recordMap</code>에 접근이 가능한 새로운 url image를 넣어 줬다.<pre spellcheck="false"><code>/**
 * Block List로부터 file(image) sigend url을 가져온다.
 * 하위 블록에 이미지가 있을 경우를 고려해 재귀를 통해 전부 탐색한다.
 */
async function getSigendUrlFromBlocks(
 &nbsp;blockList: (PartialBlockObjectResponse | BlockObjectResponse)[],
 &nbsp;signedMap: Record&lt;string, string&gt;,
) {
 &nbsp;const promises = blockList.map(async block =&gt; {
 &nbsp; &nbsp;if ("image" in block &amp;&amp; block.image.type === "file") {
 &nbsp; &nbsp; &nbsp;signedMap[block.id] = block.image.file.url;
 &nbsp; } else if ("has_children" in block &amp;&amp; block.has_children) {
 &nbsp; &nbsp; &nbsp;// 자식의 blockList를 다시 가져와야함...
 &nbsp; &nbsp; &nbsp;const children = await this.getBlockList(block.id);
 &nbsp; &nbsp; &nbsp;// 재귀!
 &nbsp; &nbsp; &nbsp;await this.getSigendUrlFromBlocks(children.results, signedMap);
 &nbsp; }
 });
 &nbsp;await Promise.all(promises);
 &nbsp;return signedMap;
}</code></pre><code spellcheck="false">NotionRenderer</code> 에서도 추가 설정을 해줘야 한다.<pre spellcheck="false"><code class="language-typescript"> &nbsp;&lt;NotionRenderer
 &nbsp; &nbsp;recordMap={recordMap}
 &nbsp; &nbsp;// ...
 &nbsp; &nbsp;// image url을 notion api를 통해 가져온 url로 교체 해준다.
 &nbsp; &nbsp;mapImageUrl={(url, block) =&gt; {
 &nbsp; &nbsp; &nbsp;if (recordMap.signed_urls[block.id]) {
 &nbsp; &nbsp; &nbsp; &nbsp;return recordMap.signed_urls[block.id];
 &nbsp; &nbsp; }
 &nbsp; &nbsp; &nbsp;return url;
 &nbsp; }}
 &nbsp;/&gt;</code></pre>이제 private page의 이미지도 잘 가져와진다!<h2>3. 이미지 로딩 속도 문제</h2>notion에 직접 업로드한 이미지를 불러오는 것은 굉장히 시간이 오래걸린다. 이유는 CDN을 제공하지 않기 때문이라고 한다.아래는 똑같은 이미지 파일을 노션에 직접 업로드한 이미지를 가져올 때와, CDN을 제공하는 스토리지에서 가져왔을 때의 속도차이다.<img src="https://image.until.blog/love/article/1722432465464" alt="until-1168">거의 20배 차이가 난다...따라서 CDN을 제공하는 서버에 이미지를 업로드한 뒤, 그 링크를 임베딩하여 가져오는 것이 더 나은 성능을 제공하겠다.<h2>4. 이미지 502 에러</h2>배포(SSG) 후 일정 시간이 지나면 502 에러가 발생한다. 이는 노션에서 주기적으로 이미지 URL을 변경해서 그런 문제 같다.<img src="https://image.until.blog/love/article/1722432432857" alt="until-1166">이 문제는 이미지를 노션에 업로드 하는 것이 아닌 다른 곳에 업로드한 후 가져오면 해결 된다..

Notion API를 사용한 블로그 개발 이슈 정리

<h2>🤔 문제<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#-%EB%AC%B8%EC%A0%9C">​</a></h2><h3>Alpine Linux와 cryptography의 호환성 문제<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#alpine-linux%EC%99%80-cryptography%EC%9D%98-%ED%98%B8%ED%99%98%EC%84%B1-%EB%AC%B8%EC%A0%9C">​</a></h3>Django 블로그 프로젝트를 docker로 옮기는 도중 에러가 떴다. alpine linux와 python에서 암호화 알고리즘이 구현된 패키지인 cryptography의 호환성 문제였다.<pre spellcheck="false"><code class="language-shell">FROM python:3.8-alpine</code></pre><pre spellcheck="false"><code class="language-shell">cryptography==3.4.7</code></pre>현재 Dockerfile에서 사용하는 image 버전과 requirements.txt에 적힌 cryptography 버전은 위와 같다.<pre spellcheck="false"><code class="language-bash">docker-compose build</code></pre><pre spellcheck="false"><code class="language-shell">ERROR: No matching distribution found for cryptography==3.4.7</code></pre><code spellcheck="false">Dockerfile</code>, <code spellcheck="false">docker-compose.yml</code>을 다 만들고 난 후에 마지막으로 위의 명령어로 빌드를 하던 중 위의 Error를 만났다.<h3>빌드가 오래 걸리는 문제<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#%EB%B9%8C%EB%93%9C%EA%B0%80-%EC%98%A4%EB%9E%98-%EA%B1%B8%EB%A6%AC%EB%8A%94-%EB%AC%B8%EC%A0%9C">​</a></h3><img src="https://image.until.blog/teddygood/article/1716799059748" alt="until-292">위의 명령어를 Dockerfile에 추가하고 다시 build 하니 위와 같이 에러 아닌 에러가 떴다. 이미지를 보면 알 수 있듯이 still running이 지속되는 상황이다. 대략 10분 정도 그대로 놔뒀는데도 빌드가 안 되는 상황이다.<img src="https://image.until.blog/teddygood/article/1716799052962" alt="until-291">cryptography GitHub 저장소에서 가져온 이슈 이미지다. 현재의 상황과 같길래 답변을 참고하려 했으나 내 지식으로는 이해 불가였다. 대략 요약하자면 파이썬 패키지 포맷과 관련된 답변과 alpine linux에 대해 공식 문서로 잘 정리되어 있다는 내용이다. 결론적으로는 도움이 안 됐지만, 혹시 저 답변으로 해결할 수 있는 분이 있을 수 있기에 가져와봤다.현 시점의 문제는 빌드가 오래 걸린다는 것이다. 이 문제를 해결하기 위해 다시 구글링을 하면서 도커에 대해 공부하게 됐고, 파이썬 환경에서 도커를 이용할 때 어떤 OS를 사용하는 것이 더 유리한 가에 대해 공부했다.<h2>🚩 해결<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#-%ED%95%B4%EA%B2%B0">​</a></h2><h3>첫 번째 문제 해결<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#%EC%B2%AB-%EB%B2%88%EC%A7%B8-%EB%AC%B8%EC%A0%9C-%ED%95%B4%EA%B2%B0">​</a></h3><img src="https://image.until.blog/teddygood/article/1716799044352" alt="until-290">아무리 구글링을 해도 찾지를 못 해서 공식 문서를 보기로 결정했고 어느정도 해결책을 찾았다.대략 요약하면 cryptography 패키지는 Rust를 사용하기에 Rust compiler도 같이 다운로드 해야지 돌아간다는 것이다. Rust는 cryptography를 빌드할 때 필요하며 stackoverflow에서 참고한 답변에서는 rust 설치를 스킵하는 명령어를 추가하는 방법도 알 수 있었다.<pre spellcheck="false"><code class="language-shell">ENV CRYPTOGRAPHY_DONT_BUILD_RUST=1</code></pre>multi-stage를 사용하여 빌드하라고 한다. 물론 multi-stage를 사용하면 이미지를 경량화하는 것도 좋은 방법이지만 도커를 자세히 배운 사람이 아니라 잘 모르기 때문에 이 방법은 패스했다.<pre spellcheck="false"><code class="language-bash">$ sudo apk add gcc musl-dev python3-dev libffi-dev openssl-dev cargo</code></pre>위의 명령어를 Dockerfile에 추가하면서 첫 번째 문제는 끝났다.<h3>두 번째 문제 해결<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#%EB%91%90-%EB%B2%88%EC%A7%B8-%EB%AC%B8%EC%A0%9C-%ED%95%B4%EA%B2%B0">​</a></h3><h4>alpine linux가 파이썬 환경에서 적절하지 않은 이유<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#alpine-linux%EA%B0%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%99%98%EA%B2%BD%EC%97%90%EC%84%9C-%EC%A0%81%EC%A0%88%ED%95%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EC%9D%B4%EC%9C%A0">​</a></h4>대부분의 사람들이 도커를 처음 사용할 때 alpine linux로 사용하는데 그 이유는 Ubuntu linux와 비교했을 때 용량도 작고 빌드할 때 더 빠르기 때문이다. 그러나 python 환경에서는 적절하지 않다.그 이유는 사용하는 라이브러리의 차이에서 시작된다. 대부분의 리눅스 배포판은 파이썬을 포함한 모든 C언어 프로그램에 필요한 C언어 표준 라이브러리인 GNU 라이브러리(glibc)를 사용한다. 그러나 Alpine Linux는 좀 더 경량화하기 위하여 GNU 라이브러리를 사용하는 것이 아니라 musl 라이브러리를 사용한다. 이 musl 라이브러리는 GNU 라이브러리로 컴파일 된 <code spellcheck="false">Wheel 바이너리</code>를 지원하지 않는다. 그렇기 때문에 <code spellcheck="false">.whl</code> 확장자를 갖는 패키지를 다운 받는 것이 아니라 <code spellcheck="false">.tar.gz</code> 확장자 파일을 다운 받게 된다. 그렇기 때문에 alpine linux를 사용하는 경우 사용하는 모든 파이썬 패키지의 C코드를 컴파일 해야 하므로 빌드 시간도 오래 걸리며 용량도 커진다는 것이다.최근 대부분의 파이썬 패키지에는 PyPI의 Wheel 바이너리가 포함되어 있어 설치 시간이 빠르다. Wheel은 사실 .whl 확장자와 특별한 형식의 파일 이름으로 이루어진 ZIP 형식을 아카이브한 것이다. 쉽게 말하면 확장자만 바꾼 것이다.<ol class="tight" data-tight="true"><li>빌드가 느리다.</li><li>이미지 용량이 커진다.</li><li>시간이 많이 낭비된다.(빌드하는 과정)</li><li>런타임 버그들을 만날 수 있다.</li></ol>간단하게 요약하자면 위의 이유들이 Alpine Linux가 python 환경에서 적절하지 않은 이유이다.<h4>그럼 어떤 OS를 사용해야 할까?<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#%EA%B7%B8%EB%9F%BC-%EC%96%B4%EB%96%A4-os%EB%A5%BC-%EC%82%AC%EC%9A%A9%ED%95%B4%EC%95%BC-%ED%95%A0%EA%B9%8C">​</a></h4>성능에 관심 있으면 ubuntu, 가볍게 도커를 시작해보려면 alpine이 좋겠지만 현재 나는 파이썬 환경에서 도커를 사용해보려 하니 Debian buster를 기반으로 한 3.8-slim-buster를 사용한다.<pre spellcheck="false"><code class="language-shell">RUN apk update \
&amp;&amp; apk add postgresql-dev gcc python3-dev musl-dev zlib-dev jpeg-dev libffi-dev openssl-dev cargo</code></pre><pre spellcheck="false"><code class="language-shell">FROM python:3.8-slim-buster</code></pre>위의 apk로 패키지 설치한 부분의 명령어를 지우고, slim-buster로 바꿔준다.이후 다시 build 했을 때 잘 되는 모습을 확인할 수 있다.<h2>🌐References<a target="_blank" rel="noopener noreferrer nofollow" class="hash-link" href="https://teddygood.github.io/wiki/python-lib-cryptography#references">​</a></h2><ul class="tight" data-tight="true"><li><a target="_blank" rel="noopener noreferrer" href="https://cryptography.io/en/latest/installation/">Cryptography installation</a></li><li><a target="_blank" rel="noopener noreferrer" href="https://github.com/pyca/cryptography/issues/5776">Dependencies to build on Alpine Linux?</a></li><li><a target="_blank" rel="noopener noreferrer" href="https://jonnung.dev/docker/2020/04/08/optimizing-docker-images/">도커 이미지 잘 만드는 방법</a></li><li><a target="_blank" rel="noopener noreferrer" href="https://pythonspeed.com/articles/alpine-docker-python/">Using Alpine can make Python Docker builds 50x slower</a></li><li><a target="_blank" rel="noopener noreferrer" href="https://pythonspeed.com/articles/base-image-python-docker-images/">The best Dockeer base image for Python application</a></li></ul>

Alpine Linux와 crptography의 호환성 문제 해결

<h3>코딩 테스트 준비 일지 4 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">프로그래머스</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42839#">소수 찾기</a></li><li>난이도 : 중</li></ul>한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>numbers는 길이 1 이상 7 이하인 문자열입니다.</li><li>numbers는 0~9까지 숫자만으로 이루어져 있습니다.</li><li>"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.</li></ul><h5>입출력 예</h5>numbers return "17" 3 "011" 2<h5>입출력 예 설명</h5>예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.<ul class="tight" data-tight="true"><li>11과 011은 같은 숫자로 취급합니다.</li></ul><h3>문제 풀이 접근</h3>어제와 별다를 것 없이 시원하게 1차로 생각했던 방식은 1시간동안 풀어도 답이안나와서 시원하게 날려먹었다. 결국 어제보다 더 돌아가서 1시간 날려먹기 + 1시간 30분만에 새로운 방식 찾고 문제 풀이하여 2시간 30분만에 정답을 찾았다. 여기서 날려먹은 방식은 내가 임의로 모든 카드를 다 사용하여 만드는 숫자겠지? 라는 생각에 빠져서 시간을 허비했다. 결국 총 3장을 주던, 5장을 주던, 마음대로 카드를 사용하여 숫자를 만들고, 이 숫자들의 집합에서 소수 판별을 하여 갯수를 리턴해라가 핵심이다.결국 처음 생각한 문제 해결 플로우는 정답이었으나, 내부 로직에 대한 판단이 실패를 해버린 결과가 2시간 30분이다.이 문제의 핵심은 아래와 같다. 1. 주어진 수를 분리하라. 2. 분리하여 만들 수 있는 모든 가지의 수 조합을 생성하라 3. 이 수 조합을 숫자로 변환하여 소수 판별을 진행하고, 혹시 모르니 판별 상 통과한 수에 대해 담고 있을 List&lt;int&gt; Collector 를 만들어서 이미 한번 패스한 숫자에 대한 필터링을 진행해라. 여기서 2번은 조합을 써도되고 순열을 써도되고, BFS, DFS 하고싶은 방식으로 만든다 나는 DFS 방식으로 순회하고 String 값에 Depth 마다 하나씩 더해주면서 소수 판단을 하여 답을 이끌어 냈다.<h3>방향 잘못 잡은 코드 작성 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

public class Solution {
 public int solution(string numbers) {
 
 List&lt;int&gt; numberList = new List&lt;int&gt;();
 

 for (int i = 0; i &lt; numbers.Length; ++i) //분리
 numberList.Add(numbers[i] - 48);
 
 List&lt;int&gt; result = new List&lt;int&gt;(); // 모음을 담아놓을 것

 // 한자릿 수는 먼저 결과에 넣어두기
 for(int i = 0; i &lt; numberList.Count; ++i)
 {
 if (result.Contains(numberList[i]) == true) continue;
 result.Add(numberList[i]); 
 }

 for (int i = 0; i &lt; numberList.Count; ++i)
 {
 for (int j = 0; j &lt; numberList.Count; j++)
 {
 //if (i == j) continue;

 char[] numToString = numbers.ToCharArray();

 char temp = numToString[j];
 numToString[j] = numToString[i];
 numToString[i] = temp;

 numbers = new string(numToString);

 int value = int.Parse(numbers);
 if (result.Contains(value) == true) continue;

 result.Add(value);
 }
 }


 // 0, 1 인 수 빼기 == 소수의 정의에 맞지 않음
 result.RemoveAll(rhs =&gt; rhs == 1);
 result.RemoveAll(rhs =&gt; rhs == 0);

 // 1과 나 자신 이외의 나머지가 0 이 되는수 ==&gt; 나눠지는 수, 
 //소수에 부합하지 않음. 삭제

 int answer = result.Count;

 for (int i = 0; i &lt; result.Count; ++i)
 {
 int resultValue = result[i];
 for (int j = 2; j &lt; resultValue; ++j)
 {
 if(j == 2) continue;
 if (resultValue % j == 0)
 {
 --answer;
 break;
 }
 }
 }
 return answer;
 }
}</code></pre><h3>오답 채점 결과 </h3><img src="https://image.until.blog/sin0105/article/1716964848582" alt="until-363"><h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>public class Solution
{
 static List&lt;int&gt; resultCollector = new List&lt;int&gt;();
 public int solution(string numbers)
 {

 bool[] isVisit = new bool[10];
 int[] numberArr = new int[numbers.Length];
 for (int i = 0; i &lt; numbers.Length; ++i)
 numberArr[i] = numbers[i] - 48;

 string newString = string.Empty;
 int answer = 0;
 DFS(numberArr, isVisit, 0, newString, ref answer);

 return answer;
 }

 public void DFS(int[] arr, bool[] isVisit, int depth, string numberString, ref int answerCnt)
 // DFS 로 찾는다.
 {
 for (int i = depth; i &lt; arr.Length; ++i)
 {
 var element = arr[i];

 SwapCharacter(arr, i, depth);
 DFS(arr, isVisit, depth + 1, numberString + element, ref answerCnt);

 int parseInt = int.Parse(numberString + element);
 if (resultCollector.Contains(parseInt) == false &amp;&amp; isPrimeCheck(parseInt) == true)
 {
 resultCollector.Add(parseInt);
 ++answerCnt;
 }

 SwapCharacter(arr, depth, i);
 }
 }

 public void SwapCharacter(int[] arr, int x, int y)
 {
 int temp = arr[x];
 arr[x] = arr[y];
 arr[y] = temp;
 }

 public bool isPrimeCheck(int number)
 {
 if (number == 0) return false;
 if (number == 1) return false;
 // 0, 1 은 소수가 아니다.

 if (number == 2) return true;
 // 2는 소수다.

 for (int i = 2; i &lt; number; ++i)
 {
 if (number % i == 0)
 return false;
 }
 // 0 으로 나눠진다면 소수가 아니다.

 return true;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1716964894808" alt="until-364">

코딩테스트 항해99 클럽 - 4일차 

[코딩테스트 일지 - 99클럽] 4일차 - 소수 찾기

[영상처리프로그래밍]

<h1>1. OpenCV란?</h1><blockquote>Open Source Computer Vision 영상 처리에 사용할 수 있는 오픈 라이브러리이다.</blockquote>OpenCV의 영상처리 및 컴퓨터 비전의 라이브러리를 사용하여 응용 프로그램을 쉽고 빠르게 만들 수 있다.<h1>2. NumPy란?</h1><blockquote>과학 계산을 위한 라이브러리로서 다차원 배열을 처리하는데 유용한 함수를 제공해주는 라이브러리</blockquote><h2>2.1. ndarray의 속성</h2><blockquote>ndarray란 Numpy의 n차원 객체로서, 하나의 데이터타입만 넣을 수 있다. (= C의 Array)</blockquote>이미지 배열은 numpy배열이다.<pre spellcheck="false"><code class="language-python">import cv2
img = cv2.imread("D:\citt.jpg")

print(type(img))

&gt;&gt; &lt;class 'numpy.ndarray'&gt;</code></pre><ul><li>ndim : 차원의 수 (기본적으로는 R, G, B, 즉 3이다.)</li><li>shape : 각 차원의 크기를 튜플로 나타냄</li><li>size : ndarray에 있는 요소의 총 개수</li><li>dtype : 요소의 데이터타입</li><li>itemsize : 각 요소의 바이트 크기</li></ul><h2>2.3. ndarray 객체 만들기</h2><h3>2.3.1. 값으로 만들기</h3><pre spellcheck="false"><code>import numpy as np

np.array(list [, dtype])</code></pre><ul><li>dtype : uint8, uint16, uint64(부호 없는 정수) / float16, float32, float64(부동소수점을 갖는 실수)</li></ul>보통은 8비트가 많이 쓰이는데, 그 이유는 픽셀의 밝기값이 256단계, 즉 8비트 데이터를 쓰기 때문이다.<pre spellcheck="false"><code class="language-python">import cv2
import numpy as np

ary = np.array([1, 2, 3, 4])
print(ary)
print(ary.dtype)

&gt;&gt;[1 2 3 4]
&gt;&gt; int64 (dtype값을 지정하지 않았으므로 array([])안에 있는 type으로 지정됨)</code></pre><pre spellcheck="false"><code class="language-python">ary = np.array([1, 2, 3.14, 4])
print(ary)
print(ary.dtype)

&gt;&gt;[1. 2. 3.14 4. ]
&gt;&gt; float64 
(ndarray는 한 가지 타입만 들어가기 때문에 타입이 섞여있으면 더 포괄적인 자료형으로 지정된다.)</code></pre><pre spellcheck="false"><code class="language-python">ary = np.array([1, 2, 3, 4])
print(ary.shape)

&gt;&gt; 4

ary = np.array([[1, 2], [3, 4]])
print(ary)
print(ary.shape)

&gt;&gt; [[1 2]
 [3 4]]
&gt;&gt; (2, 2)

ary = np.array([[1],[2],[3],[4]])
print(ary)
print(ary.shape)
&gt;&gt; [[1]
 [2]
 [3]
 [4]]
&gt;&gt; (4, 1)</code></pre><h3>2.3.2. 크기와 초기값으로 만들기</h3><ul><li>np.empty : 쓰레기값으로 채움</li><li>np.zeros : 0을 채움</li><li>np.ones : 1로 채움</li><li>np.full(shape, fill_value [, dtype)) : fill_value값으로 채움</li></ul><pre spellcheck="false"><code class="language-python">a = np.empty((2,3))
print(a)
print(a.dtype)

&gt;&gt; [[ 4.64583300e-308 4.66664552e-308 -2.57703408e+010]
 [-4.70231646e-064 2.26262303e-319 0.00000000e+000]]
&gt;&gt; float64 (empty는 초기화가 아님에 유의하기)
초기화가 필요할 때는 a.fill(0)처럼 fill()함수를 사용하기</code></pre>dtype을 지정해줄 때<pre spellcheck="false"><code class="language-python">c = np.zeros((2,3), dtype=np.unit8)</code></pre>컬러 이미지는 하나의 픽셀이 RGB값을 가지므로 3차원 배열이 필요하다.<h3>2.3.3. 기존 배열과 같은 크기의 배열 만들기</h3><ul><li>np.empty_like(array [, dtype]) : 크기만 같고 안에는 쓰레기값이 들어간다</li><li>np.zeros_like(img) : 0으로 채움</li></ul>

#1. OpenCV-Python

Java 기술면접

<h3>🥅 목표</h3>📝 Java 개념 Review &amp; 관련 기술 면접 질문에 대비해 보자<blockquote>(1) JVM이 뭘까요? (2) JDK, JVM, JRE 의 차이점을 말해주세요</blockquote><h3>Java의 동작구조</h3><img src="https://image.until.blog/woonideveloper423/article/1718544207971" alt="until-526">JDK, JVM, JRE 에 대해 자세히 살펴보기 전에 Java의 동작 구조를 한 번 살펴 보자<ol><li>개발자는 사람이 이해할 수 있는 언어로 소스 코드를 작성한다.(.java)</li><li>자바 컴파일러(javac.exe)가 자바 소스코드를 읽어서 가상 머신이 이해할 수 있는 바이트 코드로 변환한다.(.class)</li><li>Class Loader 를 통해 .class 파일이 JVM 메모리에 적재된다.</li><li>JVM 이 JAVA Interpreter(java.exe) 및 JIT 컴파일러 를 이용하여 바이트 코드를 실행한다.</li><li>JVM 이 메모리 관리,스레드 관리 등 런타임 환경을 제공한다.</li></ol><h3>JVM(Java Virtual Machine)이란?</h3>위 자바 코드의 동작 순서에서 JVM이 대략적으로 어떤 역할을 하는지 알 수 있었다. JVM 이란 자바 가상 머신으로 자바 프로그램을 실행하기 위한 가상 컴퓨터 역할을 한다. 여기서 가장 중요한 점은 JVM은 자바와 운영 체제 사이에서 중계 역할을 하여, 자바가 플랫폼 독립적 으로 실행 가능하게 해준다는 것이다. 정리하면 다음과 같다.<ul><li>JVM 은 자바 가상 머신을 자바 바이트코드를 실행하는 플랫폼 독립적인 실행 환경을 제공한다.</li><li>JVM은 컴파일된 바이트 코드를 해당 운영 체제가 이해할 수 있는 기계어로 변환하고 실행한다.</li><li>JVM의 존재로 같은 자바 프로그램을 한 번 작성하면 어느 운영체제에서나 실행된다.(Write Once, Run Any where)</li></ul><h3>JDK&amp;JRE 와의 차이점</h3>JDK와 JRE 또한 JVM 과 마찬가지로 자바 개발 및 실행에 있어 필수적인 구성요소이다. 구조는 대략적으로 다음과 같다.<img src="https://image.until.blog/woonideveloper423/article/1718544367014" alt="until-527">JRE(Java Runtime Environment)는 자바 실행 환경으로 자바 프로그램을 실행하기 위해 필요한 JVM 과 자바 클래스 라이브러리, 그리고 다른 지원 파일들을 포함한다. JRE만으로는 Java 프로그램 실행은 가능하지만 컴파일러가 없기 떄문에 자바 프로그램 개발은 불가능하다. 정리하면 JRE는 JVM을 동작하기 위한 자바 실행 환경이라 보면 되겠다. JDK(Java Development Kit) 은 자바 개발 키트로 자바로 프로그램까지 개발하고 싶다면 JDK를 설치해야만 한다. 보통 자바를 설치한다고 할 떄 이는 JDK 를 설치한다는 뜻과 거의 동일하다. JDK는 JRE(JVM)의 기능을 포함하고 있으며 .java 파일들을 .class 파일들로 변환하는 JavaCompiler(javac) 기능이 있다. JDK는 jdb 개발 도구를 통해 디버깅 기능도 제공한다.<h3>🔚 결론</h3>자 이제 관련 면접 예상 질문을 바탕으로 정리해보자<ol><li>JVM이란? ⏩ JVM은 컴파일된 바이트 코드를 운영체제가 이해할 수 있는 기계어로 번역해 실행하는 가상 머신이다.</li><li>JDK 와 JRE의 차이점은? ⏩ JRE는 JVM을 포함하여 자바 프로그램을 실행하기 위해 필요한 자바 클래스 라이브러리, 그 밖에 다른 지원파일을 포함하는 자바 실행 환경이다. (컴파일러가 없기 때문에 오직 실행만 가능하다.) JDK는 자바 컴파일러를 포함해 자바로 프로그램을 개발하기 위해 필요한 모든 도구를 포함한 키트이다. 자바로 프로그램을 개발하려면 JDK를 설치하여야 한다.</li></ol><h3>📚 참고자료</h3><ul><li><a target="_blank" rel="noopener noreferrer nofollow" href="https://wonyong-jang.github.io/java/2020/11/08/Java-JVM.html">https://wonyong-jang.github.io/java/2020/11/08/Java-JVM.html</a> </li></ul>

[Java&기술면접] JVM의 개념 및 JDK JRE 와의 차이점

<h3>코딩테스트 준비 일지</h3><ul class="tight" data-tight="true"><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.hackerrank.com/dashboard">해커랭크</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.hackerrank.com/challenges/one-month-preparation-kit-plus-minus/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=preparation-kits&amp;playlist_slugs%5B%5D=one-month-preparation-kit&amp;playlist_slugs%5B%5D=one-month-week-one">Plus Minus</a></li><li>난이도 : 하</li></ul><h3>문제</h3>Given an array of integers, calculate the ratios of its elements that are positive, negative, and zero. Print the decimal value of each fraction on a new line withplaces after the decimal.Note: This challenge introduces precision problems. The test cases are scaled to six decimal places, though answers with absolute error of up to 10^(-4), are acceptable.Examplearr = [1,1,0-1,-1]There are n = 5 elements, two positive, two negative and one zero. Their ratios are 2/5 = 0.400000 , 2/5 = 0.400000 , and 1/5 = 0.200000. Results are printed as:<pre spellcheck="false"><code>0.400000
0.400000
0.200000</code></pre>Function DescriptionComplete the plusMinus function in the editor below.plusMinus has the following parameter(s):<ul class="tight" data-tight="true"><li>int arr[n]: an array of integers</li></ul>Print Print the ratios of positive, negative and zero values in the array. Each value should be printed on a separate line withdigits after the decimal. The function should not return a value.Input FormatThe first line contains an integer,, the size of the array. The second line contains space-separated integers that describeConstraints<ul class="tight" data-tight="true"><li>0 &lt; n &lt;= 100</li><li>- 100 &lt;= arr[i] &lt;= 100</li></ul>Output FormatPrint the following lines, each to decimals:<ol class="tight" data-tight="true"><li>proportion of positive values</li><li>proportion of negative values</li><li>proportion of zeros</li></ol>Sample Input<pre spellcheck="false"><code>STDIN Function
----- --------
6 arr[] size n = 6
-4 3 -9 0 4 1 arr = [-4, 3, -9, 0, 4, 1]</code></pre>Sample Output<pre spellcheck="false"><code>0.500000
0.333333
0.166667</code></pre>ExplanationThere are positive numbers, negative numbers, and zero in the array. The proportions of occurrence are positive: 3/6 = 0.500000 , negative: 2/6 = 0.333333 and zeros: 1/6 = 0.166667<h3>문제 풀이 접근</h3>뭔가 문제가 영어다보니, 쉬운 문제도 어렵게 보이는 듯한 그런 느낌이 있다. 하지만, 이 문제는 아래와 같다. 1. n 개 정수 던져줄게 2. 양수 / 전체 , 음수 / 전체, 0 / 전체 이렇게 나눠서 값 출력해. 그래서 던져주는대로, 갯수를 먼저 세고, 양의 정수, 음의 정수, 0 의 값을 비율로 출력했다. 출력까지 하는줄 몰랐는데, 출력하니 All Case Pass 였다.<h3>작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{/*
 * Complete the 'plusMinus' function below.
 *
 * The function accepts INTEGER_ARRAY arr as parameter.
 */
public static List&amp;lt;double&amp;gt; ratio = new List&amp;lt;double&amp;gt;();public static void plusMinus(List&amp;lt;int&amp;gt; arr)
{
double count = arr.Count;
double posiCount = arr.FindAll(rhs =&amp;gt; rhs &amp;gt; 0).Count;
double NegaCount = arr.FindAll(rhs =&amp;gt; rhs &amp;lt; 0).Count;
double ZeroCount = arr.FindAll(rhs =&amp;gt; rhs == 0).Count;ratio.Add(posiCount/count);
ratio.Add(NegaCount/count);
ratio.Add(ZeroCount/count);}}class Solution
{
public static void Main(string[] args)
{
int n = Convert.ToInt32(Console.ReadLine().Trim()); List&amp;lt;int&amp;gt; arr = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(arrTemp =&amp;gt; Convert.ToInt32(arrTemp)).ToList();Result.plusMinus(arr);
var ratio = Result.ratio;for(int i = 0; i &amp;amp;lt; ratio.Count; ++i)
{
Console.WriteLine(ratio[i]);
}}}
</code></pre>

해커랭크 - 1 Month Preparation Kit 1번 문제.

[코딩테스트 일지] 해커랭크, Plus Minus

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/">Maximum Product of Two Elements in an Array</a></li><li>사용언어 : C#</li><li>난이도 : 최하</li><li>풀이시간 : 6m</li><li>유형 : 정렬, 시간복잡도, 배열</li></ul>1464. Maximum Product of Two Elements in an ArrayGiven the array of integers <code spellcheck="false">nums</code>, you will choose two different indices <code spellcheck="false">i</code> and <code spellcheck="false">j</code> of that array. Return the maximum value of <code spellcheck="false">(nums[i]-1)*(nums[j]-1)</code>.Example 1:<pre spellcheck="false"><code>Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 
</code></pre>Example 2:<pre spellcheck="false"><code>Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.
</code></pre>Example 3:<pre spellcheck="false"><code>Input: nums = [3,7]
Output: 12
</code></pre>&nbsp;Constraints:<ul><li><code spellcheck="false">2 &lt;= nums.length &lt;= 500</code></li><li><code spellcheck="false">1 &lt;= nums[i] &lt;= 10^3</code></li></ul><h3>문제 풀이 접근</h3>이 문제에 대한 접근 방법은 2가지가 생각났다. 1번. 리스트 돌면서 가장 큰 두개의 수를 찾아서 그 값을 -1 해서 곱한다. 2번. 어떤 리스트가 들어오던지 일단 정렬해서 2개를 찾는다. (2번 일때, 오름차순 내림차순 상관없다. 그거에 맞게 인덱스를 뽑아오면 되기 때문) 그런데, 여태까지 풀어왔던 코딩테스트에서는 이런 문제가 주어질 때, 효율성까지 테스트하면 1번의 방법은 효율성에서 패스 못하는 경우가 많았던 것으로 기억해서 2번으로 방향을 잡았다. 이 문제의 플로우 1. 들어온 배열을 정렬한다. ( 오름차순으로 가정 ) 2. 2개 이상은 꼭 들어온다는 것이 문제에 보장되어 있다. 그렇기 때문에, (arr[arr.Length-2] -1) * (arr[arr.Length-1]-1); 을 연산해서 반환한다.<h3>정답 작성 코드 (C#) - 오름차순</h3><pre spellcheck="false"><code>using System;
using System.Collections;

public class Solution {
 public int MaxProduct(int[] nums) {
 int answer = 0;

 Array.Sort(nums);
 answer = (nums[nums.Length-1]-1 ) * (nums[nums.Length-2]-1 );
 return answer;
 }
}</code></pre><h3>정답 작성 코드 (C#) - 내림차순</h3><pre spellcheck="false"><code>using System;
using System.Collections;

public class Solution {
 public int MaxProduct(int[] nums) {
 int answer = 0;

 Array.Sort(nums, (num1,num2) =&gt; num2.CompareTo(num1));
 answer = (nums[0]-1 ) * (nums[1]-1 );
 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1722783174683" alt="until-1179">

혼자서 다시푸는 코딩테스트 준비 일지 - 10

코딩테스트 준비 - Maximum Product of Two Elements in an Array

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42747">H - Index</a></li><li>사용언어 : C#</li><li>난이도 : 중상</li><li>풀이시간 : 1h 49m</li><li>유형 : 정렬, 문제이해, 인덱스</li></ul><h6>문제 설명</h6>H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과<a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42747#fn1">1</a>에 따르면, H-Index는 다음과 같이 구합니다.어떤 과학자가 발표한 논문 <code spellcheck="false">n</code>편 중, <code spellcheck="false">h</code>번 이상 인용된 논문이 <code spellcheck="false">h</code>편 이상이고 나머지 논문이 h번 이하 인용되었다면 <code spellcheck="false">h</code>의 최댓값이 이 과학자의 H-Index입니다.어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul><li>과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.</li><li>논문별 인용 횟수는 0회 이상 10,000회 이하입니다.</li></ul><h5>입출력 예</h5>citations return [3, 0, 6, 1, 5] 3<h5>입출력 예 설명</h5>이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다. ** H-Index 이해 필요 <a target="_blank" rel="noopener noreferrer nofollow" href="https://en.wikipedia.org/wiki/H-index">링크</a><h3>문제 풀이 접근</h3>이 문제는, 문제의 불친절함 때문에 여러번 낚였다. 구현과 생각을 4번 정도 변경해서 오래걸렸다. 여기서 말하는 H-Index의 비교수는 결코 Element의 값이 아니라 순수 Loop 되는 Index 로 생각하면 편하다. 문제를 다 풀고나서 생각이지만, 정말 이해하기 어려웠다. 위키피디아 보고나서 5분만에 고쳐서 해결했다. 이 문제의 플로우는, 1. 받은 배열을 정렬한다. (내림차순) 2. 진행한 인덱스 i 의 값을 만족하지 못하는 수가 발견되면 break 해도 좋고, i 의 값 이상 인용된 논문을 찾아서 answer에 넣어주면 쉽게 풀린다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

public class Solution {
 public int solution(int[] citations) {
 int answer = 0;
 Array.Sort(citations);
 List&lt;int&gt; list = new List&lt;int&gt;();
 
 if(citations.Length == 1)
 return citations[0];
 
 for(int i =0; i &lt; citations.Length; ++i)
 list.Add(citations[i]);
 
 list.Sort((int a, int b)=&gt;{return b.CompareTo(a);});
 
 for(int i = 0; i &lt; list.Count; ++i)
 {
 int index = i+1;
 int count = list.FindAll(rhs=&gt; rhs &gt;= index).Count;
 
 if(index &lt;= count)
 answer = index;
 }

 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724185496584" alt="until-1259">다시 생각해봐도 정말 시간 아까웠다. 더빨리 풀 수 있었는데.. 다시 푸는 것으로 동일한 문제에 대한 포스팅이 있다. <a target="_blank" rel="noopener noreferrer nofollow" href="https://until.blog/@sin0105/-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9D%BC%EC%A7%80---99%ED%81%B4%EB%9F%BD--2%EC%9D%BC%EC%B0%A8---h-index">링크</a>

혼자서 다시푸는 코딩테스트 준비 일지 - 15

코딩테스트 준비 - H - Index

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42746">가장 큰 수</a></li><li>사용언어 : C#</li><li>난이도 : 중하</li><li>풀이시간 : 1h13m</li><li>유형 : 정렬, 수 비교, 배열</li></ul><h6>문제 설명</h6>0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.<h5>제한 사항</h5><ul><li>numbers의 길이는 1 이상 100,000 이하입니다.</li><li>numbers의 원소는 0 이상 1,000 이하입니다.</li><li>정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.</li></ul><h5>입출력 예</h5>numbers return [6, 10, 2] "6210" [3, 30, 34, 5, 9] "9534330"<h3>문제 풀이 접근</h3>이 문제에선 삽질을 많이해서 여러번 정답을 들이밀면서 해결해보았다. 1. 모든 조합을 구한 뒤, 큰 수 부터 정렬하여 구하는 방법 2. 문제에서 원소 크기는 1000 으로 고정되었기 때문에, 자릿 수를 10000만의 자리까지 끌고 올라와서 정렬하여 비교하는 방법 먼저, 1번은 효율성에서 좋지 않아 보인다. 일단 모든 조합수를 구하는 데 있어서, O(N^2) 이 들 수 밖에 없다. 모든 원소의 값을 다 구한 뒤 정렬도 수행해야하기 때문이다. 결국 O(N^2) + O(N Log N) 의 시간복잡도로 가정된다. ( 편의상 전부 적어보았음 ) 그렇다면 2번의 방법은 어떤게 다른가? 2번은 원소의 수를 잠시 5자리 이상의 수로 연산을한 뒤 정렬을 하면, 1번에서 O(N^2)는 안들고 정렬에 대한 시간 복잡도인 +O(N Log N) 정도만 들겠다. 그러면 수를 정렬하는 방법은 단순히 [6,10,2] 등과 같이 수가 다 다르다면 상관은 없을 수 있는데, [3,3000] 과 같이 앞자리가 같은수는 결국 3 * 10000 , 3000 * 10 을 하면 결국 30000으로 같다. 그렇기 때문에 자릿수를 맞추는 것은 수를 문자열로 바꾼 후 문자열의 길이만큼 Loop하여 추가한다. 그러면 33333 , 30003 이기 때문에, 3이 더 큰수로 나올 것이다. 이런 아이디어로 비교를 하여 정렬을 하게된다면 정답을 찾을 수 있다. 문제의 플로우는 아래와 같다. 1. Tuple을 이용하여, Key : 6자리 변경 수 , Value : 원래 수 2. Key 기준으로 정렬 3. List의 처음부터 끝까지 원래 수를 StringBuilder 에 Append 하면서 추가. 4. 그리고 Int32.Parse로 캐스팅하여 반환<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Text;
using System.Collections.Generic;

public class Solution {
 public string solution(int[] numbers) {
 string answer = "";
 int isZero = 0;

 if(numbers.Length == 1)
 {
 return numbers[0].ToString();
 }
 
 for(int i = 0; i &lt; numbers.Length; ++i)
 {
 if(numbers[i] == 0)
 ++isZero;
 }
 
 if(isZero == numbers.Length)
 {
 answer = "0";
 return answer;
 }
 
 
 // 모두 100000의 숫자로 변경해서 체크.
 List&lt;Tuple&lt;int,int&gt;&gt; list = new List&lt;Tuple&lt;int,int&gt;&gt;();
 
 for(int i = 0; i &lt; numbers.Length; ++i)
 { 
 int valueInt = numbers[i];
 int makeInt = MakeValue(valueInt);
 
 list.Add(new Tuple&lt;int,int&gt;(makeInt,valueInt));
 }
 
 var toArr = list.ToArray();
 
 Array.Sort(toArr, (a,b) =&gt; {return b.Item1.CompareTo(a.Item1);});
 
 StringBuilder sb = new StringBuilder();
 for(int i = 0; i &lt; toArr.Length; ++i)
 {
 var element = toArr[i];
 sb.Append(element.Item2);
 }
 
 answer = sb.ToString();
 return answer;
 }
 
 public int MakeValue(int valueInt)
 {
 int ret = 0;
 String valueString = valueInt.ToString();
 StringBuilder sb = new StringBuilder();
 int intIndex = 0;
 
 while(sb.Length != 6) // 비교는 10만으로 비교, 즉 6자리 수로 비교하겠다.
 {
 if(valueString.Length == intIndex)
 intIndex = 0;
 
 
 char element = valueString[intIndex];
 sb.Append(element);
 ++intIndex;
 }
 
 ret = Int32.Parse(sb.ToString());
 return ret;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724065391054" alt="until-1246">

혼자서 다시푸는 코딩테스트 준비 일지 - 13

코딩테스트 준비 - 가장 큰 수

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42576">완주하지 못한 선수</a></li><li>사용언어 : C++</li><li>난이도 : 중 or 중하</li><li>풀이시간 : 15m</li><li>유형 : 해시 , 정렬</li></ul><h6>문제 설명</h6>수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul><li>마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.</li><li>completion의 길이는 participant의 길이보다 1 작습니다.</li><li>참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.</li><li>참가자 중에는 동명이인이 있을 수 있습니다.</li></ul><h5>입출력 예</h5>participant completion return ["leo", "kiki", "eden"] ["eden", "kiki"] "leo" ["marina", "josipa", "nikola", "vinko", "filipa"] ["josipa", "filipa", "marina", "nikola"] "vinko"["mislav", "stanko", "mislav", "ana"] ["stanko", "ana", "mislav"] "mislav"<h5>입출력 예 설명</h5>예제 #1 "leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.예제 #2 "vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.예제 #3 "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.<h3>문제 풀이 접근</h3>이 문제는, 어제 풀었던 것과 같이 문자열의 정렬 기준만 알면 간단하게 풀 수 있다. complete 의 길이가 participant 의 길이 보다 1 작아서 무조건 1명만 반환한다는 제약도 있고, 애초에 return 값이 문자열 하나다. 그래서 하나 작다고 유추할 수도 있다. 문자열의 정렬 기준을 이용해서 둘다 정렬하고, 각 index에 매칭되는 것이 있는지 체크를 한 후에 맞지 않는 Case 가 있다면 answer 에 저장하고 리턴하면 옳은 값을 도출해 낼 수 있다.<h3>정답 작성 코드 (C++) - 문제가 C# 지원 안한다.</h3><pre spellcheck="false"><code>#include &lt;string&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

using namespace std;

string solution(vector&lt;string&gt; participant, vector&lt;string&gt; completion) {
 string answer = "";
 
 sort(participant.begin(), participant.end());
 sort(completion.begin(), completion.end());
 
 
 string strParticipant = "";
 string strCompletion = "";
 
 for(int i = 0; i &lt; participant.size(); ++i)
 {
 if(answer != "")
 {
 return answer;
 }
 
 if(i &lt; completion.size() &amp;&amp; participant[i] != completion[i])
 answer = participant[i];
 }
 
 if(answer == "")
 {
 answer = participant[participant.size()-1];
 }
 
 return answer;
}</code></pre><h3> </h3>

혼자서 다시푸는 코딩테스트 준비 일지 - 3

코딩테스트 준비 - 완주하지 못한 선수

다시푸는 코딩 테스트 준비 일지

문제 설명

제한사항

입출력 예

입출력 예 설명

문제 풀이 접근

정답 작성 코드 (C++) - 문제가 C# 지원 안한다.