'자료구조'에 해당되는 글 2건

  1. 2016/03/02 글뻥 Algorithm practice
  2. 2007/04/02 글뻥 자료구조에 대해
C# 알고리즘 연습용입니다.

문제1. 임의의 문자열을 입력받아 유일한지 검사하라.
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace TestCode
{
    class Program
    {
        static Hashtable _UniqueTable;

        static void Main(string[] args)
        {

            string _InputString = Console.ReadLine();
            _UniqueTable = new Hashtable();

            for (int i=0; i < _InputString.Length; i++)
            {
                AddTable(_InputString[i]);
            }
            CheckTable();
            Console.ReadLine();
        }

        static void AddTable(char _x)
        {
            if (_UniqueTable != null && _UniqueTable.Contains(_x))
                _UniqueTable[_x] = (int)_UniqueTable[_x] + 1;
            else
                _UniqueTable.Add(_x, 1);
        }

        static void CheckTable()
        {
            foreach (DictionaryEntry _dt in _UniqueTable)
            {
                if ((int)_dt.Value > 1) Console.WriteLine("Error! No unique key found! {0}, Count {1}", _dt.Key, _dt.Value);
            }

        }
    }
}


결과는 Count가 2개 이상인 경우 문자메시지를 출력합니다.

Crack
1. 입력받은 문자열을 Char로 변환하여 HashTable에 넣는게 관건.
2. 이때 중복되는 키가 있으면 Value증가시킴
3. 중복되는 키가 없으면 Add시킴
4. 모든 입력과정 종료후 DictionaryEntry형으로 변환하여 Foreach날림

만약 C#의 Linq를 사용한다면 더 짧게 코딩이 가능합니다.
        static void Main(string[] args)
        {
            string InputString = "cvdss";
            Console.WriteLine(GetSameUniqueText(InputString).ToString());
            Console.ReadLine();
        }

        static bool GetSameUniqueText(string _x)
        {
            char[] ArrayChar = _x.ToCharArray();
            Array.Sort(ArrayChar);
            var Result = (from x in ArrayChar select x).Distinct().OrderBy(x => x).ToArray();
            if (new string(ArrayChar) == new string(Result)) return true;
            return false;
        }



문제2. 임의의 문자열을 받아서 역순으로 배열하여 출력하라.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            string _TempString = "";
            string _InputString = Console.ReadLine();

            for (int i= _InputString.Length; i > 0; i--)
            {
                _TempString += _InputString[i-1];
            }
            Console.WriteLine(_TempString);
            Console.ReadLine();
        }

    }
}


Crack. 이건 간단해서 패스...
만약 C#이라면 역시 Linq로...
        static void Main(string[] args)
        {
            string InputString = "cvdss";
            Console.WriteLine(SetReverse(InputString));
            Console.ReadLine();
        }

        static string SetReverse(string _x)
        {
            char[] ArrayChar = _x.ToCharArray();
            var Result = (from x in ArrayChar select x).Reverse().ToArray();
            return new string(Result);
        }



문제3. 임의의 문자열을 입력받아 공백을 %20으로 교체하라.
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            string _InputString = Console.ReadLine();
            Console.WriteLine(_InputString.Replace(" ", "%20"));
            Console.ReadLine();
        }
    }
}


Crack : 이것도 간단해서 생략

문제4. 반복되는 임의의 문자열 예를 들어 "aaaabbbccaa"를 입력받으면 "a4b3c2a2"로 압축하라.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            char _OldChar = '\x0000';
            string _OutputStr = "";
            string _InputString = Console.ReadLine();

            int _count = 0;
            for (int i = 0; i < _InputString.Length; i++)
            {
                char _NewChar = _InputString[i];
                if (_NewChar == _OldChar) {
                    if (_count < 2) _OutputStr += _NewChar.ToString();
                    _count++;
                } 
                else
                {
                    if (_count > 0) _OutputStr += _count.ToString();
                    _OldChar = _NewChar;
                    _count = 1;
                }
            }

            Console.WriteLine(_OutputStr + _count.ToString());
            Console.ReadLine();
        }
    }
}


Crack : 이것도 간단해서 패스

문제5. 앞으로 읽어도 뒤로 읽어도 똑같은 문자열인지 Bool값으로 리턴하라. 단, Letter만 확인하라.
using System;
using System.Text.RegularExpressions;

