[TIL] 백준 코드 풀이 & Computer System

1. 백준 - 어려웠던 문제 정리 & 풀이 공부

1. N-Queen (9663번)

import sys

n = int(sys.stdin.readline())
# row 리스트에서 인덱스 = 행번호 / row[i] 값은 열번호
row = [0] * n
result = 0

# https://seongonion.tistory.com/103 참고
# https://lighter.tistory.com/m/26 참고

# 퀸을 놓을 수 있는 위치인지 여부 판단
def isPromising(x) :
    for i in range(x) :
        '''
        1. 같은 열에 있는지 확인
            row[x] == row[i] : x번 행과 i번 행에 놓여있는 퀸의 열 번호가 같은 경우
        2. 대각선에 존재하는지 확인
            row[x]-row[i] : 세로로 얼마만큼 갔는지
            x-i : 가로로 얼마만큼 갔는지
            위의 두 값이 같은 경우 대각선 상에 존재한다.
        '''
        if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i) :
            return False
    return True
    

# x = 행, row[x] = 열
def nQueens(x) :
    global result
    
    # x가 n이 되면 모든 행에 퀸이 채워졌다는 의미로 함수 종료
    if x == n : 
        result += 1
        return
    else :
        for i in range(n) :
            row[x] = i
            if isPromising(x) :
                nQueens(x+1)

nQueens(0)
print(result)

---

2. 외판원 순회2 (10971번)

1. DFS를 이용한 구현

import sys

N = int(sys.stdin.readline())
city = []
# 방문 여부 배열
visited = [False] * N

for i in range(N) :
    city.append(list(map(int, sys.stdin.readline().split())))

# 도시 순회 함수
# https://velog.io/@y7y1h13/알고리즘백준-10971번-외판원-순회-2python 참고

'''
start : 시작 도시
current : 현재 탐색하고 있는 도시
value : 현재까지 순회한 비용
count : 현재까지 탐색한 도시 수
'''
def dfs(start, current, value, count) :
    global result
    # 현재 도시가 마지막 도시라면
    if count == N :
        # 시작한 도시로 돌아간다.
        if city[current][start] :
            value += city[current][start]
            # 이미 저장된 탐색값보다 작을경우
            if result > value :
                result = value
        return
    # 이미 저장된 탐색값 보다 클 경우
    if value > result :
        return
    
    # 도시 수만큼 반복
    for i in range(N) :
        # 아직 탐색할 수 있는 도시가 남아있다면
        # 즉, 방문한 적이 없고 도시 비용이 0이 아닌 경우
        if not visited[i] and city[current][i] :
            visited[i] = True
            dfs(start, i, value + city[current][i], count + 1)
            visited[i] = False

result = sys.maxsize
# 도시마다 출발점 지정
for i in range(N) :
    visited[i] = True
    dfs(i, i, 0, 1)
    visited[i] = False
print(result)

2. 순열을 이용한 구현

import sys
from itertools import permutations

def main() :
    N = int(sys.stdin.readline())
    city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    result = sys.maxsize
    # 모든 도시들 사이에 비용이 존재한다는 가정하에 모든 루트 생성
    all_list = permutations(range(N))
    
    for root in all_list :
        sum = 0
        flag = True
        # 출발지부터 마지막 도착지까지
        for i in range(N-1):
            if city[root[i]][root[i+1]] != 0 :
                sum += city[root[i]][root[i+1]]
            else :
                flag = False
                break
        # 마지막 도착지에서 출발지 비용 더해주기
        if city[root[N-1]][root[0]] == 0 :
            flag = False
        # 모든 루트에서 비용이 존재했을 경우
        if flag :
            sum += city[root[N-1]][root[0]]
            result = min(result, sum)
    print(result)

main()

효율은 DFS를 이용한 풀이가 더 좋지만 공부할 겸 다른분이 푸신 순열을 이용한 방법을 사용해보았다.

---

