'Algorithm'에 해당되는 글 1건

  1. 2016/03/06 글뻥 Algorithm Test Top 20 practics.
* 유진호님 감사합니다. =)
출처 : http://www.csharpstar.com/top-20-googl ··· tions%2F

알고리즘 문제 Top20개인데, 풀이 결과는 별거 없는데... 용어가.. 좌절스럽습니다.
일단 문제 옮겨 놓고 용어부터 풀어야 겠네요.

1. Given an unsorted array which has a number in the majority (a number appears more than 50% in the array), find that number?
2. How to detect a cycle in singly linked list?
3. How to merge two sorted linked list, write a program in your favorite programming language i.e. Java,C#
4. Write a Program which checks if two Strings are Anagram or not?
5. How to swap two numbers without using a temp variable, write code which is free from Integer overflow?
6. How to find all pairs of elements in an integer array, whose sum is equal to a given number?
7. Write a function to print nth number in Fibonacci series?
8. Write a function to count a total number of set bits in a 32 bit Integer?
9. Write a function to remove duplicate characters from String?
10. How to find the 3rd element from end, in a singly linked, in a single pass?
11. How to calculate factorial using recursion in C#?
12. C# program to check if a number is Armstrong number or not?
13. Algorithm to check if a number is Prime or not?
14. Algorithm to check if a number is Palindrome?
15. Algorithm to find if Array contains duplicates?
16. Write code to reverse a linked list, if you able to do it using loops, try to solve with recursion?
17. How to rotate an array by a given pivot ?
18. How to remove duplicates from a sorted linked list?
19. How to find sum of digits of a number using Recursion?
20. Sorting an Array using Selection Sort

흐미... -_-;; 용어 몰라서 문제 못풀뻔 했네요.
(물론 불러줘야 인터뷰를 볼 수 있겠지만....)

용어정의부터 
* a number in the Majority : 50%이상을 차지하는 수입니다. 
예를 들면, {1,2,3,4,5,2,2,2,2} 에서 2가 Majority 수가 되겠군요. 간단히 Linq로 해결할 수 있을거 같네요.

* cycle in singly linked list 는 순환 연결리스트 같네요.

* Anagram은 이전에서 다뤘던 앞으로 읽어도 뒤로 읽어도 같은 문자입니다.

* Fabonacci 수열이 있네요. 
파보나치 수열은 간단히 예로 들면 0, 1, 1, 2, 3, 5, 8, 13... 과 같이 바로 앞의 숫자와 현재 숫자를 더한 결과입니다.

* Factorial 을 계산하라네요. 팩토리얼은 예를 들어 3i = 3*2*1 = 6 (고딩때 수학이... 으으으)

* 암스트롱 넘버는 의외인데, 찾아보니 153 = 1^3 + 5^3 + 3^3 = 153 처럼 abc = a^n + b^n + c^n = x 로 n은 자릿수입니다.

* Prime number 는 영원한 수학계의 숙제인 자신외에는 나눌 수 있는 수가 없는 소수입니다. 

* Palindrome number는 anagram하고 똑같이 숫자 131, 121,  22, 11 같은 수로 꺼꾸로 읽어도 같은 수가 됩니다. 
만드는 공식은 "처음수+꺼꾸로한수"로 72 + 27 = 99 가 되는 수입니다.

* Selection Sort는 지난 포스팅에서 했던 배열 정렬 방법중 하나인데, 선택정렬이군요. 

1. {1,2,3,4,5,2,2,2,2} 이 주어졌을때 2가 나오면 되는거네요.
static void Main(string[] args)
{
     int[] _x = new int[]{ 1, 2, 4, 6, 5, 2, 2, 2, 2 };
     var query = _x.GroupBy(x => x).Select(x => new { Key = x.Key, count = x.Count() }).ToList(); //Linq로 먼저 Groupby해서 카운트를 구합니다.
     var isMajority = query.Find(x => x.count >= _x.Length / 2); //배열의 길이의 50%가 넘게 차지하는 수를 찾습니다.
     string result = (isMajority == null) ? "Not Found" : isMajority.Key.ToString();
     Console.WriteLine(result);
     Console.ReadLine();
}