public class Palindrome
{
     public static bool IsPalindrome(string str) {
          //먼저 소문자로 치환하고 특수문자는 제거합니다.
          string _x = JustLetter(str);
          //만약 3글자라면 1번만, 4글자라면 2번만 루프돌면서 가운데를 기준으로 대칭에 있는 문자열을 비교합니다.
          //만약 틀리면 false 를 리턴하고 빠집니다.
           int lastidx = _x.Length - 1;
           for (int i = 0; i < _x.Length / 2; i++){
                     if (_x[i] != _x[lastidx]) return false;
                     lastidx--;
           }
          //아무런 문제가 없으면 true;
           return true;
     }

     public static string JustLetter(string _str)
     {
           string _x = "";
           string returnVal = _str.ToLower();
           string pattern = @"[a-z]";

          //요부분이 좀 애먹은 부분인데 C#의 정규표현식으로 MatchCollection을 만든다음에 한글자씩 따는 부분입니다.
           MatchCollection matches = Regex.Matches(returnVal, pattern);
           foreach (Match match in matches)
                     _x += match.Value;
           return _x;
      }

     public static void Main(string[] args)
     {
           Console.WriteLine(IsPalindrome("Level."));
     }
}


Crack.
1. 글자를 비교할 수 있도록 표준화하는게 관건
   - 소문자로 만들기
   - 특수문자제거
2. 처음과 끝에서 부터 한단계씩 비교

문제 6. momdad와 dadmon은 단어의 순서가 바뀐 문자열이다. 이처럼 순서가 바뀐 단어가 있으면 true, 아니라면 false를 반환하라.

using System;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        if (CharSort(a) == CharSort(b)) return true;
        return false;
    }
    
    public static string CharSort(string _x)
    {
        char[] x = _x.ToCharArray();
        Array.Sort(x);
        return new string(x);
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}


Crack.
1. 두개의 단어가 정확하게 쓰여졌다는 가정하에 2개의 문자열을 Char로 치환후 Sort하면 동일한 결과를 얻을 수 있어야 합니다.
2. 따라서, string을 char로 변환후 sort해서 비교하는 루틴으로 간단하게 처리됩니다.


*문제7. Linked list Class를 만들고 특정 문자열을 지우면 나머지 단계도 삭제되는 루틴을 만드시오.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
 
namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            List<NodeClass> _LinkedNode = new List<NodeClass>();
            SetNode(_LinkedNode);
            #region For Debug (Input data check)
            //foreach (NodeClass _n in _LinkedNode)
            //    Console.WriteLine("Parent:{0}, Value:{1}",_n._Parent, _n._value);
            #endregion
 
            RemoveValue(_LinkedNode, "A");
 
            #region For Debug (Input data check)
            foreach (NodeClass _n in _LinkedNode)
                Console.WriteLine("Parent:{0}, Value:{1}", _n._Parent, _n._value);
            #endregion
            Console.ReadLine();
        }
 
        static void SetNode(List<NodeClass> _LinkedNode)
        {
            string[] _Values = new string[] { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J" };
            foreach (string _value in _Values)
                _LinkedNode.Add(new NodeClass
                {
                    _Parent =
                    ((_value == "B") ? "A" :
                    (_value == "C") ? "A" :
                    (_value == "D") ? "A" :
                    (_value == "E") ? "B" :
                    (_value == "F") ? "C" :
                    (_value == "G") ? "C" :
                    (_value == "H") ? "D" :
                    (_value == "I") ? "F" :
                    (_value == "J") ? "F" :
                    ""),
                    _value = _value
                });
 
        }
        static void RemoveValue(List<NodeClass> _LinkedNode, string _X)
        {
            foreach (NodeClass _n in _LinkedNode)
            {
                if (_n._value == _X) _n._value = "";
                if (_n._Parent == _X) RemoveValue(_LinkedNode, _n._value);  
            }
        }
    }
 
    public class NodeClass
    {
        public string _Parent { get; set; }
        public string _value { get; set; }
    }
 
}


Crack.
1. 클래스 생성은 Parent와 value구조만 있으면 문제가 없습니다. 만약 node 탐색이 들어간다면 또 다른 이야기가 되겠지만, 현재 Tree구조로는 해당 문제를 푸는데 문제없습니다.
2. 먼저 노드를 생성합니다. SetNode
3. 임의의 문자를 입력하여 하위 노드를 삭제합니다. 이때 재귀함수 (Recursion Function)을 사용해서 하위레벨도 삭제되도록 합니다.

추가로 노드를 삭제하려면 아래의 메소드를 호출해주면 되겠습니다.
static void TruncItem(ref List<NodeClass> _LinkedNode) {
     _LinkedNode = _LinkedNode.FindAll(x => x._value != "");
}
ref 키워드이니까, 당연히 TruncItem(ref _LinkNode); 로 호출해야 겠죠?


