空놀이

if 문을 만들어 보려고 한다.

if 문은 소프트웨어에서 가장 기본적이고도 중요한 문법이다.

'만약 사람이 들어왔다면 불을 켜라.' 라는 것을 실행하고 싶다면,

if 사람이 들어왔니?:

    print("불을 켜라")

와 같은 방식으로 실행하면 된다.

구구단에서 2단 4단 6단 8단만 출력하고 싶다면?

아래와 같이 코딩을 하면 된다.

def Dan(i): 
  for j in range(1, 10): 
    print("%d x %d = %d" % (i, j, i * j), end = "\t") 
  print() 

for i in range(2, 10): 
  if(i %2 == 0):
    Dan(i)

i % 2 라는 말은 i 값에서 2로 나눈 나머지 값을 계산해달라는 말이다.

1 / 2의 나머지 값은 1이고

2 / 2의 나머지 값은 0

3 / 2의 나머지 값은 1이고

4 / 2의 나머지 값은 0 이다.

즉 나머지 값이 0인 것을 찾아 달라는 말은 2의 배수를 찾아 달라는 말이다.

이를 통해 구구단 중에서 2단 4단 6단 8단만 출력을 할 수 있게 되었다.

이번 시간에는 함수 호출에 대해서 얘기해 보려고 한다.

함수란..

특정한 역할을 해주는 것을 따로 빼 놓은 것이다.

예를 들어, 아래와 같이 더하기를 계산해주는 함수가 있다고 하자.

def SUM(a, b):
  return (a+b)

c = SUM(10, 20)
print(c)

출력 _> 30

SUM 이란 함수이며 인자를 a와 b 두개를 받는다.

SUM(10, 20) 이라고 호출해 주면

SUM 함수는 10과 20을 받아서 10과 20의 합을 돌려준다.

c라는 변수에서 SUM이라는 함수에서 나온 값을 저장하고,

출력을 해주면, 30이란 값이 출력된다.

이전에 짰던 구구단을 함수를 이용해 만들어 보자.

몇단을 출력해줄지 입력을 받아서 1단, 2단 5단 등의 내가 원하는 단만 출력해주는 함수이다.

def Dan(i):
  for j in range(1, 10):
    print("%d x %d = %d" % (i, j, i * j), end = "\t")
  print()

Dan(2)
Dan(4)

Dan이라는 함수를 만들고, 2 와 4를 입력하면,

아래와 같이 2단과 4단이 출력되는 것을 확인할 수 있다.

2 x 1 = 2 2 x 2 = 4 2 x 3 = 6 2 x 4 = 8 2 x 5 = 10 2 x 6 = 12 2 x 7 = 14 2 x 8 = 16 2 x 9 = 18

4 x 1 = 4 4 x 2 = 8 4 x 3 = 12 4 x 4 = 16 4 x 5 = 20 4 x 6 = 24 4 x 7 = 28 4 x 8 = 32 4 x 9 = 36

그럼 2단에서 9단까지 출력하려면 어떻게 하면 될까?

def Dan(i):
  for j in range(1, 10):
    print("%d x %d = %d" % (i, j, i * j), end = "\t")
  print()

for i in range(2, 10):
  Dan(i)

위와 같이 하면, 우리는 이전에 했던 구구단을 출력할 수 있다.

2 x 1 = 2 2 x 2 = 4 2 x 3 = 6 2 x 4 = 8 2 x 5 = 10 2 x 6 = 12 2 x 7 = 14 2 x 8 = 16 2 x 9 = 18

3 x 1 = 3 3 x 2 = 6 3 x 3 = 9 3 x 4 = 12 3 x 5 = 15 3 x 6 = 18 3 x 7 = 21 3 x 8 = 24 3 x 9 = 27

4 x 1 = 4 4 x 2 = 8 4 x 3 = 12 4 x 4 = 16 4 x 5 = 20 4 x 6 = 24 4 x 7 = 28 4 x 8 = 32 4 x 9 = 36

5 x 1 = 5 5 x 2 = 10 5 x 3 = 15 5 x 4 = 20 5 x 5 = 25 5 x 6 = 30 5 x 7 = 35 5 x 8 = 40 5 x 9 = 45

6 x 1 = 6 6 x 2 = 12 6 x 3 = 18 6 x 4 = 24 6 x 5 = 30 6 x 6 = 36 6 x 7 = 42 6 x 8 = 48 6 x 9 = 54

7 x 1 = 7 7 x 2 = 14 7 x 3 = 21 7 x 4 = 28 7 x 5 = 35 7 x 6 = 42 7 x 7 = 49 7 x 8 = 56 7 x 9 = 63

8 x 1 = 8 8 x 2 = 16 8 x 3 = 24 8 x 4 = 32 8 x 5 = 40 8 x 6 = 48 8 x 7 = 56 8 x 8 = 64 8 x 9 = 72