2. 싱글 링크드 리스트에서 순환되는 링크드 리스트를 찾으란 말인즉슨 Child node 가 null이 있으면 순환이 아니고, null이 없으면 Loop돈다는 뜻입니다.
따라서, Linked class를 만들어서 확인해보면 되겠네요.

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace TestCode
{
    class Program
    {
        static private Node head;
        static void Main(string[] args)
        {
            List<Node> _LinkedList = new List<Node>();
            MakeLinkedList(ref _LinkedList, 0);
            MakeLinkedList(ref _LinkedList, 1);
            MakeLinkedList(ref _LinkedList, 2);
            MakeLinkedList(ref _LinkedList, 3);

            SetCheck(_LinkedList); //정작 사용하는건 요거 하나 입니다. -_-;;

            MakeLoopList(_LinkedList);

            SetCheck(_LinkedList);
            Console.ReadLine();
        }

        static void SetCheck(List<Node> _LL)
        {
             var result = _LL.Find(a => a.Child == null);
             if (result == null) Console.WriteLine("Loop Linked List : True"); else Console.WriteLine("Loop Linked List : false");
        }

        #region for Make Linked List 
        static void MakeLinkedList(ref List<Node> _LL, int value)
        {
             if (head == null) AddFirst(ref _LL, value);
             else
             {
                Node _node = new Node { value = value, Child = null };
                _LL.Add(_node);
                Node _current = head;
                while (_current.Child != null)
                {
                     _current = _current.Child;
                }
                _current.Child = _node;
             }
        }

        static void AddFirst(ref List<Node> _LL, int value)
        {
            Node _Head = new Node { value = value, Child = null };
            _LL.Add(_Head);
            head = _Head;
        }
        #endregion 

        static void MakeLoopList(List<Node> _LL)
        {
            _LL.Find(a => a.value == 3).Child = head;
        }

        public class Node
        {
            public int value;
            public Node Child;
        }
    }
}



3번은 좀 멘붕이네요. 2개의 Sort된 Linked List를 Merge하라니... OTL... 뭐 암튼 이건 2번 문제 응용으로 Value를 비교하여 Node를 연결하면 해결되지 않을까? 합니다.
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace TestCode
{
    class Program
    {
        static private Node head;
        static void Main(string[] args)
        {
            //Linked list를 먼저 만듭니다.
            List<Node> _LinkedListA = new List<Node>();
            MakeLinkedList(ref _LinkedListA, 0);
            MakeLinkedList(ref _LinkedListA, 1);
            MakeLinkedList(ref _LinkedListA, 2);
            MakeLinkedList(ref _LinkedListA, 3);

            List<Node> _LinkedListB = new List<Node>();
            MakeLinkedList(ref _LinkedListB, 1);
            MakeLinkedList(ref _LinkedListB, 3);
            MakeLinkedList(ref _LinkedListB, 5);
            MakeLinkedList(ref _LinkedListB, 6);
            
            //Merge할 List를 만들고,
            List<Node> _MergeList = new List<Node>();
            //Merge합니다.
            MergeLinkedList(_LinkedListA, _LinkedListB, ref _MergeList);
            Console.ReadLine();
         }

         //하나로 모아서 Sort한 뒤에 LinkedList를 생성합니다.
         static void MergeLinkedList(List<Node> _A, List<Node> _B, ref List<Node> _C)
         {
              ArrayList A = new ArrayList();
              foreach(Node x in _A) A.Add(x.value);
              foreach (Node x in _B) A.Add(x.value);
              A.Sort();
              foreach (int x in A) MakeLinkedList(ref _C, x);
          }

          #region for Make Linked List 
          static void MakeLinkedList(ref List<Node> _LL, int value)
          {
               if (head == null) AddFirst(ref _LL, value);
               else
               {
                   Node _node = new Node { value = value, Child = null };
                   _LL.Add(_node);
                   Node _current = head;
                   while (_current.Child != null)
                   {
                        _current = _current.Child;
                   }
                   _current.Child = _node;
                }
           }

           static void AddFirst(ref List<Node> _LL, int value)
           {
                Node _Head = new Node { value = value, Child = null };
                _LL.Add(_Head);
                head = _Head;
           }
           #endregion 

           static void MakeLoopList(List<Node> _LL)
           {
                _LL.Find(a => a.value == 3).Child = head;
           }

           public class Node
           {
                public int value;
                public Node Child;
           }

    }
}