문제8. 임의의 배열이 주어졌을때 이를 Sort하라.

using System;
using System.Linq;

namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arrays = new int[] { 1, 5, 6, 2, 4, 7, 9 };
            for (int i = 0; i < arrays.Count(); i++)
            {
                for (int y = 0; y < arrays.Count() - 1; y++)
                {
                    if (arrays[y] <= arrays[y + 1]) continue;
                    int x = arrays[y];
                    arrays[y] = arrays[y + 1];
                    arrays[y + 1] = x;
                }
            }

            foreach (int z in arrays)
                Console.WriteLine(z);
            Console.ReadLine();
        }
    }
}


Crack.
1. 간단한 Bubble sort입니다.
2. x개의 원소가 주어졌을 때, 총 x * (x-1)번의 Loop를 돌면서 맨 앞에서부터 차례로 데이터를 Swap 합니다.

보다 C#에 가깝게 고치면 ref 키워드를 사용해서 값 참조합니다.
using System;
using System.Linq;

namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arrays = new int[] { 1, 5, 6, 2, 4, 7, 9 };
            for (int i = 0; i < arrays.Count(); i++)
            {
                for (int y = 0; y < arrays.Count() - 1; y++)
                {
                    if (arrays[y] <= arrays[y + 1]) continue;
                    SwapInt(ref arrays[y], ref arrays[y + 1]);
                }
            }
            foreach (int z in arrays)
                Console.WriteLine(z);
            Console.ReadLine();
        }

        public static void SwapInt(ref int _x, ref int _y)
        {
            int x = _x;
            _x = _y;
            _y = x;
        }
    }
}


ref 키워드와 비슷한 녀석이 out 키워드인데, ref는 반드시 선언되고 정의되어야 하지만, out은 선언만 되면 사용이 가능합니다.
만약, 여러개의 인자를 한번에 정의하려면 out 키워드가 더 적합합니다.
using System;

namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            string a, b;
            SetString(out a, out b);

            Console.WriteLine(a);
            Console.ReadLine();
        }

        static void SetString(out string x, out string y)
        {
            x = "A";
            y = "B";
        }
    }
}


하지만, 역시 Just C#이라면....
        static void Main(string[] args)
        {
            int[] arrays = new int[] { 1, 5, 6, 2, 4, 7, 9 };
            Array.Sort(arrays);
            foreach (int _x in arrays) {
                Console.WriteLine(_x.ToString());
            }
            Console.ReadLine();
        }

역순으로 Sort하는건, Sort 한뒤에 Method 하나더 불러줍니다.
 Array.Sort(arrays);
 Array.Reverse(arrays); //추가


문제 9.abcdefg 라는 문자열이 주어졌을때 n = 4 라고 할때
a c e g 
b d f
로 출력하시오.
Crack First. 이건 순열 문제로 문제의 의도를 파악하기 힘들군요. 만약 피시험자였다면 출제자에게 더 자세히 물어봤겠지만, 인터넷에 있는 후기를 퍼온 덕에 추가 정보를 얻을 수 없습니다만. 일단 기대값을 볼때 2자리마다 끝어서 출력하면 되지 않을까 싶네요.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 4;
            string InputStr = "abcdefg";
            string[] Row = new string[2];

            char[] ArrayChar = InputStr.ToCharArray();

            int indexNum = 0;
            foreach (char c in ArrayChar)
            {
                if (indexNum % (n / 2) == 0) Row[0] += ArrayChar[indexNum];
                else Row[1] += ArrayChar[indexNum];
                indexNum++;
            }

            foreach (string s in Row)
            {
                Console.WriteLine(s);
            }

            Console.ReadLine();
        }
    }
}





문제 10. 예를들어 ccbbdddbcccaabbaaeeefff 가 주어졌을때 -> cbdaef 처음으로 등장한 알파벳만 모아서 보여주시오. 
using System;
using System.Linq;

namespace TestCode
{
     class Program
     {
          static void Main(string[] args)
          {
               string _x = "ccbbdddbcccaabbaaeeefff";
               char[] _arrChar = _x.ToCharArray();
               var query = (from x in _arrChar select x).Distinct().ToArray();
               Console.WriteLine(new string(query));
               Console.ReadLine();
          }
     }
}


Crack. 

간단한 Linq 문제입니다. =)



문제 11. 2개의 임의의 배열이 주어졌을때, Merge하고 Sort하라 

