눈물보다 땀을

문제

 피보나치 수열 중 각 자리의 숫자를 더한 수로 나누어 떨어지는 수를 다음 예에 이어 작은 쪽부터 5개 구해보세요.

 예)

   2 > 2/2

   3 > 3/3

   5 > 5/5

   8 > 8/8

   13 > 13/4  x

   21 > 21/3

   144 > 144/9

난이도

IQ 85

목표시간

20분

풀이(c#,VS)

1. 

using System;

namespace _11_Fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            long num1 = 1;
            long num2 = 2;
            for(long i =0; i<1000; i++)
            {
                //피보나치 수 구하기
                long pbNum;
                pbNum = num1 + num2;

                num1 = num2;
                num2 = pbNum;

                //자릿수 구하기
                long tempPbNum = pbNum;
                long sumNumLen = 0;
                do
                {
                    sumNumLen+= (long)(tempPbNum % 10);
                    tempPbNum = (long)(tempPbNum / 10);
                } while (tempPbNum > 0);
                   
                //자릿수 합으로 나누었을때 떨어지는 숫자 구하기
                if(pbNum%sumNumLen == 0f)
                {
                    Console.WriteLine(pbNum + "/" + sumNumLen);
                }

                
            }
        }
    }
}

문제정답(사용언어:python)

1.

a=b=1
count = 0
while count<11:
    c = a+b
    # 1자리씩으로 분할하여 각 자리의 합을 취득
    sum =0
    for e in str(c):
        sum +=int(e)
    if c%sum == 0:
        #나누어 떨어지면 출력
        print(c)
        count += 1
    a,b,=b,c

-

재귀를 이용해서 문제를 풀지 않았지만 책에서는 재귀를 이용하면 자칫 stackoverflow에 빠질 수 있다고 한다. 재귀가 끝나는 시점까지 호출 메소드관련 메모리가 스택에 계속 살아 있어야 되기 때문인것 같다. 간단하고 작은 수를 다룰 때는 재귀 나름의 장점이 있지면 역시 재귀는 쓰기전에 고려해볼 점이 많은것 같다.

문제

 남자 20명, 여자 10명이 도착하였을 때 어디에서 끊더라도 두 그룹 모두 남자와 여자의 수가 달라지게 되는 도착 순서가 몇 가지 있는지 구해 보세요.

난이도

IQ 80

목표시간

20분