4. Anagram 문자열 비교는 이전 포스팅 http://www.wolfpack.pe.kr/920 문제 5번과 동일합니다.

5. 2개의 숫자를 바꾸는 것인데, 임시 변수 사용하지말고 하라니 쬐끔 황당하긴하네요.
만약 A=200 이고 B=100이라면 2개 수의 합은 300이 됩니다. 300을 A에 저장해놓고, A에서 B를 빼면 200, 이걸 B에 할당한뒤에 다시 300에서 B를 빼면 100 올ㅋ~
따라서, 공식은 

A = A + B;
B = A - B;
A = A - B;

static void Main(string[] args)
{
    int A = 100;
    int B = 200;
    A = A + B;
    B = A - B;
    A = A - B;
    Console.WriteLine(A.ToString());
    Console.WriteLine(B.ToString());
    Console.ReadLine();
}


6. 쉬운 단어들 조합인데 해석이 제대로 안되서 까다로운 문제네요. 주어진 값이 나올수있는 배열안 2개의 원소 합을 구하라는 건데.. 간단히 TEST CASE를 작성하면,
{1,2,3,4} 라는 배열이 있다면 5가 나오는 합은 1, 4 / 2, 3 입니다. 6이 나오는 합은 2, 4가 되겠지요?
그냥 For 문 노가다입니다.

static void Main(string[] args)
{
    int[] arrayInt = new int[] { 1, 2, 3, 4, 5 };
    Console.WriteLine(SearchElement(arrayInt, 3));
    Console.ReadLine();
}

static bool SearchElement(int[] _arr, int x)
{
    for (int i = 0; i < _arr.Length; i++)
    {
        for (int y = 0; y < _arr.Length; y++)
        {
            if (i == y) continue;
            if (i + y == x) return true;
        }
    }
    return false;
}


7. 파보나치 수열은 위에 용어정의에서 이미 터치하고 왔습니다. 뭐.. 이것도 별건 없습니다. x = n-1 + n-2 단, 0과 1은 그대로 찍어주면 될 일 같습니다.
Arraylist로 간단히 해결가능할 거 같네요.

static void Main(string[] args)
{
    ArrayList _ar = new ArrayList();
    SetFibonacci(_ar, 12);
    foreach (int x in _ar)
    Console.Write(x + " ");
    Console.ReadLine();
}

static void SetFibonacci(ArrayList ar, int x)
{
    for (int i = 0; i < x; i++) {
        if (ar.Count < 1) { ar.Add(i); continue; }
        if (ar.Count < 2) { ar.Add(i); continue; }
        ar.Add((int)ar[i-2] + (int)ar[i-1]);
    }
}


8.번 문제는 32비트 int형의 bit 카운트 하라는 것같습니다. =)
이건 간단하게 10진수를 2진수로 변환하고나서 1의 갯수를 세면 bit 카운트가 됩니다. -_-;; 
static void Main(string[] args)
{
    int x = 512;
    string bit = Convert.ToString(x, 2); //int.MaxValue 로 대체하면 31이 나와야 합니다. 32비트 int형이니까요...
    int cnt = 0;
    for (int i =0; i < bit.Length; i++)
    {
        if (bit[i].ToString() == "1") cnt++;
    }
    Console.WriteLine(cnt);
    Console.ReadLine();
}


9.번은 스트링에서 중복되는 문자열을 제거하는 겁니다. Linq로 간단히 합의 볼 수 있는 수준입죠.
static void Main(string[] args)
{
    string x = "aabcded"; //기대결과값은 abcde
    var result = x.Distinct().ToArray();
    Console.WriteLine(new string(result));
    Console.ReadLine();
}