using System;
using System.Linq;

namespace TestCode
{
     class Program
     {
          static void Main(string[] args)
          {
               int[] One = new int[] { 1, 4, 6, 3, 9 };
               int[] Two = new int[] { 8, 2, 5 };
               int[] Merge = new int[One.Count() + Two.Count()];

               SetMerge(ref One, ref Two, ref Merge);
               Array.Sort(Merge);

               foreach(int x in Merge)
               {
                    Console.WriteLine(x);
               }
               Console.ReadLine();
          }

          static void SetMerge (ref int[] _x, ref int[] _y, ref int[] Result)
          {
               int MergeIdx = 0;
               for (int i = 0; i < _x.Count(); i++)
               {
                    Result[MergeIdx] = _x[i];
                    MergeIdx++;
                }
                for (int i = 0; i < _y.Count(); i++)
                {
                    Result[MergeIdx] = _y[i];
                    MergeIdx++;
                }
           }
     }
}

Crack. 
전통적인 방법으로는 위와 같이 배열 2개를 합한 크기의 배열을 만들고 For문 2번 돌려서 합치겠지만, C# 이라는 Linq가 있습니다.

using System;
using System.Linq;

namespace TestCode
{
     class Program
     {
          static void Main(string[] args)
          {
               int[] One = new int[] { 1, 4, 6, 3, 9 };
               int[] Two = new int[] { 8, 2, 5 };
               int[] Merge = new int[One.Count() + Two.Count()];

               SetMerge(ref One, ref Two, ref Merge);

               foreach (int x in Merge)
               {
                    Console.WriteLine(x);
               }
               Console.ReadLine();
           }

          static void SetMerge (ref int[] _x, ref int[] _y, ref int[] Result)
          {
               Result = _x.Concat(_y).OrderBy(x => x).ToArray(); //바로 이렇게 한방에 처리항 수 있습니다.
          }
     }
}



문제 12. 사용자 input 을 문자열로 받아서 숫자로 인식하는 프로그램을 만들어라.input에는 어떤 문자든지 올 수 있고, 어떤 규칙까지 허용하고 어떤 숫자까지 지원할지는 자유이다. 
Crack.
실제 MS사에서 면접 보신분의 후기에서 가져온 문제입니다. 이 경우 저라면 Hash 테이블에 단어장을 먼저 만들겠습니다.
먼저 필요한 테이블은 숫자만 카운팅 하는 테이블
1-one, 2-two, 3-three, 4-four, 5-five, 6-six, 7-seven, 8-eight, 9-nine, 10- ten, 11- eleven, 12-twelve, 13-thirteen, 14-fouteen, 15-fivteen .... 999-ninehundredniteennine
그리고 자릿수 3자리씩 잘라서 인식할 테이블을 만듭니다.
1000-thousand, 1000000-million, 1000000000-billion, 1000000000000-trillion
linq lambda 식으로 조회합니다.

//코드는 나중에 정리 예정.



문제 13.  두번째 문제는 Binary Tree가 있다고 가정하고 그 트리에 있는 숫자를 root에서 leaf까지 해서 도달하는 숫자의 합을 구하시오.
1
/ \
2  3
/\ /
4 5 6
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace TestCode
{
     class Program
     {
          static void Main(string[] args)
          {
               BinaryTree<int> broot = new BinaryTree<int>();
               broot.Root = new Node<int>(1);
               broot.Root.LNode = new Node<int>(2);
               broot.Root.RNode = new Node<int>(3);
               broot.Root.LNode.LNode = new Node<int>(4);
               broot.Root.LNode.RNode = new Node<int>(5);
               broot.Root.RNode.LNode = new Node<int>(6);

               ArrayList result = new ArrayList();
               broot.PrintNodeValue(broot.Root, 0, ref result);

               foreach (int i in result)
               {
                     Console.WriteLine(i);
               }

                Console.ReadLine();
           }
     }

      public class Node<T>
     {
          public Node<T> LNode;
          public Node<T> RNode;
          public int Value;
          public Node(int data)
          {
                this.Value = data;
          }
     }

     public class BinaryTree<T>
     {
          public Node<T> Root;
          public void PrintNodeValue(Node<T> node, int ParentValue, ref ArrayList result)
          {
                if (node.LNode != null) PrintNodeValue(node.LNode, node.Value + ParentValue, ref result);
                if (node.RNode != null) PrintNodeValue(node.RNode, node.Value + ParentValue, ref result);
                if (node.LNode == null && node.RNode == null)
                {
                     result.Add(node.Value + ParentValue);
                }
          }
     }
}