9 x 1 = 9 9 x 2 = 18 9 x 3 = 27 9 x 4 = 36 9 x 5 = 45 9 x 6 = 54 9 x 7 = 63 9 x 8 = 72 9 x 9 = 81

이전 챕터에서 구구단을 출력해보자고 얘기 했다.

구구단을 출력해보기 위해 우선 알아야 할 것은

문자열과 숫자 같이 출력하기와 2중 반복문이다.

일단 문자열과 숫자 같이 출력하기를 해보겠다.

(1) print("out: %d" % 1) 를 입력해 보자.

출력 ->   out: 1

이 경우 " " 안에 있는 문자가 출력되지만, %d가 출력이 되지 않고, " " % 뒤에 있는 숫자가 출력된 것을 확인할 수 있다.

(2) print("%d x %d = %d" % (2, 1, 2)) 를 입력해 보자

2 x 1 = 2 라고 출력되는 것을 확인할 수 있다.

즉 %d 가 뒤에 있는 2, 1, 2 로 대체 되어 출력된 것을 확인할 수 있다.

(3) 이제 변수를 출력해 보자.

for i in range(2, 9):
  print("2 x %d = %d" % (i, 2 * i))

출력 

2 x 1 = 2

2 x 2 = 4

2 x 3 = 6

2 x 4 = 8

2 x 5 = 10

2 x 6 = 12

2 x 7 = 14

2 x 8 = 16

2 x 9 = 18

짠!! 2단이 출력된 것을 확인할 수 있다.

파이썬에서 계산한 값까지 같이 출력이 되었다.

(4) 2중 반복문을 실행해 보자.

아래와 같이 for 아래에서 또 for 반복문이 들어가면, 

2단부터 9단까지 출력을 할 수 있다.

for i in range(2, 10):
  for j in range(1, 10):
    print("%d x %d = %d" % (i, j, i * j))

출력은 너무 길어서 생략한다.

실행해 보면 알겠지만, 2단부터 9단까지 아래로 쭉 내려오니 너무 보기가 어렵다.

그래서 2장에서 배운 띄어 쓰기와 줄바꿈을 이용해 보자.

(5) 2중 반복문

for i in range(2, 10):
  for j in range(1, 10):
    print("%d x %d = %d" % (i, j, i * j), end = "\t")
  print()                                                           # 줄바꿈

여기서 end = " " 이 아니라, end = "\t"라고 써 줬는데, 이것은 띄어쓰기가 아니라 tab으로 정렬해 주라는 명령어이다.

# 뒤에 들어간 글자는 주석으로 소스코드에 영향을 주지 않는다.

출력 ->

2 x 1 = 2 2 x 2 = 4 2 x 3 = 6 2 x 4 = 8 2 x 5 = 10 2 x 6 = 12 2 x 7 = 14 2 x 8 = 16 2 x 9 = 18

3 x 1 = 3 3 x 2 = 6 3 x 3 = 9 3 x 4 = 12 3 x 5 = 15 3 x 6 = 18 3 x 7 = 21 3 x 8 = 24 3 x 9 = 27

4 x 1 = 4 4 x 2 = 8 4 x 3 = 12 4 x 4 = 16 4 x 5 = 20 4 x 6 = 24 4 x 7 = 28 4 x 8 = 32 4 x 9 = 36

5 x 1 = 5 5 x 2 = 10 5 x 3 = 15 5 x 4 = 20 5 x 5 = 25 5 x 6 = 30 5 x 7 = 35 5 x 8 = 40 5 x 9 = 45

6 x 1 = 6 6 x 2 = 12 6 x 3 = 18 6 x 4 = 24 6 x 5 = 30 6 x 6 = 36 6 x 7 = 42 6 x 8 = 48 6 x 9 = 54

7 x 1 = 7 7 x 2 = 14 7 x 3 = 21 7 x 4 = 28 7 x 5 = 35 7 x 6 = 42 7 x 7 = 49 7 x 8 = 56 7 x 9 = 63

8 x 1 = 8 8 x 2 = 16 8 x 3 = 24 8 x 4 = 32 8 x 5 = 40 8 x 6 = 48 8 x 7 = 56 8 x 8 = 64 8 x 9 = 72

9 x 1 = 9 9 x 2 = 18 9 x 3 = 27 9 x 4 = 36 9 x 5 = 45 9 x 6 = 54 9 x 7 = 63 9 x 8 = 72 9 x 9 = 81

짠~~ 예쁘게 출력 되었다.

inorder 트리 구조가 어떤 것인지 알게 되었다.

class Solution:
    def __init__(self):
        self.traversal = []
        
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        
        
        self.inorderTraversal(root.left)
        
        self.traversal.append(root.val)
        
        
        self.inorderTraversal(root.right)
        
        return self.traversal