10번은 끝에서 3번째 Element를 찾는 문제네요. 이제 슬슬 LinkedList는 지겨워 지려합니다. 2번 코드 재활용해서 만들어 볼께요.
그런데 끝은 어떻게 찾느냐? 간단히 child가 null인 녀석을 찾고 그 걸 child로 가지고 있는걸 찾고, 다시 그걸 child로 가진걸 찾고... 3번 반복하면 되겠네요.

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace TestCode
{
    class Program
    {
        static private Node head;
        static void Main(string[] args)
        {
            List<Node> _LinkedList = new List<Node>();
            MakeLinkedList(ref _LinkedList, 0);
            MakeLinkedList(ref _LinkedList, 1);
            MakeLinkedList(ref _LinkedList, 2);
            MakeLinkedList(ref _LinkedList, 3);

             //마지막 노드 찾는건 Lambda 함수로 Child가 null인 걸 찾으면 끝!
            Node LastNode = _LinkedList.Find(x => x.Child == null);
            Node findedNode;
            FindNode(_LinkedList, LastNode, 2, out findedNode);
            Console.Write(findedNode.value);
            Console.ReadLine();
        }

         //여기서 재귀함수 Recursive 로 돌려주면서 1씩 까나갑니다.
        static void FindNode(List<Node> LL, Node current, int n, out Node finded)
        {
            if (n == 0) { finded = current; return; }
            Node parent = LL.Find(x => x.Child == current);
            FindNode(LL, parent, n - 1, out finded);
        }

#region for Make Linked List 
static void MakeLinkedList(ref List<Node> _LL, int value)
{
if (head == null) AddFirst(ref _LL, value);
else
{
Node _node = new Node { value = value, Child = null };
_LL.Add(_node);
Node _current = head;
while (_current.Child != null)
{
_current = _current.Child;
}
_current.Child = _node;
}
}

static void AddFirst(ref List<Node> _LL, int value)
{
Node _Head = new Node { value = value, Child = null };
_LL.Add(_Head);
head = _Head;
}
#endregion

        static void MakeLoopList(List<Node> _LL)
        {
            _LL.Find(a => a.value == 3).Child = head;
        }

        public class Node
        {
            public int value;
            public Node Child;
        }
    }
}



11번 문제는 재귀함수로 팩토리얼 구하는 문제입니다. 3i이라면 3*2*1 = 6 이 나오면 되는 문제입니다.

static void Main(string[] args)
{
    Console.WriteLine(Factorial(4));
    Console.ReadLine();
}

static int Factorial(int x)
{
    if (x == 1) return x;
    return Factorial(x - 1) * x;
}



12번 문제는 암스트롱 수가 맞는지 확인하는거 같네요. 공식을 대입하면 abc = a^n + b^n + c^n = abc 가 나와야 합니다.
따라서, 입력한 값을 위 공식을 적용해서 테스트해보고 비교하면 올ㅋ~

static void Main(string[] args)
{
    Console.WriteLine(GetCalator(154));
    Console.ReadLine();
}

static bool GetCalator(int x)
{
    //자르기 편하게 string으로 변환부터
    string _x = x.ToString();
    //자릿수 n을 구합니다.
    int n = _x.Length;
    double y = 0;
    for (int i = 0; i < n; i++)
    {
        //C#은 C처럼 ^연산자는 2진수 계산을 하는군요. VB는 그냥 제곱인데.. 쩝..
        y += Math.Pow(int.Parse( _x[i].ToString()), n);
    }
    if (x == y) return true;
    return false;
}



13번 문제는 수학계의 영원한 숙제인 소수찾기입니다. 소수는 자기외에 나눌수 없는 성질을 가지고 있기 때문에 테스트 케이스를 작성하면,
1 소수
2 소수
3 소수
4 소수아님 (4%2==0)
5 소수 

1을 제외하면 for문으로 주어진 2~n-1까지 수로 나눠서, 그과정에서 나머지가 없으면 소수가 아닌걸로 판정하면 올ㅋ

static void Main(string[] args)
{
    Console.WriteLine(isPrime(7));
    Console.ReadLine();
}

static bool isPrime(int x)
{
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0) return false;
    }
    return true;
}


14번 문제는 이전 포스팅에서 아나그람으로 다뤘지만, 조금 다른방식으로 처리해보면, Array.Reserve로 뒤집어 놓고 비교하면 더 간단하겠네요. =)

