C++ Code

CodingTest

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li><p>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/3273">3273.두 수의 합</a></p></li><li><p>사용언어 : C#</p></li><li><p>난이도 : Milddle</p></li><li><p>풀이시간 : 20m</p></li><li><p>유형 : 투 포인터</p></li></ul><h2>문제</h2><p>n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i &lt; j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.</p><h2>입력</h2><p>첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)</p><h2>출력</h2><p>문제의 조건을 만족하는 쌍의 개수를 출력한다.</p><h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>9
5 12 7 10 9 1 2 3 11
13
</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>3
</code></pre><h2>문제 풀이 접근</h2><p>이 문제는 투 포인터로 해결할 수 있다. <br>정렬을 해도 그만, 안해도 그만이지만, 값을 비교해서 인덱스를 올리고 내리는 과정이 필요해 나는 정렬하여 풀이를 했다. </p><p>아직 투 포인터 문제 관련해 반복 조건식에 조금 익숙치 않아 시간이 걸렸는데, <br>조건식을 <br>while(_left &lt; (_maxRight <em> 0.5) &amp;&amp; right &gt;= (maxRight </em> 0.5))<br>이렇게 짤때도 있었고, <br>while(_left &lt; (_right * 0.5)) <br>이렇게 짤때도 있었다. </p><p>그러나, 단순하게 조건식을 while(left &lt; right) 로 두면 되는 문제였다. <br>그 이유는 어차피 둘다 인덱스 용도이기도 하며, 양 끝단의 투포인터 인덱스가 중앙인덱스까지 루프한다는 조건 자체가 맞지 않았다. <br>arr[7] 배열 0 1 2 3 4 5 6 이 있으면 left가 1 right 가 2 가 온 뒤에 left 가 1 증가해서 끝나는 경우가 있을 것이고 배열의 값 상황에 따라 끝나는 지점을 매번 바뀔 수 있다. </p><p>그 점을 항상 생각하면서 투포인터 문제를 접근해야할 것으로 보인다.</p><h3>작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : Middle
// * URL : https://www.acmicpc.net/problem/3273
//  * Time : 20m
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public int _ret;
        public int _n;
        public int _m;
        public int[] _arr;

        public int _left;
        public int _right;
        public void solve()
        {
            _n = int.Parse(Console.ReadLine());

            _arr = new int[_n];

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

            for(int i =0; i &lt; _n; ++i)
                _arr[i] = int.Parse(_input[i]);

            Array.Sort(_arr);

            _m  = int.Parse(Console.ReadLine());

            _left = 0;
            _right = _n - 1;

            while(_left &lt; _right)
            {
                if(_arr[_left] + _arr[_right] == _m)
                {
                    ++_ret;
                    ++_left;
                    --_right;
                }
                else if (_arr[_left] + _arr[_right] &lt; _m)
                {
                    ++_left;
                }
                else
                {
                    --_right;
                }
            }

            Console.WriteLine(_ret);
        }
    }
}
</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1734622065945.png" data-width="100%" data-align="center" alt="2584"><p></p>

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