풀이(c#,VS)

1. 재귀를 이용하여 풀이

남성 10, 여성 5명, 남성 가로축, 여성 세로축 이라고 가정 했을때  - 부분을 지나지 않고 도착 경로에 도착할 수 있는 가짓수를 찾으면 된다.

/*
20200204
ksj
*/ 
using System;

namespace _9_MaleFemaleUnBalance
{
    class Program
    {
        static void Main(string[] args)
        {
            int cnt = 0;
            Move(1, 0, 0, ref cnt);
            //처음 위칸으로 이동하면 (여자가 먼저 도착하면) 절대로 타겟 경로로 이동할 수없다.
            //Move(-1, 0, 0, ref cnt);   // 이때 cnt는 0이다.

            Console.WriteLine(cnt);
        }

        static void Move(int dir, int x, int y, ref int cnt)
        {
            //dir  1 오른쪽한칸 x++
            //dir  -1 위쪽한칸 y++
            if (dir == 1)
            {
                x++;
            }
            else
            {
                y++;
            }
                        
            if ((x == y) ||( (x-10) == y) || x > 20 || y > 10)  //범위 벗어나거나 여자 남자 수가 같아지는 지점
            {
                return;
            }
            else if ((x == 19 && y == 10) || (x == 20 && y == 9)) //도착지
            {
                cnt++;               
            }
            else //새로운 이동 (위,아래)(여자,남자)
            {
                Move(1, x, y,ref cnt);
                Move(-1, x, y,ref cnt);
            }
        }
    }
}

문제정답(사용언어:python)

1. 최단 경로 문제

죄측 아래에서 우측 위 꼭지점 까지 가는 총 가짓수는 35가지이다.

해당 점까지 이동할때 이전 두점의 가짓수를 더한 값과 같다.

2. 2차원 배열을 1차원으로 표현함

boy, girl = 20, 10
boy, girl = boy+1, girl+1

arr = [0] * (boy*girl)
arr[0] = 1

#2차원 배열 형태를 arr[가로현재위치 + 가로최대크기 * 세로현재 위치]와 같이 1차원 형태로 표현 했다.
for g in range(0,girl):
    for b in range(0,boy):
        if(b!=g) and (boy-b != girl - g):
            if b>0:
                arr[b+boy*g] += arr[b-1+boy*g]
            if g>0:
                arr[b+boy*g] += arr[b+boy*(g-1)]

#-2 인덱스는 마지막 인덱스에서 가로로 -2칸이동을 의미
#-boy- 인덱스는 마지막 인덱스에서 가로 한줄 내려가고 가로로 -1칸 이동을 의미
print(arr[-2] + arr[-boy-1])

-

문제

 전후 좌우로 움직이는 로봇 청소기가 있다. 또한 같은 장소를 다시 지나다지니 않는다. 이때 이 로봇이 12회 이동할 때, 생각할 수 있는 이동 경로의 패턴이 몇 가지인지 구해 보세요.

난이도

IQ 80

목표시간

20분

풀이(c#,VS)

1.

/**
 2020.01.31
 ksj

 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _8_SmartRobotCleaner
{
    class Program
    {
        static int MAXK_COUNT = 12;
        static int[,] dirArr = new int[4,2]{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        static int dd = 0;
        static void Main(string[] args)
        {
            List<int[]> log = new List<int[]>();

            //초기좌표 0,0
            int[] initPos = new int[2]{ 0, 0 };
            log.Add(initPos);

            Console.WriteLine(Move(log));
        }

        static int Move(List<int[]> log)
        {
            if( log.Count == MAXK_COUNT+1)
                return 1;

            int cnt = 0;

            for (int i = 0; i < dirArr.GetLength(0); i++)
            {
                //next move pos
                int[] nextPos = new int[2] { log[log.Count - 1][0] + dirArr[i, 0], log[log.Count - 1][1] + dirArr[i, 1] };

                //can move?
                bool canMove = true;
                for (int j = 0; j < log.Count; j++)
                {
                    if (log[j][0] == nextPos[0] && log[j][1] == nextPos[1])
                    {
                        canMove = false;
                        break;
                    }
                }

                if (canMove)
                {
                    log.Add(nextPos);
                    cnt += Move(log);
                }
            }
            return cnt;
        }
    }
}

문제정답(사용언어:python)

1. 깊이 우선 탐색

2. 배열 -1 인덱스는 배열 맨 마지막 인덱스를 뜻함

N = 12

def move(log):

    # 맨 처음 위치를 포함하여 N+1개 조사하면 종료
    if len(log) == N+1:
        return 1

    cnt =0
    #전후 좌우 이동
    for d in [[0,1],[0,-1],[1,0],[-1,0]]:

        # 탐색이 끝나지 않았으면 이동시킴
        next_pos = [log[-1][0] + d[0], log[-1][1] + d[1]]
        print(log, d, next_pos)
        #로그에 다음 위치가 기록되어 있는지 확인하기
        check = False
        for p in log:
            if p[0] == next_pos[0] and p[1] == next_pos[1]:
                check = True # 있는 경우 플래그를  True로 변경
        if check == False:
            cnt += move(log + [next_pos])

    return cnt

print(move([[0,0]]))

배운점

c#코드가 stackoverflow가 발생한다.. 로그를 배열이 아닌 리스트로 담고 있는 차이인데.. vs 스택사이즈 설정을 확인하려고 속성창에 들어가는데;; 안 보인다... 프로젝트 생성할떄 잘못된건지.. 버전문제인지 잘 모르겠다. 보면 볼수록 파이썬이 코드가 직관적이고 유연성이 좋아보인다.. 컬렉션 추가도 간단한 연산처리 처럼 되니.. 파이썬하다가 불편해서 다른 언어 쓰겠나..

문제

 연월일을 YYYYMMDD의 8자리 정수로 나타내었을 때 2진수로 변환하여 거꾸로 나열한 다음 다시 10진수로 되돌렸을 때 원래 날짜와 같은 날짜가 되는 것을 찾아보세요. 기간은 지난 도쿄 올림픽(1964년 10월 10일)부터 다음 도쿄 올림픽(2020년 7월 24일 예정)으로 하겠습니다.

ex)

 1. YYYYMMDD의 포맷 -> 19660713

 2. 2진수로 변환 -> 1001010111111111110101001

 3. 2진수를 거꾸로 나열 -> 1001010111111111110101001

 4. 거꾸로 나열한 2진수를 10진수로 되돌림 -> 19660713

난이도

IQ 80

목표시간

20분

풀이(c#,VS)

1.진수변환,문자열Reverse

2.DateTime 생성자 에러로 날짜변환 가능여부 판단

/*
* 2020.01.30
* ksj
*/ 

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

namespace _6_BinaryConversionOfDates
{
    class Program
    {
        static void Main(string[] args)
        {
            int start = 19641010;
            int end = 20200724;

            for (int i = start; i <= end; i++)
            {
                string binarayNum = Convert.ToString(i, 2);
                string ReverseNum = new string(binarayNum.ToCharArray().Reverse().ToArray());

                if (binarayNum.Equals(ReverseNum))
                {
                    try
                    {
                        string decimalNum = Convert.ToInt32(binarayNum, 2).ToString();
                        new DateTime(Convert.ToInt32(decimalNum.Substring(0, 4)), Convert.ToInt32(decimalNum.Substring(4, 2)), Convert.ToInt32(decimalNum.Substring(6, 2)));

                        Console.WriteLine(decimalNum);
                    }
                    catch
                    {
                        //날짜 형식 변화 불가
                    }
                    
                }

            }
        }


    }
}

문제정답(사용언어:python)

1.탐색 범위를 확인한다.

 19641010 : 1001010111011001010110010

 20200724 : 1001101000011110100010100

2. 25자리이며 앞자리가 1001로 공통이다.

3. 이진수를 reverse했을 일치해야하므로 

4. 탐색범위는 1001 ******** * ******** 1001 과 같은 형태다

5. 5~12자리 수와 14~21자리 수 역시 대칭되어야 하므로 일치된다.

6. 따라서 5~12자리수만 탐색 하면된다.

# 날짜를 다루는 datetime 클래스 불러오기
from datetime import datetime, timedelta

# 대상 기간에서 2진수의 5번째 문자부터 8개의 문자 추출
from_left = int(bin(19641010).replace("0b","")[4:4 +8],2)
to_left = int(bin(20200724).replace("0b","")[4:4 +8],2)

# 좌우의 8문자를 반복
for i in range(from_left, to_left+1):
    l = "{0:08b}".format(i)     # 왼쪽
    r = l[::-1]
    for m in range(0, 1+1):
        value = "1001{}{}{}1001".format(l, m, r)
        try:
            # 변환 가능한지 확인
            date = datetime.strptime(str(int(value,2)), "%Y%m%d")
            # 변환 가능할 경우 출력
            print(date.strftime("%Y-%m-%d"))
        except:
            # 변환 불가
            pass

    

배운점

 날짜형식인지 여부를 datetime api 에러로 쉽게 확인.

 탐색 범위를 연구하여 규칙성을 찾고 탐색 범위를 줄임.

 단, 제시된 조건에서만 적용되는 규칙성이기 때문에 확장성이 없고 규칙성을 이해하고 있는 사람이 아니라면 소스코드만 보고 문제를 이해하기 힘들다. 

문제

 수학의 미해결 문제중 하나로 콜라츠 추측이 있다.

 콜라츠 추측

   -n이 짝수인 경우, n을 2로 나눈다.

   -n이 홀수인 경우, n에 3을 곱해 1을 더한다.

  이 계산을 반복하면 초깃값이 어떤 수였더라도 반드시 1에 도달한다.

이 내용을 조금 바꾸어 초깃값이 짝수면 맨 처음에만 n에 3을 곱하여 1을 더하는 것에서 시작하기로 하고 '맨 처음의 수'로 돌아가는 법을 생각해 보자.

ex)

 2 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2

 4 13 40 20 10 5 16 8 4

 6 ....(6으로 돌아가지 않음)

10000 이하의 짝수 중 앞의 2나 4와 같이 '처음의 수로 돌아가는 수'가 몇 개 있는지 구해 보세요.

난이도

IQ 75

목표시간

15분

풀이(c#,VS)

1.재귀함수를 이용

2.초기값이 어떤 수더라도 반드시 1에 도달하다는 점

/*
 *2020.01.28
 * ksj
 */

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

namespace _6_CollatzConjecture
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;

            for(int i=2; i<=10000; i += 2) //10000이하의 짝수 갯수만큼 반복
            {
                int num = i * 3 + 1;

                if (cal(i,num))
                {
                    count++;
                }
            }

            Console.WriteLine(count);
        }

        private static bool cal(int originalNum, int curNum)
        {
            if(originalNum == curNum)
            {
                return true;
            }

            if(curNum == 1)
            {
                return false;
            }

            if (curNum % 2 == 0)
            {
                int temp = curNum / 2;
                return cal(originalNum, temp);
            }
            else
            {
                int tmep = curNum * 3 + 1;
                return cal(originalNum, tmep);
            }
        }
    }
}