위키백과에 따르면, 트리 구조는 아래와 같다.

이진 탐색 트리에서

• 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
• 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
• 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
• 레벨 순서 순회: F, B, G, A, D, I, C, E, H

출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

파이썬 그리고 트리에 익숙해지기

"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        traversal = [root.val]
        for child in root.children:
            traversal.extend(self.preorder(child))
        return traversal

-> 뒤에 나오는 것은 리턴 타입이다

즉 List[int] 가 리턴 타입

모든 언어의 기본은 반복문이다.

대표적으로 for문과 while문이 있는데,

많은 친구들이 이 쉬운 문법을 이해하지 못해서, 프로그래밍을 포기한다.

심지어 컴퓨터 학과 학생들도 이해를 하지 못해서 포기하는 경우가 많았다.

물론 그 때는 파이썬이 나오기 전이었고, c를 사용하던 때였으니..

그럼 가장 간단한 반복문을 실행해 보자

for i in range(1, 6):
  print(i)

i가 1~6의 영역안에서 바뀌는 동안, i의 값을 출력하라는 뜻이다.

1~6 의 영역인데 실제로는 1보다 크거나 같고 6보다 작은 값을 출력하라는 뜻이다.

주의: for문 아래에서 반복할 명령어들은 tab 키를 이용해서 안으로 들여쓰기를 해야함을 명심해야 한다.

이렇게 5개의 숫자가 나오는 것을 알 수 있다.

i가 1~5 로 바뀌면서 출력된 것이다.

하지만 숫자 하나가 나오도 또  줄이 바뀌니 한눈에 보기가 어렵다.

한 줄에 1 2 3 4 5 를 출력해보자.

for i in range(1, 6):
  print(i, end = ' ')

end = ' ' 를 넣으니 숫자 출력 뒤에 줄 바뀜이 사라지고, end에 넣어준 공백이 나온 것을 확인할 수 있다.

end에 값을 안 넣으면 '\n' 이라는 줄바뀜이 들어가 있음을 예상할 수 있다.

다음 장에서는 아래와 같이 구구단을 출력해 볼 것이다.

2 x 1 = 2     3 x 1 = 3    4 x 1 = 4   ...........  9 x 1 = 9

2 x 2 = 4 . . . . . . .                                             9 x 2 = 18

.

.

2 x 9 = 18 ...                                                       9 x 9 = 81

모든 언어가 그렇지만, 

hello world를 실행하는 것이 매우 어렵다.

hello world가 출력된다는 것은, 

컴파일러를 설치하고, 필요한 라이브러리가 제대로 설치되었다는 것인데..

요즘은 그래도 많이 좋아지긴 했지만..

여전히 어려운 부분들이 생긴다.

파이썬은 버젼2와 버젼3이 있는데,

파이썬3이 최신이니 파이썬3으로 공부해 보도록 하겠다.

쉬운 공부를 위해 파이썬을 설치하지 않을 예정이다.

대신, 구글이 제공하는 멋진 무료 사이트인 Google Colaboratory 를 이용할 것이다.

구글은 tensorflow를 이용할 수 있는 무료 웹서버를 제공하는데, 성능도 매우 좋다.

어느정도 언어가 익술해지고 난 후 원하는 컴파일러를 설치하면 된다.

그건 나중에 하자.

1. 우선 아래 주소에 접속하자.

가입이 필요할 수도 있는데, 본인의 구글 아이디로 연결해 주면 된다.

https://colab.research.google.com/notebooks/welcome.ipynb

2. '파일 -> 새 Python 3 노트' 를 누르자

3. 아래와 같이 글자를 쓰고 왼쪽 실행 버튼을 누르자.

print("Hello Python World!!")

4. 아래와 같이 내가 print한 글자가 화면에 출력되면 성공이다

C++은 알아서 정렬을 빠르게 해준다.

구조체의 경우도 아래와 같이 가능

#include <algorithm>

#include <vector>

struct st{
int X, ID;//위치, 아이디
};
st AI[50010];

bool myfunction (st i,st j) { 

    return (i.X < j.X); 

}

void main(void){

    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> AI[i].X >> AI[i].ID;
        A.push_back(AI[i]);
    }

    sort (A.begin(), A.end(), myfunction); 

}

출처 : http://www.cplusplus.com/reference/algorithm/sort/ 

C++로 코드를 짜려고 했었는데..

이 문제는 Playground에서 C++ 지원이 되지 않았다. 

그래서 자바로 변경해서 디버깅을 하고, 다시 C++로 변경하였다.

한번에 코드를 다 짜면 좋은데,

코드 짜다가 아들 우유 주고, 산책 다녀오고, 밥 먹고 와서 다시 짜다 보니까

중간에 산으로 한번 갔다가 다시 돌아왔다.