3. 안전 영역 (2468번)

1. BFS를 사용한 내 풀이

import sys
from collections import deque

N = int(sys.stdin.readline())

array = []
'''
상하좌우 표현
x[0], y[0] = -1, 0 = 왼쪽
x[1], y[1] = 1, 0 = 오른쪽
x[2], y[2] = 0, -1 = 아래쪽
x[3], y[3] = 0, 1 = 위쪽
'''
x = [-1, 1, 0, 0]
y = [0, 0, -1, 1]

for i in range(N) :
    array.append(list(map(int, sys.stdin.readline().split())))

result = 0

# 물의 높이 제한 : 100이하의 정수
for height in range(101) :
    # 방문 여부 저장 배열
    visited = [[0] * N for i in range(N)]
    count = 0
    
    for j in range(N) :
        for k in range(N) :
            if array[j][k] > height and visited[j][k] == 0 :
                queue = deque()
                queue.append((j, k))
                visited[j][k] = 1
                
                # BFS 구현
                # queue 큐 = 선입선출 구조
                while queue:
                    a, b = queue.popleft()
                    for i in range(4) :
                        nx = a + x[i]
                        ny = b + y[i]
                        # 상하좌우 확인 + 범위 내인지 확인
                        if nx >= 0 and nx < N and ny >= 0 and ny < N :
                            if array[nx][ny] > height and visited[nx][ny] == 0 :
                                visited[nx][ny] = 1
                                queue.append((nx, ny))
                count += 1
    # 이미 다 잠겼을 경우 반복문 중지
    if count == 0:
        break
    result = max(result, count)
        
print(result)

2. DFS를 이용한 동료분의 풀이( - 주석 설명 추가)

import sys

# python 재귀함수 깊이 제한을 늘린다.
sys.setrecursionlimit(100000)

# 행과 열의 개수
N = int(sys.stdin.readline())

# 땅의 높이 저장 행렬
land = []
land = [list(map(int,input().split())) for i in range(N)]

# 상하좌우 확인을 위한 배열
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 최종 결과를 저장할 변수
result = 0

'''
x : 현재 시작 위치 x
y : 현재 시작 위치 y
h : 현재 물의 높이
'''
def dfs(x,y,h):
    # 물에 잠긴 구역이면
    # 방문 완료 표시 후 탐색 종료
    if h >= land[x][y]:
        check[x][y] = True
        return False
    
    # 물에 잠기지 않은 구역이면
    check[x][y] = True
    # 현재 위치에서 상하좌우 확인
    for i in range(4):
        nx,ny = x+dx[i] , y+dy[i]
        # 위치가 범위 내에 있고 방문한 적이 없으면
        if(0<= nx < N and 0<= ny < N and not check[nx][ny]):
            dfs(nx,ny,h)
    return True

# 입력 받은 땅의 높이 중 가장 높은 땅의 높이만큼 반복
for k in range(max(map(max, land))):
    # 확인한 장소인지 여부 판별 배열
    check = [[False]*N for i in range(N)]
    sum = 0
    for i in range(N):
        for j in range(N):
           if not check[i][j] and dfs(i,j,k):
               sum += 1
               
    # 안전영역의 개수가 더 많으면 변경
    if result < sum :
        result = sum
print(result)

이미 비슷한 문제를 푼 적이 있어서 바로 BFS를 사용하여 비슷하게 구현했었다. (7576번 - 토마토) + (내 풀이)
그런데 서로의 코드 리뷰를 해보니 그 중 DFS로 구현하신 분의 코드를 보았다.
내가 알기로는 기본적으로 BFS의 수행 속도가 DFS(재귀함수 방식) 보다 빠르다고 알고 있었다. 