코딩테스트 준비 - 두 수의 합

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li><p>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/15652">15652.N과 M(4)</a></p></li><li><p>사용언어 : C#</p></li><li><p>난이도 : Easy ~ Middle</p></li><li><p>풀이시간 : 21m</p></li><li><p>유형 : 백트래킹 , DFS</p></li></ul><h2>문제</h2><p>자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.</p><ul><li><p>1부터 N까지&nbsp;자연수 중에서 M개를 고른 수열</p></li><li><p>같은 수를 여러 번 골라도 된다.</p></li><li><p>고른 수열은 비내림차순이어야 한다.</p><ul><li><p>길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.</p></li></ul></li></ul><h2>입력</h2><p>첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)</p><h2>출력</h2><p>한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.</p><p>수열은 사전 순으로 증가하는 순서로 출력해야 한다.</p><h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>3 1
</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>1
2
3
</code></pre><h2>예제 입력 2 복사</h2><pre spellcheck="false"><code>4 2
</code></pre><h2>예제 출력 2 복사</h2><pre spellcheck="false"><code>1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
</code></pre><h2>예제 입력 3 복사</h2><pre spellcheck="false"><code>3 3
</code></pre><h2>예제 출력 3 복사</h2><pre spellcheck="false"><code>1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3</code></pre><h3>문제 풀이 접근</h3><p>이 문제에서는 요구사항이, 이전 수보다 이상인 들을 이용하여 순열을 구성하는것이다.<br>가능과 불가능 케이스를 나누자면, </p><p>가능</p><ul><li><p>1 1 1</p></li><li><p>1 1 2</p></li><li><p>1 2 3</p></li></ul><p>불가능</p><ul><li><p>1 2 1</p></li><li><p>1 3 2 </p></li><li><p>1 4 1 </p></li></ul><p>즉 이전 수 보다 작으면 안된다는 얘기다. <br>이 문제는 단순하게 Cnt, Pos 값으로 해결할 방법을 찾아보았으나, 이전 수를 넣어주는 파라미터를 추가하여, 0부터 순회하지만, 이전수인 Prev 보다 작을 경우 Continue로 순회할 수 있도록 작성해주었더니 문제를 풀 수 있었다. </p><p>플로우에 대한 케이스는 이렇게 된다.</p><p>1 2 3 4 가 있을때, 4 개 중 2개를 뽑는다. <br>_per 에는 1 x 가 들어가고, 1 2 , 1 3 , 1 4 가 모두 순회한 후에 2 x 를 구하는 번째에서 prev 의 값인 arr[i] 값을 파라미터로 넣으면 1이 들어간다. <br>그렇게되면 2 x 에서 x 는 arr의 i 가 0 부터 순회를 하게되는데 arr[0]  == 1 이기때문에 continue로 통과하게 된다.  <br>그 이후 i 가 1로 증가하여 arr[1] 의 값을 참조하면 2 이기 때문에 2 x 에서 2 2 를 뽑아낼 수 있게된다. </p><p>이렇게 값이 증가하여 문제에서 요구하는 순열을 구성할 수 있게되어, 문제를 해결할 수 있다.</p><h3>작성 코드 (C#)</h3><pre spellcheck="false"><code class="language-csharp">using System;
using System.Collections.Generic;
using System.IO.Pipes;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;

///*
// * Difficulty : Easy
// * URL : https://www.acmicpc.net/problem/15652
//  * Time : 21m
// */

namespace Test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }


    public class Solution
    {
        public const int max = 9;
        public int _n;
        public int _m;

        public int[] _arr;
        public int[] _per;

        public StringBuilder _sb;

        public void solve()
        {
            _sb = new StringBuilder();
            string[] _in  = Console.ReadLine().Split(' ');

            _n = int.Parse(_in[0].ToString());
            _m = int.Parse(_in[1].ToString());

            _arr = new int[max];

            for(int i = 0; i &lt; max; ++i)
                _arr[i] = i + 1;

            _per = new int[max];

            dfs(0, 0,0);

            Console.Write(_sb.ToString());
        }
        public void dfs(int cnt, int pos, int prev)
        {
            if(cnt  &gt;= _m)
            {
                for(int i = 0; i &lt; cnt; ++i)
                {
                    _sb.Append(_per[i]);

                    if(i != cnt -1 )
                        _sb.Append(" ");
                }

                _sb.AppendLine();
            }
            else
            {
                for(int i = 0; i &lt; _n; ++i)
                {
                    if (_arr[i] &lt; prev) continue;

                    _per[pos] = _arr[i];
                    dfs(cnt+1, pos + 1, _arr[i]);
                }
            }
        }
    }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1731909951818.png" data-width="100%" data-align="center" alt="2180">

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

코딩테스트 준비 - N과 M(4)

Experience

