Krafton_jungle 5기 10일차 TIL - 알고리즘 문제풀이, CS:APP

백준 문제풀이

 

1. 2740 행렬곱샙

혼자 2중for문으로 풀려다가 시간 다날리고 결국 풀이를 확인했다.

좀만 더 생각해보면 간단히 해결할 수 있는데 너무나도 아쉬운 문제.

 

2. 2468 안전 영역

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 1 = 강수량 1 ~ n+1
# 전체 탐색 시작
result = 0
def search_safe(result, max_value):
    for i in range(0, max_value + 1):
        visited = set()
        safe = 0
        for y in range(n):
            for x in range(n):
                safe += dfs(i, x, y, visited)
        result = max(result, safe)
    return result

# 시간날때 bfs로 풀어보기
# queue를 사용하면 됨

def dfs(i, x, y, visited):
    if x < 0 or n <= x or 0 > y or y >= n or (x,y) in visited or arr[y][x] <= i:
        return 0
    visited.add((x, y))
    # 동
    if x + 1 <= n:
        dfs(i, x + 1, y, visited)
    # 서
    if x - 1 >= 0:
        dfs(i, x - 1, y, visited)
    # 남
    if y - 1 >= 0:
        dfs(i, x, y - 1, visited)
    # 북
    if y + 1 <= n:
        dfs(i, x, y + 1, visited)
    return 1


n = int(input())
arr = list(list(map(int, input().split())) for _ in range(n))
max_value = max(max(row) for row in arr)
print(search_safe(result, max_value))

나같은 경우 dfs로 풀이했는데 queue로 푸는 방법이 있더라.

완전 탐색같은 경우 queue를 이용한 bfs로 탐색하는게 좀 더 효과적인 것 같다.

나중에 다시 풀어볼 예정

 

3. 8983 사냥꾼

사냥꾼 같은 경우에는 2개의 방법으로 문제에 접근했었다.

처음엔 사수의 위치를 기준으로 탐색하는 방법.

하지만 해당 방법엔 치명적인 문제점이 발견되어 바른 방법으로 풀이를 시도했다.

import sys
input = sys.stdin.readline


# 탐색 시작
# 사수의 위치, 사거리, 탐색 시작점(Y좌표), tmp
def binary_search(x, l):
    global tmp
    if len(n_list) == 0:
        return
    if l <= 0:
        return
    search_left(x-l)
    search_right(x+l)
    binary_search(x, l-1)  # 재귀 호출된 결과를 tmp에 할당
    return


def search_left(location):
    global tmp
    animals_found = [i for i in n_list if i[0] == location]
    for animal in animals_found:
        print(animal)
        n_list.remove(animal)
        tmp += 1

def search_right(location):
    global tmp
    animals_found = [i for i in n_list if i[1] == location]
    for animal in animals_found:
        print(animal)
        n_list.remove(animal)
        tmp += 1


# 사대의 수, 동물의 수, 사거리
m, n, l = map(int, input().split())
m_list = list(map(int, input().split()))
m_list.sort()
n_list = list()

# 동물의 위치 좌표
for i in range(n):
    x,y = map(int, input().split())
    # 사수의 사정거리에 속한 동물만 arr에 추가
    if y <= l:
        # 왼쪽 대각, 오른쪽 대각
        n_list.append((x-y, x+y))

result = 0

# 사대의 위치를 순회
for i in m_list:
    tmp = 0
    binary_search(i, l)
    result += tmp

print(result)

문제의 코드.

N-Queen과 같이 대각의 좌표값을 라벨링 해서 접근했는데 해당 방법은 어차피 모든 경우의 수를 탐색하는 방법과 다를 바 없고, 사거리 밖에 있음에도 같은 대각선에 위치해 범위에 포함되어 버리는 문제점이 발생했다.

 

이를 해결하기 위해 탐색의 기준을 사수의 위치에서 동물의 위치로 바꾸었다.

import sys
input = sys.stdin.readline


def search_m(animal_location, result):
    # 왼쪽, 오른쪽 유효 사거리 구하기
    left_effective_range = animal_location[0] + animal_location[1] - l
    right_effective_range = animal_location[0] - animal_location[1] + l
    # 사수가 배치되어있는 배열을 탐색할 기준
    left = 0
    right = len(m_list)-1
    # 모든 범위를 탐색할때까지
    while left <= right:
        mid = (left + right) // 2
        if left_effective_range <= m_list[mid] <= right_effective_range:
            result += 1
            break
        elif m_list[mid] < left_effective_range:
            left = mid + 1
        elif m_list[mid] > right_effective_range:
            right = mid - 1
    return result