Crack.
2진트리는 1개의 노드가 최대 2개의 자식 노드를 가진 트리형입니다.
반듯이 왼쪽부터 채워져야 하는 규칙을 가지고 있지요.
아마도 이 문제 응용문제로 2진 트리에서 공통 조상을 찾아라 든가... 혹은 2진트리를 반전 시켜라와 2진트리 Leaf를 찾아라와 같은 응용 문제가 있을 수 있습니다.
중요한건 재귀함수를 쓸 줄 아느냐 일것 같은데, C#에서는 2진트리 쓸일이 사실 별로 없어서... 쿨럭...
2016/03/02 17:11 2016/03/02 17:11

자료구조라고 하면 어렵게 생각하는 분들이 꽤나 있는데 사실 어려운 개념이 아니다.
프로그래밍하면서 자료구조에 대해 살펴보는것도 나쁘지 않을것 같아 정리하니 행여나 자료구조론에 대해 공부하지 않더라도 알고는 넘어가도록 해야 나중에 Core 프로그래밍할때 개고생 하지 않는다.

자료구조를 한마디로 정의하자면 "데이터를 사용하는 방법"이라 하겠다.
어떻게 저장하고 어떻게 꺼내쓰느냐의 문제란 것이다.

먼저 메모리쪽의 자료구조를 보면 딱! 2개밖에 없다.
바로 Stack(스택)과 Heap(힙)
고정된 크기를 사용하는 것이 스택. 가변된 크기를 사용하는 것이 힙이다.

예를 들어 "int"형으로 선언한 변수와 같이 가변되지 않고 크기가 고정된 다시말해 -2,147,
483,648~2,147,483,648의 값을 가진것으로 고정된 변수는 스택영역을 사용한다.
또한 같은 고정된 변수를 저장하는 곳이 스택이다.
따라서 Heap과 비교하여 작은 크기로 존재하며 먼저 집어 넣은 놈보다 나중에 집어 넣은 놈을 먼저 가져올 수 있는 구조이다.

1step : [A] - A를 입력
2step : [A] [B] - B를 입력
3step : [A] [B] [C] - C를 입력
4step : [A] [B] - C를 출력

그러나 "string"과 같이 크기가 null이 될수도 있고 "abcdef"와 같이 6byte가 될 수도 있는 가변형의 자료는 어떻게 하는가? 이경우는 Heap이라는 자유메모리 공간에 저장되어 마음대로 썼다 지웠다 꺼냈다 한다. 따라서 상대적으로 많은 공간을 잡아둔 공간이다.
정해진 순서대로 처리되는 스택과 달리 힙은 마음대로 썼다(new) 지웠다(delete, dispose) 할 수 있다. 물론 이렇게 막 썼다고 지우기를 반복하면 공간의 빈틈이 생겨 비효율적인 동작을 하게되는데 (디스크 조각처럼 쪼각쪼각 나면 찾기 힘들어지고 링크를 사용하므로 메모리도 비효율적이 되는 원리) 이럴때 사용하라고 있는것이 가베지컬렉터(GC)이다.
뭐 암튼 IBM호환 PC는 모두 이런 구조로 되어 있다.

여기서 부터 출발하자.
프로그램밍에서는 스택, 연결고리, 큐 등으로 알고리즘과 함께 자료구조에 대해 설명하고 있는데 그냥 있는그대로 받아 들이면

스택은 위에서 설명한 방식대로 나중에 저장한넘부터 꺼내서 사용하는 구조이고

큐는 스택과 반대 개념이다. 먼저 집어 넣은놈을 먼저 실행한다.
1step : [A] - A를 입력
2step : [A] [B] - B를 입력
3step : [A] [B] [C] - C를 입력
4step : [B] [C] - A를 출력

연결고리는
[데이터|연결고리] [데이터|연결고리] [데이터|연결고리]... 순서로 되어 있는 구조이다.
데이터가 써지고나서 연결되는 데이터가 어디에 있는지 연결고리에 기록한후 그 지점에 계속해서 데이터를 써나가는 구조이다.
검색 중간에 자료를 쓰거나 지우는 것이 가능한 구조 되겠다. 그러나 길면 길수록 실행시간이 길어지는 단점이 있다.

이외에도 흔히 사용하는 노드구조도 있다.
Root - A - A1
             - A2
       - B - B1
             - B2
탐색기에서 많이 본 구조 ^^;;

2007/04/02 18:15 2007/04/02 18:15