요즘 알고리즘과 프로그래밍언어 같이 공부하기 글과 같이 백준온라인의 '단계별로 풀어보기'를 통해 문제를 풀고 있습니다.

그 중 '별찍기 11 - 2448'에 대한 풀이 입니다.


주어진 라인수만큼 별을 찍는 문제인데요 라인수 N은 3, 6, 12, 24, 48, ... 와 같이 3*2^k (k <=10) 입니다.

N = 3 일 때, 아래와 같이 프린트해야하며 아래 삼각형이 기본 단위가 되겠습니다.

***
***
*****


N = 6 일 때,

******                        
***** *                       
********                      
*********                     
**********                    
***********


N = 12 일 때,

************                        
*********** *                       
**************                      
***************                     
****************                    
*****************
******************
***** *********** *
********************
*********************
**********************
***********************


요런 식인데요, 잘 보면 규칙성이 있습니다.

다음 단계 삼각형은 현 단계 삼각형 두 개가 아래에 위치하 것과 같은 모양이 됩니다.

그래서 저는 다음과 같이 문제를 풀었습니다.

"현 단계 삼각형 두 개를 만들어서 뒤에 붙이고 현 단계 삼각형을 오른쪽으로 민다."


N = 6 일 때,

1. 현 단계 삼각형

***
***
*****

2. 현 단계 삼각형 두 개를 만들어서 뒤에 붙인다

***                        
** *                       
*****                      
*********                     
**********                    
***********

3. 현 단계 삼각형을 오른쪽으로 민다.

******                        
***** *                       
********                      
*********                     
**********                    
***********


위의 3번에서 "현 단계 삼각형을 오른쪽으로 민다"고 했는데요,

그렇다면 '오른쪽으로 얼마나 밀어야하는가?'가 문제입니다.

요것도 규칙이 있습니다.

기본적으로 아래와 같이 삼각형을 갖고 있다면,

***
***
*****

N = 3 일 때, 0칸

N = 6 일 때, 3칸

N = 12 일 때, 6칸

...

N = 3 × 2^k 이므로, 오른쪽으로 미는 칸 수는 바로 3 × 2^(k - 1)가 되겠습니다. 아래와 같은 수식으로 k를 구할 수 있습니다.

log₂(N ÷ 3) = log₂(3 × 2^k ÷ 3) = log₂2^k = k


구현은 파이썬 언어를 사용했습니다.

저는 기본 삼각형을 아래와 같이 1차원 배열로 선언하고

s = ["  *   ", " * *  ", "***** "] #삼각형 사이에 빈 칸 하나 있음을 고려


다음 단계 삼각형을 만드는 함수를 아래와 같이 선언했습니다.

def makeStar(shift):
    c = len(s)
    for i in range(c):
        s.append(s[i] + s[i]) #현 단계 삼각형을 뒤에 붙이고
        s[i] = ("   " * shift + s[i] + "   " * shift) #현 단계 삼각형을 오른쪽으로 민다

전체 소스코드 입니다.


얼마 전 회사에서 머신러닝에 대해 사내 강의를 들었습니다.

사내 강의였지만 머신러닝에 대해 전문가가 없기에 홍콩과기대 김성훈 교수님의 공개강의를 같이 듣는 걸로 대신했습니다.

(Link : 모두를 위한 머신러닝/딥러닝 강의)

실습은 Google이 만든 TensorFlow를 사용했는데 구현 언어는 Python 이었고 이렇게 자연스레 Python을 접하게 되었습니다.

그런데 머신러닝은 너무 어려웠고 그 이언에 Python이란 언어에 대한 이해도도 너무 낮았습니다.

어영부영 강의는 끝났고 머신러닝과 Python이 뇌리에서 사라져가고 있었습니다.


그러던 어느날, 매 달 알고리즘 퀴즈가 게시될거고 제일 먼저 푸는 사람에게 10만원 상품권을 지급하겠다는 글이 회사 게시판에 올라왔습니다.

이어서 8월 퀴즈 문제가 올라왔는데 저는 대학생 때 문제 풀던 경험을 살려 꼭 10만원을 타내겠다는 일념으로 문제를 후벼팠습니다.

그리고 무참히 패배했습니다 ㅡㅡ;;


참 오랜만의 문제풀기에 실패하고 Python과 알고리즘 두 가지를 공부해야겠다는 마음이 생겼습니다.

그래서 시작한게 문제풀기를 Python으로 하기!

온라인 저지는 예전에 봐뒀던 Baekjoon Online Judge 입니다.

운영자 최백준님은 꽤 유명하신 분 같네요. 알고리즘 공부법에 대한 슬라이드도 찾을 수 있었습니다. 



Python과 알고리즘 둘을 같이 공부해야 했기에 쉬운 문제부터 풀기로 했습니다. 저 같은 사람을 위한 메뉴가 있었는데요 바로 단계별로 문제풀기 입니다.

문제 > 단계별로 풀어보기 순으로 들어가면 단계별로 묶인 문제들을 볼 수 있습니다.


입/출력, 사칙연산, for문, if문 등 정말 기초부터 다질 수 있는 문제들로 시작할 수 있습니다.

단계별 문제들을 풀다보면 Python의 기본 문법은 다 알 수 있을거 같습니다.

저는 for문을 사용하는 문제들까지 다 풀었네요 ㅎㅎ


이상 알고리즘과 프로그래밍 언어 같이 공부하는 좋은 방법에 대한 포스팅이었습니다.

+ Recent posts