<p>게임을 만들기 위해서는 수많은 방법이 존재하는데, 그 중 데이터를 어떻게 효율적으로 관리할지에 대한 고민은 항상 존재한다고 생각한다.</p><p>회사를 많은 회사를 경험해보진 못했지만, 이번에 적는 내용은 도입하는 회사도 있었고, 도입하지 않는 회사도 있었다.</p><p>개인적으로는 도입한 회사를 다닌쪽이 조금더 편했기도 하고, 생각하는 방향이랑 맞았었다.</p><p>초기 구상했던 툴 기획은 아래와 같다.</p><hr><p>제작 : C# Winform</p><p>사용 라이브러리</p><ul><li><p>OfficeOpenXml</p></li><li><p>System.IO</p></li></ul><p>외에는 System.Text 나 이런 주로 사용되는 namespace다.</p><hr><h2><strong>ClassTypeExporter</strong></h2><h3>1. 제작 의도</h3><p>기획자에게 Enum Type에 대한 추가 권한을 주기 위해 제작 필요</p><h3>2. 제작으로 인해 얻는 이득</h3><p>타입에 대한 추가 사양이 있을 시, 기획자가 추가하여, 개발자와의 불필요한 커뮤니케이션 비용을 줄일수 있다.</p><h3>3. 툴의 한계점</h3><ul><li><p>추가는 할 수 있으나, 이후 기능적인 부분이 적용되는 것은 개발자에게 알려줘야한다.</p></li><li><p>있던 타입을 제거하기 위해서는, 게임 프로젝트 내 컴파일 에러가 출력되기 때문에, 개발자에게 알려줘야한다.</p></li></ul><hr><p>세부 규칙은 이렇다.</p><h2>ClassTypeExporter Tips</h2><hr><p>파일의 세부 규칙을 기술한다.</p><h3>파일</h3><ul><li><p>엑셀 파일 접두어로 “Field” 을 붙인다.</p></li></ul><h3>시트</h3><ul><li><p>(Field +시트 파일명)은 Enum 의 타입명 이 된다.</p><ul><li><p>Sheet : GamaData ⇒ FieldGameData</p></li></ul></li></ul><h3>컬럼</h3><ul><li><p>컬럼 (0,0) 내용에 “Link” 가 없을 시 변환하지 않는다.</p></li><li><p>컬럼 변환 시작은 (0,2) 컬럼부터 시작한다.</p></li><li><p>변환은 Y 방향으로 아래로 증가하며, 빈 공간이 발견될때까지 변환한다</p></li></ul><hr><p>뭔가 내용은 어려워 보이는데, 특별한 내용은 없다. <br>첫 컬럼에 변환 작업을 할 것인지 아닌지 판단하는 것이 끝이다.</p><p>여기 보이는 0,0 에 있는 Link를 달면 변환 작업을 하는 것이다.</p><img src="https://image.until.blog/sin0105/article/1733671437511.png" data-width="100%" data-align="center" alt="2439"><p>이렇게 준비된 Excel을 아래 툴을 이용해서 추가한다.</p><img src="https://image.until.blog/sin0105/article/1733672000716.png" data-width="75%" data-align="center" alt="2446"><p>이번엔 엑셀데이터를 타입으로 변환하는 기능이기 때문에 Field가 엑셀 파일의 접두어로 들어가 있어야 올바른 변환을 한다.</p><img src="https://image.until.blog/sin0105/article/1733672023339.png" data-width="75%" data-align="center" alt="2447"><p>이 상태에서 데이터 추출 버튼을 클릭하게 되면, 내가 지정한 경로로 파일이 생성된다. <br>시트명이 LoadData 였기 때문에, FieldLoadData.cs 로 파일이 만들어지게 된다.</p><img src="https://image.until.blog/sin0105/article/1733671799534.png" data-width="100%" data-align="center" alt="2443"><p>결과는 생각한대로 자동으로 만들어지는 EnumType 추출기가 만들어졌다.</p><img src="https://image.until.blog/sin0105/article/1733671830265.png" data-width="100%" data-align="center" alt="2444"><p></p>

게임을 효율적으로 서비스하기 위해 준비할 아이템