1. 그래프의 모든 정점을 방문하는 것이 문제일 경우 : 두 가지 방법 중 어느 것을 사용해도 상관없다
2. 경로의 특징을 저장해둬야 하는 문제일 경우 : DFS
3. 최단거리를 구하는 문제일 경우 : BFS

 위의 경우에서 봤을 때 최단 거리를 구하는 문제인 경우와 비슷하다는 생각도 들어 당연히 내 코드가 빠를 줄 알았다.
그러나 서로의 실행 결과를 비교해보니 DFS가 좀 더 빠르게 나왔다. 

위의 두 코드 실행 결과

너무 이상해서 내가 잘못알고 있는건가 싶어서 인터넷을 찾아보고 했는데 다 BFS가 좀 더 빠르다고 일려주었다.
그래서 생각하다가 팀원분께서 python은 전역 변수에 접근할 때가 지역 변수에 접근할 때 훨씬 느리다는 것을 알려주신 것이 생각이 나서 각각의 코드를 main() 함수를 만들어서 넣어서 지역변수로 접근할 수 있게 만들었다.

main() 함수로 구현 후 실행 결과

import sys
from collections import deque

# 지역변수로 활용하기 위한 main() 함수 사용
def main():
    N = int(sys.stdin.readline())

    array = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
    '''
    상하좌우 표현
    x[0], y[0] = -1, 0 = 왼쪽
    x[1], y[1] = 1, 0 = 오른쪽
    x[2], y[2] = 0, -1 = 아래쪽
    x[3], y[3] = 0, 1 = 위쪽
    '''
    x = [-1, 1, 0, 0]
    y = [0, 0, -1, 1]

    result = 0

    # 입력받은 높이 중 가장 높은 것만큼만 반복
    for height in range(max(map(max, array))):
        # 방문 여부 저장 배열
        visited = [[0] * N for i in range(N)]
        count = 0

        for j in range(N):
            for k in range(N):
                if array[j][k] > height and visited[j][k] == 0:
                    queue = deque()
                    queue.append((j, k))
                    visited[j][k] = 1

                    # BFS 구현
                    '''
                    deque 사용 이유 : 시간복잡도 차이
                    list.pop(0) = O(n)
                    deque.popleft() = O(1)
                    위의 두 경우 모두 맨 앞의 원소를 꺼낸다.
                    '''
                    while queue:
                        a, b = queue.popleft()
                        for i in range(4):
                            nx = a + x[i]
                            ny = b + y[i]
                            # 상하좌우 확인 + 범위 내인지 확인
                            if nx >= 0 and nx < N and ny >= 0 and ny < N:
                                if array[nx][ny] > height and visited[nx][ny] == 0:
                                    visited[nx][ny] = 1
                                    queue.append((nx, ny))
                    # while문이 종료되었다는 의미는 영역 1개의 탐색을 완료했다는 의미
                    count += 1
        result = max(result, count)
    print(result)

main()

결과가 반전이 되었다. 위의 코드와 같이 DFS, BFS 모두 main() 함수를 사용하여 실행했다. 시간자체가 모두 확연히 줄었다.
나는 python은 간결하게 쓰기 좋다고 생각해서 함수를 만드는 습관을 들이지 않았었는데
이 일을 겪고 전역 변수와 지역 변수의 접근 속도가 이렇게 차이가 많이 난다는 것을 뼈저리게 깨닫고 반성했다.
그동안 다른 언어들로 프로그래밍을 배울 때에는 당연히 함수를 만들고 구조를 짜가면서 코드를 작성했는데
python이 편리하다는 이유로 그러지 않았다는 것에 놀랐다.
앞으로는 코드를 작성할 때 함수도 사용하며 코드를 좀 더 구조화하여 작성해야겠다.

전역변수와 지역변수의 속도 차이 : https://www.acmicpc.net/board/view/905

---

4. python 문법 주의 사항

(10819번 - 차이를 최대로) - 순열을 반복문으로 생성할 때 사용해보다가 알았다.

example = [1, 2, 3, 4, 5]

list1 = [example]
list2 = [example[:]]

print(list1)
print(list2)