static void Main(string[] args)
{
    Console.WriteLine(isPalindrome(78));
    Console.ReadLine();
}

static bool isPalindrome(int x)
{
    char[] _x = x.ToString().ToCharArray();
    Array.Reverse(_x);
    if (x.ToString() == new string(_x)) return true;
    return false;
}



15번은 배열안에 중복되는 인자가 있는지 확인하는건데 이것도 걍 Linq한방이면 되겠네요! (1번 문제 응용이네요)
static void Main(string[] args)
{
    int[] _array = new int[] { 1, 2, 3, 3, 5 };
    var result = _array.GroupBy(x => x).Select(x => new { key = x.Key, count = x.Count() }).ToList();
    if (result.Find(x=>x.count >= 2) == null) Console.WriteLine("cant find Duplicated element");
    else Console.WriteLine("Find Duplicated element");
    Console.ReadLine();
}



16번은... 양키 형님들은 진짜 Linked List를 사랑하는거 같아요. -_-;; 
Linked List를 가능하다면 재귀함수 써서 뒤집으라 하십니다. 2번 소스 응용해서 만들어 보겠습니다.

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace TestCode
{
    class Program
    {
        static private Node head;
        static void Main(string[] args)
        {
            List<Node> _LinkedList = new List<Node>();
            MakeLinkedList(_LinkedList, 0);
            MakeLinkedList(_LinkedList, 1);
            MakeLinkedList(_LinkedList, 2);
            MakeLinkedList(_LinkedList, 3);

            List<Node> _ReservedList = new List<Node>();

            SetReserve(_LinkedList, _ReservedList, _LinkedList.Count()-1);
            foreach (Node v in _ReservedList)
            {
                 Console.WriteLine(v.value);
            }

            Console.ReadLine();
         }

         static void SetReserve(List<Node> linked, List<Node> Reserved, int idx)
         {
              if (idx < 0) return;
              MakeLinkedList(Reserved, linked[idx].value);
              SetReserve(linked, Reserved, idx-1);
         }


#region for Make Linked List 
static void MakeLinkedList(List<Node> _LL, int value)
{
if (head == null) AddFirst(ref _LL, value);
else
{
Node _node = new Node { value = value, Child = null };
_LL.Add(_node);
Node _current = head;
while (_current.Child != null)
{
_current = _current.Child;
}
_current.Child = _node;
}
}

static void AddFirst(ref List<Node> _LL, int value)
{
Node _Head = new Node { value = value, Child = null };
_LL.Add(_Head);
head = _Head;
}
#endregion 

      public class Node
      {
           public int value;
           public Node Child;
      }
   }
}


17번 문제는 의미를 몰라서 뒤져봤습니다.
찾아 봤더니 다른 의미가 아니라, 테스트 케이스로 보면, {1,2,3,4,5}라는 배열이 있다면, 3을 주면,
-1번-> {2,3,4,5,1} -2번-> {3,4,5,1,2} -3번-> {4,5,1,2,3}
결국 {4,5,1,2,3}이 나와야 하는거네요. 이건 string으로 변환해서 맨 앞에 녀석을 뒤로 가져다 붙이기를 몇번 하느냐 하는 문제 같군요!

* 그런데, 이거 예전에 한 20여년 전에 테트리스 블록 회전하기 했었을때 알고리즘 같은데.. 풀이는 좀 다르게 되어 있네요. 뭐 암튼 재귀함수와 ref 로 간단히 해결됩니다.
(C는 포인터로...)

static void Main(string[] args)
{
    int[] _array = new int[] { 1, 2, 3, 4, 5 };
    SetPivot(ref _array, 3);
    Console.ReadLine();
}

static void SetPivot(ref int[] _arr, int cnt)
{
    if (cnt < 1) return;
    int[] _cpyarray = new int[_arr.Length];
    int tmp = _arr[0];
    for (int i = 1; i < _arr.Length; i++)
    {
         _cpyarray[i - 1] = _arr[i];
    }
    _cpyarray[_arr.Length-1] = tmp;
    _arr = _cpyarray;
    SetPivot(ref _arr, cnt - 1);
}



