Algorithms, Data Analytics

배열은 순차적으로 연결된 공간에 데이터를 나열하는 구조

배열은 미리 공간을 예약해둬야 한다는 단점이 있다.

이 단점을 해결한 것이 연결 리스트(Linked List)이다.

연결 리스트는 미리 공간을 예약 해두지 않아도 필요할 때 마다 데이터를 추가할 수 있는 구조.

연결 리스트는 데이터와 다음 데이터를 가리키는 주소가 결합되어 하나의 노드라고 부른다.

최초의 노드를 만들고

다음의 추가할 노드를 만든다.

그 후에 최초의 노드의 포인터에 추가할 노드의 데이터의 주소값을 가리키도록 한다.

연결 리스트에 있는 노드 들 중에 주소 값이 없는 노드가 있다면 그 노드가 마지막 노드일 수 있다.

class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
        
    def add(data):
        node = head
        
        while node.next:
            node = node.next
            
        node.next = Node(data)
        
    def insert(data, index):
        node = head
        insert_node = Node(data)
        
        for i in range(index-1):
            node = node.next
            
        insert_node.next = node.next
        node.next = insert_node
        
#         node_next = node.next
#         node.next = insert_node
#         insert_node.next = node_next

노드 등록, 추가, 삽입을 구현해보았다.

data와 주소값을 가지는 생성자를 만들었다. (주소 값을 넣지 않을 경우를 디폴트로)

add는 추가하고자 하는 노드를 가장 뒤에 만드는 메소드이다.

insert는 추가하고자 하는 노드를 기존에 있던 노드와 노드 사이에 넣고자 할 때 사용한다.

insert는 강의에서 본 것과는 다르게 나름대로 생각해서 연결 리스트의 인덱스를 기준으로 삽입할 수 있도록 구현해봤다.

주석 처리 한 부분은 

삽입하고자 하는 노드를 기존의 노드와 연결하는 코드인데, 강사님은 저것과 비슷한 방법으로 하셨다.

[기초-2차원배열] 성실한 개미

영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다.

왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데,
그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다.

개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다.
(오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.)

이에 호기심이 생긴 영일이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다.

미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지
오른쪽 또는 아래쪽으로만 움직였다.

미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고,
먹이가 2로 주어질 때, 성실한 개미의 이동 경로를 예상해보자.

단, 맨 아래의 가장 오른쪽에 도착한 경우, 더 이상 움직일 수 없는 경우, 먹이를 찾은 경우에는
더이상 이동하지 않고 그 곳에 머무른다고 가정한다.


미로 상자의 테두리는 모두 벽으로 되어 있으며,
개미집은 반드시 (2, 2)에 존재하기 때문에 개미는 (2, 2)에서 출발한다.

입력

10*10 크기의 미로 상자의 구조와 먹이의 위치가 입력된다.

출력

성실한 개미가 이동한 경로를 9로 표시해 출력한다.

입력 예시

1 1 1 1 1 1 1 1 1 1

1 0 0 1 0 0 0 0 0 1

1 0 0 1 1 1 0 0 0 1

1 0 0 0 0 0 0 1 0 1

1 0 0 0 0 0 0 1 0 1

1 0 0 0 0 1 0 1 0 1

1 0 0 0 0 1 2 1 0 1

1 0 0 0 0 1 0 0 0 1

1 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1

출력 예시

1 1 1 1 1 1 1 1 1 1

1 9 9 1 0 0 0 0 0 1

1 0 9 1 1 1 0 0 0 1

1 0 9 9 9 9 9 1 0 1

1 0 0 0 0 0 9 1 0 1

1 0 0 0 0 1 9 1 0 1

1 0 0 0 0 1 9 1 0 1

1 0 0 0 0 1 0 0 0 1

1 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1

width = 10
height = 10
box = [[0 for i in range(width)] for i in range(height)]

for i in range(height):

    temp = list(map(int, input().split()))

    for j in range(width):

        box[i][j] = temp[j]

i = 1
j = 1

while (box[i][j] != 2):

    if (box[i][j+1] != 1):

        box[i][j] = 9
        j += 1

    elif (box[i+1][j] != 1):

        box[i][j] = 9
        i += 1

    elif ((box[i+1][j] == 1) and (box[i][j+1] == 1)):
        break