위의 코드의 경우 둘다 list 안에 원소로 리스트를 넣어주고 있다.

코드 실행 결과

둘다 똑같이 들어간 것처럼 보여지지만 아래의 코드를 추가하고 출력해보면

example.append("add")

print(list1)
print(list2)

코드 실행 결과

list1 은 변경된 요소가 적용되어 있고 list2는 적용되어 있지 않는 모습을 볼 수 있다.

이때 중요한 것은 example이라는 리스트를 원소로 넣어줄 때 방식이다.

[example] 방식은 단순히 리스트 안에 example 리스트의 주솟값을 넣어주는 것과 같아 항상 값이 같다.

그러나 [example[:]] 방식은 example 리스트 속 모든 값을 복사한 리스트를 넣어주는 것이기 때문에 값이 변경될 수 없다.

(by 팀원분의 도움)

---

2. 컴퓨터 시스템 용어

1. bit(비트)

   : 정보의 최소단위 = 0 또는 1 (8bit = 1byte)

2. 파일

    1. Binary file : 텍스트 파일이 아닌 컴퓨터 파일

    2. Text file : 아스키(ASCII) 문자들로만 이루어진 파일

3. Context

   : 문맥 상황에 따라 어떤 해석이 가미되어 이해되는 한 차원 높은 공간

 

4. instruction

   : 컴퓨터에게 일을 시키는 단위, 기계어로 이루어져 있는 명령

5. Complie System

실행가능 목적 프로그램(object file) = 컴퓨터가 알아들을 수 있는 저급 기계어 인스트럭션들

    1. 전처리 단계 (Pre-Processor)

       : 헤더파일 등 필요한 프로그램 문장 삽입 

    2. 컴파일러 (Compiler)

       : 고급 언어 → 어셈블리어로 번역

    3. 어셈블러 (Assembler)

       : 어셈블리어 → 기계어로 번역 (relocatable object file)

    4. 링커 (Linker)

       : 사용한 라이브러리 중 별도의 목적 파일을 결합할 필요가 있는 경우 어셈블러 실행 결과 파일과 필요한 목적 파일을 결합

        최족적으로 Executable object file 생성 

6. 시스템 하드웨어 조직

컴퓨터 시스템 제3판

    1. 버스(Buses)

       : 시스템 내를 관통하는 전기적 배선군, 단위 = 워드(word)

    2. 입출력 장치(I/O)

       : 시스템과 외부세계와의 연결

    3. 메인 메모리

       : 프로세서가 프로그램을 실행하는 동안 데이터와 프로그램을 모두 저장하는 임시 저장장치

• DRAM(dynamic random access memory) : 일반적인 기억 장치로 전원이 끊어지면 저장된 자료가 바로 소멸되는 메모리

    4. 프로세서

       : CPU(주처리장치), 메인 메모리에 저장된 인스트럭션들을 해독(실행)하는 엔진

• 레지스터(Register) : 메모리와 유사하나, 훨씬 빠른 소규머 저장장치, CPU 내 임시 저장장치
• 프로그램 카운터(PC) : 다음 인출할 명령어 주소를 임시 저장하는 레지스터, 각 명령어 인출 후 1씩 증가
• 작업 종류
  • 적재(Load) : 메인 메모리→ 레지스터 로 덮어쓰는 방식으로 복사
  • 저장(Store) : 레지스터 → 메인 메모리 로 덮어쓰는 방식으로 복사
  • 작업(Operate) : 두 레지스터의 값을 수식/논리 처리기(ALU)로 복사하고 수식연산을 수행 후 다시 레지스터에 저장
  • 점프(Jump) : PC(Program Counter) 위치 조절

7. 저장 장치의 계층 구조