18. 중복되는 Linked list 값을 제거하랍니다. 
Linked list merge소스를 조금 응용하면 되겠네요.

 class Program
 {
    static private Node head;
     static void Main(string[] args)
     {
        List<Node> _LinkedListA = new List<Node>();
         MakeLinkedList(ref _LinkedListA, 0);
         MakeLinkedList(ref _LinkedListA, 1);
         MakeLinkedList(ref _LinkedListA, 2);
         MakeLinkedList(ref _LinkedListA, 3);
         MakeLinkedList(ref _LinkedListA, 2);

         //Merge할 List를 만들고,
         List<Node> _UniqueList = new List<Node>();
         //Merge합니다.
         RemoveDuplicatedLinkedList(_LinkedListA, ref _UniqueList);
         Console.ReadLine();
    }

         //하나로 모아서 Sort한 뒤에 LinkedList를 생성합니다.
    static void RemoveDuplicatedLinkedList(List<Node> _A, ref List<Node> _C)
    {
         ArrayList A = new ArrayList();
         foreach (Node x in _A) A.Add(x.value);
         var _x = A.ToArray().Distinct().ToArray();
         foreach (int x in _x) MakeLinkedList(ref _C, x);
    }

 #region for Make Linked List 
 static void MakeLinkedList(ref List<Node> _LL, int value)
 {
 if (head == null) AddFirst(ref _LL, value);
 else
 {
 Node _node = new Node { value = value, Child = null };
 _LL.Add(_node);
 Node _current = head;
 while (_current.Child != null)
 {
 _current = _current.Child;
 }
 _current.Child = _node;
 }
 }

 static void AddFirst(ref List<Node> _LL, int value)
 {
 Node _Head = new Node { value = value, Child = null };
 _LL.Add(_Head);
 head = _Head;
 }
 #endregion

    static void MakeLoopList(List<Node> _LL)
    {
        _LL.Find(a => a.value == 3).Child = head;
    }

    public class Node
   {
        public int value;
        public Node Child;
    }
}



19. digits of the number 의 합을 재귀함수로 구하라고 하는건데, 말이 어렵네요... 간단하게 테스트 케이스를 만들어 보면 123 => 6 다시 말해 자릿수에 있는 0~9까지의 수를 다 더하란 이야기 입니다.
static void Main(string[] args)
{
    int x = 158; //14가 나와야 함.
    int result = 0;
    GetSum(x, ref result, x.ToString().Length - 1);
    Console.WriteLine(result);
    Console.ReadLine();
}

static void GetSum(int _x, ref int _result, int _digit)
{
    if (_digit >= 0)
    {
        _result = _result + int.Parse(_x.ToString().ToCharArray()[_digit].ToString());
        GetSum(_x, ref _result, _digit - 1);
    }
}


20. 마지막문제는 선택정렬하라 입니다.
지난번 포스팅에서 버블소트 다뤘는데, 선택정렬의 테스트 케이스는 다음과 같습니다.
{9,2,5,1,4,6} 가 있다면 n+1~m까지 중에 가장 작은 수를 찾아 비교한후 뒤에 숫자가 더 작다면 Swap합니다.
2번째 루프에서는 2번째 자리의 수를 기준으로 n+2~m까지 수중 가장 작은 수와 비교합니다.
버블소트가 마구마구 치환하는데 비해 이건 선택한 자리수의 수를 가지고 비교하기입니다.

static void Main(string[] args)
{
    int[] x = new int[]{ 9, 2, 5, 1, 4, 6 };
    foreach(int i in SetSort(x))
        Console.WriteLine(i);
    Console.ReadLine();
}

static int[] SetSort(int[] _x)
{
    for (int i = 0; i < _x.Length; i++)
    {
        for (int j = i+1; j < _x.Length; j++)
        {
            if (_x[i] > _x[j])
            {
                _x[i] = _x[i] + _x[j];
                _x[j] = _x[i] - _x[j];
                _x[i] = _x[i] - _x[j];
            }
        }
     }
     return _x;
}



2016/03/06 20:58 2016/03/06 20:58