핵심을 잘 생각하고, 종이에 먼저 써보고 코딩하는 습관을 들여야겠다.

C++ Code

class Solution {
public:
    vector<vector> visited;
    vector<vector> wall;
    vector<vector> original_board;


    int r_len;
    int c_len;
    
    int printFlag = 0;
    int change(vector<vector>& board, int r, int c, int w){
        
        //if(printFlag == 1)
        //    System.out.println(r + " " + c);
        
        int wall_detected = 0;
        if(r < 0 || r >= r_len || c < 0 || c>= c_len){
            //if(printFlag == 1)
            //    System.out.println(r + " " + c + " return " + 1);
            return 1;
        }
        if(board[r][c] == 'X'){
            //if(printFlag == 1)
            //     System.out.println(r + " " + c + " return " + 0);
            return 0;
        }
        
        if(w == 1)
            wall[r][c] = 1;
        
        if(visited[r][c] == 1){
            //if(printFlag == 1)
            //    System.out.println(r + " " + c + " visited " + wall[r][c] );
        
            //cout << "visited " << wall[r][c] << endl;
            if(wall[r][c] == 0)
                return 0;
            return 1;
        }
       
        if(visited[r][c] == 1){        
            //cout << "visited " << wall[r][c] << endl;
            if(wall[r][c] == 0)
                return 0;
            return 1;
        }
       
        //System.out.println("");
        //cout << endl;
        visited[r][c] = 1;
        
        wall_detected = change(board, r, c-1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r, c+1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r-1, c, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r+1, c, wall[r][c]);          
        if(wall_detected == 1)
            wall[r][c] = 1;
        

        if(board[r][c] == 'O' && wall_detected == 0)
            board[r][c] = 'X';
        wall[r][c] = wall_detected;
        //if(printFlag == 1)
        //    System.out.println("return " + r + " " + c + " " + wall_detected );
        return wall_detected;
        
    }
    void solve(vector<vector>& board) {        
        r_len = board.size();
        if(r_len == 0)
            return;
        c_len = board[0].size();
        
        original_board = board;

        for(int i = 0; i < r_len; i++){
            vector wallvector;
            vector visitedvector;
            for(int j = 0; j < c_len; j++){
                wallvector.push_back(0);
                visitedvector.push_back(0);
            }
            wall.push_back(wallvector);
            visited.push_back(visitedvector);

        }
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 3 && j == 3)
                        printFlag = 2;
                    change(board, i, j, 0);
                }
            }
        }
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 3 && j == 3)
                        printFlag = 2;
                    change(board, i, j, 0);
                }
            }
        }

    }
};

Java Code

class Solution {
    //int visited[][];
    //int wall[][];
    int visited[][] = new int[1000][1000];
    int wall[][] = new int[1000][1000];
    char original_board[][] = new char[1000][1000];


    int r_len;
    int c_len;
    
    int printFlag = 0;
    int change(char[][] board, int r, int c, int w){
        
        if(printFlag == 1)
            System.out.println(r + " " + c);
        
        int wall_detected = 0;
        if(r < 0 || r >= r_len || c < 0 || c>= c_len){
            if(printFlag == 1)
                System.out.println(r + " " + c + " return " + 1);
            return 1;
        }
        if(board[r][c] == 'X'){
            if(printFlag == 1)
                 System.out.println(r + " " + c + " return " + 0);
            return 0;
        }
        
        if(w == 1)
            wall[r][c] = 1;
        
        if(visited[r][c] == 1){
            if(printFlag == 1)
                System.out.println(r + " " + c + " visited " + wall[r][c] );
        
            //cout << "visited " << wall[r][c] << endl;
            if(wall[r][c] == 0)
                return 0;
            return 1;
        }
       
        //System.out.println("");
        //cout << endl;
        visited[r][c] = 1;
        
        wall_detected = change(board, r, c-1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r, c+1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r-1, c, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r+1, c, wall[r][c]);          
        if(wall_detected == 1)
            wall[r][c] = 1;
        

        if(board[r][c] == 'O' && wall_detected == 0)
            board[r][c] = 'X';
        wall[r][c] = wall_detected;
        if(printFlag == 1)
            System.out.println("return " + r + " " + c + " " + wall_detected );
        return wall_detected;
        
    }
    void solve(char[][] board) {
        
        r_len = board.length;
        if(r_len == 0)
            return;
        c_len = board[0].length;
        
    
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                wall[i][j] = 0;
                visited[i][j] = 0;
                original_board[i][j] = board[i][j];
            }
        }
        int finish = 0;
        
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 2 && j == 5)
                        printFlag = 2;

                    if(printFlag == 1)
                        System.out.println("Call " + i + " " + j);
                    change(board, i, j, 0);
                }
            }
        }
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 3 && j == 3)
                        printFlag = 2;
                    change(board, i, j, 0);
                }
            }
        }
    }
};