box[i][j] = 9

for width in box:

    for status in width:

        print(status, end = " ")

    print("")

설명

좌표판의 크기를 변수에 선언해준다.

2차원 배열을 만들어준다.

입력값을 받아서 2차원 배열에 넣어준다.

while문에서 i와 j를 활용하기 위해 1로 선언해준다. 개미의 출발지가 (2,2)이기 때문에

좌표판에서는 1,1 이다. (리스트는 0부터 시작하기 때문)

while문의 조건을 개미가 먹이 위에 있을 때로 놓는다.

오른쪽 길이 열려있으면 개미는 반드시 오른쪽으로 가야하기 때문에

가장 최상위의 if에 오른쪽 길이 열렸는지 검증해주고 열려있다면 개미의 현재 위치를 9로 표시하고 j에 1을 더해주어

현재 위치에서 오른쪽으로 이동시켜준다.

2번째 elif는 만약 오른쪽이 막혔다면 아래쪽으로 이동하도록 해준다.

3번째 elif는 개미의 현재 위치에서 오른쪽도 아래쪽도 막힐 경우 제자리에 놔두기 위해서 break으로 while문을 나온 뒤

현재 위치에 9를 입력해준다.

이렇게 진행하다가 먹이를 발견시에는 while문의 조건에 의해 while문을 나오게 되고

먹이의 위치에 9를 입력할 수 있다.

조건에 맞게 출력해준다.

[기초-2차원배열] 설탕과자 뽑기

부모님과 함께 유원지에 놀러간 영일이는
설탕과자(설탕을 녹여 물고기 등의 모양을 만든 것) 뽑기를 보게 되었다.

길이가 다른 몇 개의 막대를 바둑판과 같은 격자판에 놓는데,

막대에 있는 설탕과자 이름 아래에 있는 번호를 뽑으면 설탕과자를 가져가는 게임이었다.
(잉어, 붕어, 용 등 여러 가지가 적혀있다.)

격자판의 세로(h), 가로(w), 막대의 개수(n), 각 막대의 길이(l),
막대를 놓는 방향(d:가로는 0, 세로는 1)과
막대를 놓는 막대의 가장 왼쪽 또는 위쪽의 위치(x, y)가 주어질 때,

격자판을 채운 막대의 모양을 출력하는 프로그램을 만들어보자.

입력

첫 줄에 격자판의 세로(h), 가로(w) 가 공백을 두고 입력되고,
두 번째 줄에 놓을 수 있는 막대의 개수(n)
세 번째 줄부터 각 막대의 길이(l), 방향(d), 좌표(x, y)가 입력된다.

입력값의 정의역은 다음과 같다.

1 <= w, h <= 100
1 <= n <= 10
d = 0 or 1
1 <= x <= 100-h
1 <= y <= 100-w

출력

모든 막대를 놓은 격자판의 상태를 출력한다.
막대에 의해 가려진 경우 1, 아닌 경우 0으로 출력한다.
단, 각 숫자는 공백으로 구분하여 출력한다.

입력 예시

5 5

3

2 0 1 1

3 1 2 3

4 1 2 5

출력 예시

1 1 0 0 0

0 0 1 0 1

0 0 1 0 1

0 0 1 0 1

0 0 0 0 1

풀이

h, w = map(int, input().split())
board = [[0 for i in range(w)] for j in range(h)]
n = int(input())

for i in range(n):
    l, d, x, y = map(int, input().split())
    
    for j in range(l):
        
        if (d == 0):
            board[(x - 1)][(y - 1)] = 1
            y += 1
            
        else:
            board[(x - 1)][(y - 1)] = 1
            x += 1
            
for width in board:
    
    for status in width:
        print(status, end = " ")
        
    print("")

설명

좌표판의 크기를 결정할 변수들을 받아 줍니다.

좌표판을 나타내는 2차원 배열을 선언해줍니다.

막대의 개수(n)를 입력 받아 for문에 활용해줍니다.

막대의 길이, 방향, 시작하는 좌표를 입력 받습니다.

막대의 방향에 따라서 y좌표와 x좌표를 증가시켜서 반복해줍니다.

출력 조건에 맞춰서 출력해줍니다.