Excel 내용을 Enum타입의 스크립트로 변환해보기

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li><p>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/16922">16922.로마숫자만들기</a></p></li><li><p>사용언어 : C#</p></li><li><p>난이도 : Middle</p></li><li><p>풀이시간 : 1h over</p></li><li><p>유형 : 백트래킹 , DFS</p></li></ul><h2>문제</h2><p>로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.</p><p>하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.</p><p>실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.</p><p>로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.</p><h2>입력</h2><p>첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.</p><h2>출력</h2><p>첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.</p><h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>1
</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>4
</code></pre><p>I, V, X, L을 만들 수 있다.</p><h2>예제 입력 2 복사</h2><pre spellcheck="false"><code>2
</code></pre><h2>예제 출력 2 복사</h2><pre spellcheck="false"><code>10
</code></pre><p>2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다.</p><h2>예제 입력 3 복사</h2><pre spellcheck="false"><code>10
</code></pre><h2>예제 출력 3 복사</h2><pre spellcheck="false"><code>244
</code></pre><h3>문제 풀이 접근</h3><p>이 문제의 풀이 방식 자체는 이전에 했던 N과 M 시리즈와 상당히 유사하다. <br>단지 I V X L 등의 문자를 숫자로 변경해 나올 수 있는 숫자의 종류를 돌려주는 문제다.<br><br>이 문제를 더 빠르게 풀기 위해, 탐색 속도를 올리기위해 해쉬테이블 기반의 유니크한 값을 가지는 HashSet을 사용했으나, 4^20 의 가짓수를 2초 내에 패스하는 것에 무리가 있어 시간초과로 패스하지 못했다.</p><p>이 방식을 수정하기 위해, HashSet대신 Count 를 증가하면서 해보아도 시간 초과가 나왔고, bool 배열로 카운트를 해도 시간초과가 나왔다.</p><p>해결법은 아래와 같다. <br>문제를 보면 IXVL로 4가지의 선택지가 있고, 최대 20번 뽑을 수 있다.<br>고로 아까 위에 적어둔 4^20번 호출될 수 있고, 이는 상당히 무거운 호출 수다. <br>15번만 뽑아도 대략 5~6초가 걸렸었다. <br><br>그렇기 때문에, 모든 케이스에서 4번 뽑는 선택지를 최대한 줄여주도록 해야한다. <br>4가지 문자에서 2가지를 뽑는다면 이렇게된다. <br><strong><em>II</em></strong> IV IX IL<br>VI <strong><em>VV</em></strong> VX VL<br>XI XV <strong><em>XX</em></strong> XL<br>LI LX LV <strong><em>LL</em></strong><br>이 식에서 잘보면 (1,2) 와 (2,1)은 IV , VI =&gt; 값 : 6 으로 같다. 고로, II VV XX LL 와 같이 볼드체인 숫자를 기준으로 대칭되는 수는 한번만 뽑아도 된다. <br>왜? 문제에서 숫자의 가짓수를 반환하길 원하니 한번만 뽑으면된다. <br>이렇게 하면 <br><strong><em>II</em></strong> IV IX IL<br><s>VI</s> <strong><em>VV</em></strong> VX VL<br><s>XI</s> <s>XV</s> <strong><em>XX</em></strong> XL<br><s>LI LX LV</s> <strong><em>LL</em></strong><br>이렇게된다. 이를 코드로 나타내면 최적화가 된다. <br>처음 I 를 뽑을때는 I 부터 V X L 을 다뽑아도된다. <br>그 후 V로 넘어올 때는 VI를 찾을 필요가 없기 때문에, V의 배열상 위치인 1위치부터 시작하여 순회하면 된다 ( 배열 시작은 0위치 부터 시작함.)<br><br>값을 저장하기 위한 인덱스를 계속해서 파라미터로 넘겨주고, 2장 뽑은 경우 내가 만들어 놓은 bool 배열을 true로 변경하거나, false 를 true 로 바꾸는 상황에만 count를 올려주면 뽑을 수 있는 최대한의 갯수를 알 수 있다.</p><h3>작성 코드 (C#)</h3><pre spellcheck="false"><code class="language-csharp">using System;
using System.Collections.Generic;
using System.Text;

/////*
//// * Difficulty : Middle ~ hard
//// * URL : https://www.acmicpc.net/problem/16922
////  * Time : 1h over
//// */

namespace Test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }

    public class Solution
    {
        public const int maxValues = 50;
        public const int max = 20;
        public int _n;
        public int _m;
        public char[] _arr;
        public char[] _per;
        public bool[] _checkCnt;

        public int _ret = 0;

        public void solve()

        {
            _checkCnt = new bool[(maxValues * max) + 1];
            string _in = Console.ReadLine();
            _n = 4;
            _m = int.Parse(_in.ToString());

            _arr = new char[4];
            _arr[0] = 'I';
            _arr[1] = 'V';
            _arr[2] = 'X';
            _arr[3] = 'L';

            _per = new char[max];

            dfs(0, 0, 0);

            Console.Write(_ret);
        }

        public void dfs(int cnt, int pos, int calc)
        {
            if (cnt &gt;= _m)
            {
                if (_checkCnt[calc] == false)
                {
                    _checkCnt[calc] = true;
                    ++_ret;
                }
            }
            else
            {

                for (int i = pos; i &lt; _n; ++i)
                {
                    dfs(cnt + 1, i, calc + GetVal(_arr[i]));
                }
            }
        }

        public int GetVal(char a)
        {
            if (a == 'I')
                return 1;
            if (a == 'V')
                return 5;
            if (a == 'X')
                return 10;
            if (a == 'L')
                return 50;

            return 0;
        }
    }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1732030585724.png" data-width="100%" data-align="center" alt="2215"><p></p>

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

