sugyeongkimdev/Algorithm

learn algorithm

learn algorithm

MD작성법
구현

• 프로그래머스
• 백준
  • (BOJ 작동 원리)
  • 삼성 SW 역량 테스트 기출 문제
  • 구현/실버
• 릿코드

알고리즘 공부 방법

• 시리즈:수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초
• VisuAlgo(정렬, 트리 등 원리 시각화)
• 시간 복잡도(Time Complexity)

정렬

• 버블정렬 [ O(n(n-1)/2) ... O(n²) ]
  • 쓰는 이유 : 구현이 '제일' 간단해서, 효율은 최악에 가까움

  void BubbleSort (int[] arr)
  {
      for (int i = 0; i < arr.Length - 1; i++)
      {
          for (int j = 0; j < arr.Length - i - 1; j++)
          {
              if (arr[j] > arr[j + 1])
              {
                  int tmp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = tmp;
              }
          }
      }
  }

• 선택정렬 [ O(n(n-1)/2) ... O(n²) ]
  • 버블정렬보다 조금 더 나은 수준
  • 차라리 버블정렬로 간단하게 구현하던가 다른걸 써야함

  void SelectSort (int[] arr)
  {
      for (int i = 0; i < arr.Length - 1; i++)
      {
          int select = i; // 최소 초기화
          for (int j = i + 1; j < arr.Length; j++)
          {
              // 최소값 선택
              if (arr[j] < arr[select])
              {
                  select = j;
              }
          }
          // i index와 선택된 최소값과 스왑
          int tmp = arr[select];
          arr[select] = arr[i];
          arr[i] = tmp;
      }
  }

    // 2차 배열 상자 90도 회전 (정사각형만 가능)
    int boxSize = 3;
    int[,] box = new int[,]{
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }};
    int[,] rotate90Box = new int[3,3];
    //    7, 4, 1,
    //    8, 5, 2,
    //    9, 6, 3,
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            rotate90Box[i,j] = box[boxSize - j - 1, i];
            Console.Write ($"{rotate90Box[i, j]}, ");
        }
        Console.WriteLine ();
    }

    //    *
    //   ***
    //  *****
    // *******
    //*********
    // *******
    //  *****
    //   ***
    //    *
    int num = 5;
    for (int i = num - 1; i > -num; i--)
    {
        string blank = new string (' ', Math.Abs (i));
        string star = new string ('*', (2 * num) - 1 - (2 * Math.Abs (i)));
        Console.WriteLine (blank + star);
    }

    // 10진법으로 변환 ((n)bit -> (10))
    string str = "ZZZZZ";    // 1111(2) ~ ZZZZ(36)
    int bit = 36;            // 2 ~ 36
    double num = 0;
    for (int i = 0; i < str.Length; i++)
    {
        num += Math.Pow (bit, i) * GetNum (str[i]);
        // or
        // num += num * (bit - 1) + GetNum (str[i]);
    }
    Console.WriteLine (num); // 60466175

    int GetNum (char c)
    {
        return c >= '0' && c <= '9' ? c - '0' : c - 'A' + 10;
    }

    // n진법으로 변환 (10 -> (n)bit)
    int value = "60466175"; // ZZZZZ(36) 10진법 값
    int bit = 36;           // 2 ~ 36
    var sb = new System.Text.StringBuilder ();
    while (value >= b)
    {
        int r = value % bit;
        value /= bit;

        sb.Insert (0, GetChar (r));
    }
    sb.Insert (0, GetChar (value)); 
    Console.WriteLine (sb);  // ZZZZZ

    int GetNum (char c)
    {
        return c >= '0' && c <= '9' ? c - '0' : c - 'A' + 10;
    }