# 사대의 수, 동물의 수, 사거리
m, n, l = map(int, input().split())
# 4수 리스트
m_list = list(map(int, input().split()))
m_list.sort()
# 동물 리스트
n_list = list()

result = 0

# 동물의 위치 좌표
for i in range(n):
    x,y = map(int, input().split())
    # 사수의 사정거리에 속한 동물만 arr에 추가
    if y <= l:
        n_list.append((x, y))

for i in n_list:
    result = search_m(i, result)

print(result)

이게 정답코드

동물이 피격당하는 사수의 위치 범위를 구하고 탐색하는 방식으로 풀이함.

 

오늘은 난이도 상 문제밖에 남지 않아 문제를 푸는데 상당한 시간을 써야했다. 넘 어려웡

 

 

CS:APP

 

1.5  캐시가 중요하다.

인스트럭션의 실행	hello 프로그램의 기계어 인스트럭션들은 본래 하드에 저장되있고, 프로그램이 로딩될 때 메모리에 올린다. 프로레서가 프로그램 실행시 메모리에서 프로세서로 올림. 마찬가지로 데이터 스트링도 디스크에 저장되어 있다가 메인 메모리를 거쳐 디스플레이 장치로 복사된다. 이런 복사과정은 실제 작업을 느리게 하는 오버헤드를 발생시킨다.
저장장치	물리학의 법칙에 따라 더 큰 저장장치들은 보다 작은 저장장치들보다 느린 속도를 갖는다. 그리고 작고 빠른 저장장치들은 더 비쌈 디스크 드라이브는 메인 메모리보다 용량이 훨씬 크지만, 메인 메모리보다 훨씬 느리다. 이 격차를 보완하기 위해 시스템 설계자는 보다 작고 빠른 캐시 메모리라 부르는 저장장치를 고안해서 프로세서가 단기간에 필요할 가능성이 높은 정보를 임시로 저장한다.
캐시 메모리	L1, L2, L3 가 있으며, 숫자가 작을수록 더 빠른 속도를 제공한다. 캐시 메모리를 이해하면 성능을 10배 이상 개선할 수 있다.

 

 

 

1.6 저장장치들은 계층 구조를 이룬다.

메모리 계층구조

메모리의 계층구조

작고 빠른 저장장치를 프로세서와 좀 더 크고 느린 장치 사이에 끼워넣는 개념은 일반적인 아이디어다. 모든 컴퓨터 시스템의 저장장치는 다음과 같이 이뤄져있다.

 

 

 

1.7 운영체제는 하드웨어를 관리한다.

컴퓨터 시스템의 계층화 모습

운영체제에 의한 추상화

메모리 엑세스	쉘 프로그램이 hello 프로그램을 로드하고 실행했을 떄와 hello 프로그램이 메세지를 출력할 때 키보드나 디스플레이, 디스크나 메인 메모리를 직접 엑세스 하지 않고, 운영체ㅓ제가 제공하는 서비스를 활용한다
운영체제	하드웨어와 소프트 웨어 사이에 위치한 계층 운영 프로그램이 하드웨어를 제어하려면 OS(Operation system)가 필요하다.
운영체제의 목적	운영체제의 목적은 제멋대로 동작하는 응용프로그램들이 하드웨어를 잘못 사용하는 것을 막기 위함이 있고, 응용프로그램들이 단순하고 균일한 메커니즘을 사용하여 복잡하고 매우 다른 저수준 하드웨어 장치들을 조작할 수 있도록 하기 위해서이다. 운영체제는 이 두가지 목표를 위 그림과 같이 추상화를 통해 달성하고 있다. 프로세스, 가상메모리, 파일 이 그림이 보여주는 것 처럼 파일은 입출력장치의 추상화이고, 가상 메모리는 메인 메모리와 디스크 입출력 장치의 추상화, 그리고 프로세스는 프로세서, 메인메모리, 입출력 장치 모두의 추상화 결과이다.

 

 

오늘의 소감 

분할정복에 대한 개념을 다시 한번 잡고가야할 것 같다.

내일은 1주차 시험이 있는데 중급까지만 맞췄으면 좋겠다.