코딩테스트 준비 - 로마 숫자 만들기

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

코딩테스트 준비 - 눈덩이굴리기

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li><p>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/15663">15663.N과 M(9)</a></p></li><li><p>사용언어 : C#</p></li><li><p>난이도 : Middle</p></li><li><p>풀이시간 : 38m</p></li><li><p>유형 : 백트래킹 , DFS</p></li></ul><h2>문제</h2><p>N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.</p><ul><li><p>N개의 자연수 중에서 M개를 고른 수열</p></li></ul><h2>입력</h2><p>첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)</p><p>둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.</p><h2>출력</h2><p>한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.</p><p>수열은 사전 순으로 증가하는 순서로 출력해야 한다.</p><h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>3 1
4 4 2
</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>2
4
</code></pre><h2>예제 입력 2 복사</h2><pre spellcheck="false"><code>4 2
9 7 9 1
</code></pre><h2>예제 출력 2 복사</h2><pre spellcheck="false"><code>1 7
1 9
7 1
7 9
9 1
9 7
9 9
</code></pre><h2>예제 입력 3 복사</h2><pre spellcheck="false"><code>4 4
1 1 1 1
</code></pre><h2>예제 출력 3 복사</h2><pre spellcheck="false"><code>1 1 1 1
</code></pre><h3>문제 풀이 접근</h3><p>이 문제부터는 N과M 시리즈에서 배열의 값도 동일한 숫자도 나오는 것 같다. <br>동일한 수를 배열에 들어갈 수도 있게 함으로써, 중복 순열에 대한 처리 등을 어떻게 하는지 체크하는 것으로 보인다. <br><br>만약 List와 같은 탐색에 O(N) 시간 복잡도를 가진다면, 아마도 이 문제에선 결과를 타임 아웃으로 리턴할 것으로 보인다. <br><br>문제는 크게 어려운 것은 없으며, HashSet을 이용해, 이미 HashSet이 담겨진 내용은 StringBuilder에 입력되지 않도록 처리하여 중복 출력을 회피하였다.</p><h3>작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : Middle
// * URL : https://www.acmicpc.net/problem/15663
//  * Time : 38m
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public const int _max = 8;
        public int _n;
        public int _m;
        public int[] _arr;
        public bool[] _isVisited;


        public StringBuilder _sb;
        public StringBuilder _sbc;

        public HashSet&lt;string&gt; _hs;
        public void solve()
        {
            _hs = new HashSet&lt;string&gt;();
            string[] _input = Console.ReadLine().Split(' ');
            _isVisited = new bool[_max];

            _n = int.Parse(_input[0]);
            _m = int.Parse(_input[1]);
            _input = Console.ReadLine().Split(' ');
            _sb = new StringBuilder();
            _sbc = new StringBuilder();
            _arr = new int[_n];
            int[] _per = new int[_m];

            for (int i = 0; i &lt; _arr.Length; ++i)
                _arr[i] = int.Parse(_input[i]);

            Array.Sort(_arr);

            BT(0, ref _per);
            Console.Write(_sb.ToString());
        }

        public void BT(int cnt, ref int[] _c)
        {
            if (cnt == _m)
            {
                _sbc.Clear();

                for (int i = 0; i &lt; cnt; ++i)
                {
                    _sbc.Append(_c[i]);

                    if (i != cnt - 1)
                        _sbc.Append(' ');
                }

                if(_hs.Contains(_sbc.ToString()) == false)
                {
                    _hs.Add(_sbc.ToString());
                    _sb.Append(_sbc.ToString());
                    _sb.AppendLine();
                }
            }
            else
            {
                for (int i = 0; i &lt; _n; ++i)
                {
                    if (_isVisited[i] == false)
                    {
                        _c[cnt] = _arr[i];
                        _isVisited[i] = true;
                        BT(cnt + 1, ref _c);
                        _isVisited[i] = false;
                    }
                }
            }
        }
    }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1732719706110.png" data-width="100%" data-align="center" alt="2344"><p>** 실버 2까지 앞으로 2점 남았다.</p><p></p>

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