컴퓨터 시스템 제3판

   기본적으로 저장장치는 클수록 느린 속도를 갖고 가격이 싸다.

   여기서 속도는 메모리에서 복사해 오는과정을 말하는데 이 과정이 빠를수록 저장장치는 비싸진다.

   문제는 반도체 기술이 발달함에 따라 프로세서와 메모리 간의 속도 차이가 증가하고 있다.

   이 문제를 대응하기 위해 사용하는 개념이 캐시 메모리(Cache) 이다.

• 지역성(locality) : 캐시 시스템 이면에 깔려 있는 아이디어로
                              어떤 데이터가 참조되면 참조된 그 지역 및 시간 근처에서 다시 참조될 가능성이 높다는 원칙
  • 시간적 지역성(Temporal Locality) : 최근에 접근했던 데이터들을 프로세서 가까이에 위치
  • 공간적 지역성(Spatial Locality) : 최근에 접근했던 데이터와 인접한 데이터들을 블록화
• Register : 곧 바로 사용될 데이터의 기억을 위한 저장장치
• Cache : 보다 작고 빠른 저장장치로 프로세서가 단기간에 필요로 할 가능성이 높은 정보를 임시로 저장할 목적으로 사용
                CPU와 주기억 장치 사이에 버퍼 형태의 고속의 임시 저장장치
  • SRAM(static random access memory) : 전원이 공급되는 동안에는 일정하게 유지되는 반도체 메모리(휘발성)
• Main Memory : 가까운 시간 내에 사용될 데이터를 기억하기 위한 저장장치
• Secondary storage : 당장 필요하지 않는 대단위 데이터를 영구적으로 기억하기 위한 저장장치(비휘발성)

   메모리 계층 구조의 주요 아이디어는 즉, 한 레벨의 저장장치가 다음 하위 레벨 저장장치의 캐시 역할을 한다는 것이다.

8. 운영체제(Operating System)

   : 컴퓨터의 동작 전반을 운영/제어하는 소프트웨어

• OS 사용 목적
  • 컴퓨터의 능력을 사용자가 편리하고 효율적으로 활용할 수 있도록
  • 하드웨어가 높은 성능을 발휘할 수 있도록 관리
    • 응용프로그램이 하드웨어를 잘못 사용하는 것을 막기 위해
    • 응용프로그램들이 단순하고 균일한 매커니즘을 사용하여 복잡하고 매우 다른 저수준 하드웨어 장치들을 조작할 수 있도록
• 프로세스
  • 단위 실행 프로그램, 메모리에 올려져 실행중인 프로그램 
  • 실행 중인 프로그램에 대한 운영체제의 추상화 결과로 추상적인 존재이다.
  • 여러 프로세스들은 동일한 시스템에서 동시에 실행될 수 있으며, 각 프로세스는 하드웨어를 배타적으로 사용한다고 느낀다.
    • 동시에(=Concurrently) : 한 프로세스의 명령들이 다른 프로세스의 명령들과 섞인다는 의미
  • 즉, 운영체제는 한개의 프로그램이 모든 자원을 독차지 하고 있는 것처럼 느끼도록 만든다.
  • 문맥 전환(Context Switching) : 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(Context)를 보관하고 새로운 프로세스의 상태를 적재하는 작업
    • 프로세스 제어 블록(PCB, Process Control Block) : Context, PC, Register 등 정보 저장
    • System Call : 프로세스가 운영체제 커널에게 어떤 동작을 수행을 요청하는 것
    • kernel : 운영체제 코드의 일부분으로 메모리에 상주, 운영체제의 핵심적인 역할을 하는 부분
                   모든 프로세스를 관리하기 위해 시스템이 이용하는 코드와 자료 구조의 집합이다.
      • 시스템 콜을 통해 넘어온 제어권을 이용해 요청한 작업을 수행하고 응용프로그램으로 리턴

용어 참고 사이트 : http://www.ktword.co.kr/test/view/view.php?no=3609 

컴퓨터 구조

계속해서 컴퓨터 시스템에 대해 공부중이다. 확실히 두번째 보니까 더 이해할 수 있는 시간이다.