문제정답(사용언어:python)

1.초기값이 어떤 수더라도 반드시 1에 도달하다는 점

# 반복하며 확인
def is_loop(n):
    # 맨 처음에는 3을 곱하고 1을 더함
    check = n*3+1
    # 1이 될 때까지 숫자를 변화시키는 작업 반복
    while check !=1:
        check = check // 2 if check % 2 == 0 else check * 3 +1
        if check == n:
            return True
        
    return False

# 2~10000 범위의 짝수 확인하기
cnt = 0
for i in range(2, 10000+1,2):
    if is_loop(i):
        cnt+=1
print(cnt)

문제

환전 자판기가 있다. 잔돈으로 10, 50, 100, 500 그리고 최대 갯수 15개로 설정 되어 있다. 사용자가 천원을 넣었을때 이때 환전 자판기가 거슬러 줄수 있는 가짓수를 계산하여라. (잔돈 설정, 최대갯수 설정에 확장성이 있게 짤것)

난이도

IQ 75

목표시간

15분

문제정답(사용언어:python)

1. deque 와 // 를 이용

from collections import deque

cnt =0
def change(target, coins, usable):
    global cnt
    coin = coins.popleft()
    if len(coins) == 0:
        if target//coin <= usable:
            cnt +=1
    else :
        for i in range(0, target // coin +1 ) :
            change(target - coin*1, coins,copy(), usable -i)

change(1000, deque([500, 100, 50, 10]) , 15)
print(cnt)

배운점

파이선 // 연산기호 => 나머지 연산이후 정수부분만 반환한다.

단순하게 중첩 for문을 이용하여 풀면 쉽고 간단한 문제. 하지만 문제에서는 확장성을 고려하여 재귀형태로 답을 요구한듯 하다. 절차형 언어에서는 재귀보다는 반복문을 선호하지만 함수형 언어에서는 반복문보다는 재귀를 선호 한다고 한다. 이책에 모든 풀이는 파이썬으로 작성되어 있어서 대부분의 반복문 처리할 내용들이 재귀로 풀이되어 있다. 

여지껏 재귀는 디버깅이 쉽지 않고 코드 이해도를 떨어트린다고 생각해서 기피해왔지만 알고리즘적인 문제 해결면에서는 재귀적인 표현도 괜찮은것 같다. 이참에 재귀표현에 익숙해져야 겠다.

문제

길이 n cm의 한 막대를 1cm 단위로 자른다. 단, 하나의 막대는 한번에 한 사람만이 자를 수 있다. 잘린 막대가 3개면 동시에 3명이 자를 수 있다. 최다 m명이 있을 때 막대를 자르는 최소 횟수를 구하시오. 예를 들어 n=8, m=3일때 4번 자를 수 있다.

난이도

IQ 70

목표시간

10분

문제풀이(사용언어:C#, 작성도구:VisualStudio2019)

//20.01.09
//
//

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

namespace _4_CutStick
{
    class Program
    {
        static void Main(string[] args)
        {
            int STICK_LENGH = 100;
            int MEMBER_COUNT = 5;
            
            double depth = Math.Ceiling(Math.Log(STICK_LENGH, 2));
            Console.WriteLine("length :: " + STICK_LENGH);
            Console.WriteLine("members :: " + MEMBER_COUNT);
            Console.WriteLine("depth :: " + depth);

            double resultCnt = 0f; //최종 자르는 횟수
            int totalCutCnt = 0;   //좌우로 2의 제곱으로 증가하면서 자르는 횟수
            int remainCut=0;       //사람이 부족해서 다음 스텝에서 잘라야 하는 횟수

            for (int i=0; i<depth; i++)
            {
                totalCutCnt++;
                int cutCnt = (int)Math.Pow(2, i);

                if (MEMBER_COUNT < cutCnt)
                {
                    remainCut += cutCnt - MEMBER_COUNT;
                }

                //마지막 뎁스 일때
                if (i == (depth-1) )
                {
                    //2의 제곱수가 아니면 홀수 단위로 자르게 되어 추가적으로 잘라야한다.
                    if ( (Math.Log(STICK_LENGH,2) - (int)Math.Log(STICK_LENGH,2) ) != 0)
                    {
                        int addCutCnt = (int)Math.Pow(2, i - 1);

                        if(MEMBER_COUNT < addCutCnt)
                        {
                            totalCutCnt++;
                            remainCut += addCutCnt - MEMBER_COUNT;
                        }
                    }
                }
            }

            resultCnt = totalCutCnt + Math.Ceiling((double)remainCut/MEMBER_COUNT);
            Console.WriteLine("least cut count::" + resultCnt);

        }
    }
}

문제정답(사용언어:python)

1. solution_1은 문제 그대로를 재귀로 옮긴 방식

2. solution_2 발상의 전환. m명이 n막대를 자르는게 아닌 m명이 1cm 막대를 n cm 막대로 붙여 나간다고 생각.

##solution_1
def cutbar(m, n, current): # current는 현재 막대의 개수
    if current >= n:
        return 0 # 잘라내기 완료
    elif current < m:
        return 1 + cutbar(m, n, current*2) # 다음은 현재의 2배가 된다
    else :
        return 1 + cutbar(m, n, current+m) # 가위 수만큼 증가

print(cutbar(3, 20, 1))
print(cutbar(5, 100, 1))

##solution_2
def cutbar(m, n): 
    count = 0;
    current = 1 # current는 현재 막대의 길이
    while n > current:
        print(current)
        current += current if current <m else m
        count +=1
    print(count)

cutbar(3, 20)
cutbar(5, 100)

배운점

깊이 우선 방식을 이용한 재귀구현.

깊이 우선 방식의 경우 모든 탐색 경로를 찾을시에는 메모리 공간을 아낄수 있다.

너비 우선 탐색은 가장 빠른 탐색 경로 하나를 발견해야하는 경우에는 유리하다.

문제

1~100까지 카드가 뒤집어져 있다. n번쨰 카드를 n-1씩 이동하여 카드를 뒤집는다. (n초기값 = 2) 100번째 카드까지 이러한 과정을 거쳤을때 뒤집어져 있는 카드는 ?

예)  (■:뒤 □:앞)

n=2  ■□■□■□■□■□ 

n=3  ■□□□■■■□□□ 

n=4  ■□□■■■■■□□ 

난이도

IQ 70

목표시간

10분

문제풀이(사용언어:C#, 작성도구:VisualStudio2019)

//20.01.08
//
//

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

namespace _3_TurnCardOver
{
    class Program
    {
        static void Main(string[] args)
        {
            //0:뒤 1:앞
            int[] deck = new int[100];

            //deck 초기화(모든 카드가 뒤집힌 상태)
            for(int i=0; i<deck.Length; i++)
            {
                deck[i] = 0;
            }

            //뒤집기
            for (int i=2; i<=deck.Length; i++)
            {
                for(int j=i-1; j< deck.Length; j+=i)
                {
                    if (deck[j] == 0)
                        deck[j] = 1;
                    else
                        deck[j] = 0;
                }
            }

            //결과
            for (int i = 0; i < deck.Length; i++)
            {
                if (deck[i] == 0)
                {
                    Console.WriteLine(i+1);
                }

            }


        }
    }
}

문제정답(사용언어:python)

1. solution_1은 문제 그대로의 규칙대로 작성된 방법

2. solution_2는 제곱수(1,4,9,16 ..)만을 구하는 방법

 2.1 나열된 카드는 홀수 뒤집혔을때 앞면을 짝수번 뒤집혔을때 된다.

 2.2 예를 들어 16번 카드는 2 4 8 16번째 카드를 이동할떄 마다 뒤집힌다.

 2.3 2 4 8 16은 16의 약수이다

 2.4 즉 1~100까지 숫자 중에 약수가 홀수개인 숫자를 찾으면된다

 2.5 약수가 홀수개인 수는 제곱수이다.

 2.6 왜? 약수를 오름차순으로 나열했을때 각 끝 숫자들의 곱은 해당 숫자값이된다

 2.7 16의 약수의 경우 1*16=16, 2*8=16, 4*4 =16 가운데 남는 4는 4*4=16이 된다.

 2,.8 따라서 제곱수는 약수가 홀수개이다 제곱수는 문제의 정답수이다.  

# 카드의 초기화
N = 200
cards = [False] * N


## solutin_1
# 2~N까지 뒤집음
for i in range(2, N+1) :
    j=i-1
    while j < len(cards):
        cards[j] = not cards[j]
        j+=i

#뒷면이 위를 향한 카드 출력
for i in range(0,N):
    if not cards[i]:
        print(i+1)


##solutin_2
for i in range(1, N+1):
    flag = False
    for j in range(1, N+1):
        if i%j==0:
            flag = not flag
    if flag:
        print(i)

배운점

 파이썬의 쉬운 배열 초기화를 보고 c#에서도 가능한지 찾아보았다

    int[] myIntArray = Enumerable.Repeat(-1, 20).ToArray();

 단순히 규칙을 코드로 옮겨 문제를 풀었다. 코드로 옮기는대 시간이 걸리더라도 그전에 단순히 문제 그대로의 풀이 방식이 아닌 새로운 방법에 대해서 다양한 접근을 습관적으로하는게 좋을것 같다. 어려운 규칙은 단순화 시켜 코드작성을 하지만 단순한 규칙은 쉽게 생각을 멈추고 코딩하는 것 같다.