코딩테스트 준비 - N과 M(9)

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li><p>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/2003">2003.수들의_합_2</a></p></li><li><p>사용언어 : C#</p></li><li><p>난이도 : Easy</p></li><li><p>풀이시간 : 31m +</p></li><li><p>유형 : 투 포인터</p></li></ul><h2>문제</h2><p>N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.</p><h2>입력</h2><p>첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.</p><h2>출력</h2><p>첫째 줄에 경우의 수를 출력한다.</p><h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>4 2
1 1 1 1
</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>3
</code></pre><h2>예제 입력 2 복사</h2><pre spellcheck="false"><code>10 5
1 2 3 4 2 5 3 1 1 2
</code></pre><h2>예제 출력 2 복사</h2><pre spellcheck="false"><code>3</code></pre><h2>문제 풀이 접근</h2><p>이 문제는, 투 포인터, DFS 등 여러 방법을 활용할 수 있는 문제로 보인다. <br>제시하는 문제의 조건은 수열은 정해져있고, 수열의 i 번째 수 부터 J 번째 수 까지 M이 되는 경우의 수를 구하는 것인데, 이는 무슨의미냐면 1 2 3 4 5 이고 M 7일때, 경우의 수를 구하라. 이는 3+4, 1개만 존재하는데 연속되는 배열을 더했을 때 M이 되는 경우의 수를 출력하라는 의미다.</p><p>나는 문제를 해결하기 위해 앞선 시리즈인 <a target="_blank" rel="noopener noreferrer nofollow" href="https://until.blog/@sin0105/1231">수들의합5 </a>처럼 기준이 되는 인덱스(Standard)부터 출발하여 좌측에서 우측으로 더하는 방식을 선택했고 투 포인터 알고리즘이기때문에, 우측 기준부터 좌측으로 넘어가는 것도 동일하게 작성했다.</p><p>중간의 _IsSuccess 로 시작하는 필터링 구문은 LeftIndex 와 rightIndex가 동일한데, leftIndex에서 이미 Pass 처리를 했다면 중복으로 처리할 필요는 없기 때문에, 예외처리를 한 구문이다.</p><h3>작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : 
// * URL : https://www.acmicpc.net/problem/2003
//  * Time : 
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        int _n;
        int _m;

        int _left;
        int _right;

        int[] _arr;
        public void solve()
        {
            string[] input = Console.ReadLine().Split(' ');
            _n = int.Parse(input[0]);
            _m = int.Parse(input[1]);

            _arr = new int[_n];

            //Array.Sort(_arr);

            input = Console.ReadLine().Split(' ');

            for (int i = 0; i &lt; input.Length; i++)
                _arr[i] = int.Parse(input[i]);

            _left = 0;
            _right = _arr.Length - 1;

            int _rightMax = _arr.Length -1 ;

            int _StandardLeft = 0;
            int _StandardRight = 0;

            int _addLeft = 0;
            int _addRight = 0;

            int _ret = 0;

            while( _left &lt;= (_rightMax * 0.5))
            {
                _StandardLeft = _left;
                _StandardRight= _right;

                _addLeft = 0;
                _addRight = 0;

                bool _isSuccess = false;

                while (_StandardLeft &lt;= (_rightMax* 0.5))
                {
                    _addLeft += _arr[_StandardLeft];

                    if (_addLeft == _m)
                    {
                        ++_ret;
                        _isSuccess = true;
                        break;
                    }
                    else if (_addLeft &gt; _m)
                        break;
                    else
                        ++_StandardLeft;
                }

                if (_isSuccess &amp;&amp; _StandardLeft == _StandardRight)
                {
                    ++_left;
                    --_right;
                    continue;
                }

                while (_StandardRight &gt;= (_rightMax * 0.5))
                {
                    _addRight += _arr[_StandardRight];

                    if (_addRight == _m)
                    {
                        ++_ret;
                        break;
                    }
                    else if (_addRight &gt; _m)
                        break;
                    else
                        --_StandardRight;
                }

                ++_left;
                --_right;
            }

            Console.WriteLine(_ret);
        }
    }
}</code></pre><h3>코드 결과</h3><p>** 질문 게시판의 반례를 모두 통과하였는데 통과하지 못해서 다시 풀 예정이다.</p>

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

코딩테스트 준비 F - 수들의 합 2

🧑‍💻 Develop

<img src="https://image.until.blog/morethanmin/article/1716457407086" alt="until-193"><blockquote><p>react, next.js, solidjs, preact,svelte, vue 등에서 컴포넌트 코드 위치를 손쉽게 찾을 수 있도록 도와주는 extension</p></blockquote><p>최근에 사용해본 크롬 익스텐션 중 신기한 익스텐션이 있어서 공유해보려고 한다...</p><p>본인들의 말에 의하면 <strong>리액트 개발 생산성을 8% 증가</strong> 시킬 수 있다고 한다...</p><p>그것은 바로 locator js... 브라우저에서 특정 영역의 컴포넌트 코드 위치를 찾고자 할때 유용하게 사용할 수 있다.</p><p><a target="_blank" rel="noopener noreferrer nofollow" href="https://www.locatorjs.com/">홈페이지</a>에 가면 설치하지 않고 실제로 사용해볼 수 있으니 궁금하면 가서 사용해보자.</p><h1>사용법</h1><p><a target="_blank" rel="noopener noreferrer nofollow" href="https://chromewebstore.google.com/detail/locatorjs/npbfdllefekhdplbkdigpncggmojpefi">크롬 웹스토어</a>에서 locator js를 설치해주면 설치해주고 홈페이지에 나와있는 <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.locatorjs.com/">가이드</a>를 참고하면 된다.</p><p>본인의 개발환경을 띄우고, 브라우저에서 윈도우에서는 <code spellcheck="false">alt</code> , 맥에서는 <code spellcheck="false">option</code> 을 누르고 특정 영역을 클릭하면 바로 찾아준다.</p><hr><h1>후기</h1><p>근데 devDependency로 설치해줄 만큼 유용한지는 잘 모르겠음</p><p></p>

react, next.js, solidjs, preact,svelte, vue 등에서 컴포넌트 코드 위치를 손쉽게 찾을 수 있도록 도와주는 extension최근에 사용해본 크롬 익스텐션 중 신기한 익스텐션이 있어서 공유해보려고 한다...본인들의 말에 의하면 리액트 개발 생산성을 8% 증가 시킬 수 있다고 한다...그것은 바로 locator js... 브라우