charge.log

Hadoop WordCount 오류 정리

Wed, 16 Nov 2022 06:34:41 GMT

Hadoop 설치 완료 후 발생한 오류

hdfs namenode -format 오류**

오류: JAVA_HOME is not set and could not be found

해결: hadoop/etc/hadoop의 hadoop-env.sh에서 JAVA_HOME 경로 설정 (경로 설정에서도 여러 번의 시도가 있었음)

2. jps 했을 때 5개가 아닌 1개만 보임

다음과 같이 ResourceManager만 나옴 원인: start-dfs.sh와 start-yarn.sh 할 때 오류가 발생했었음

3. dfs 실행시 아래와 같이 가 발생 오류: rcmd socket permission denied

해결: ~/.bashrc 에 export PDSH_RCMD_TYPE=ssh 추가 (시행착오)-> 그 후에도 똑같음 => source ~/.bashrc 통해 적용 했어야함

여기까지 했을 때 Namenode에서 오류가 났음을 볼 수 있음
4. namenode만 뜨지 않음

해결: bin 에서 hdfs namenode -format 다시 진행 -> sbin에서 stop-all.sh로 다 종료 시킨 후에 다시 실행

성공!

5. Wordcount를 실행하였을 때 output에 파일 형성되지 않음

이런 오류 뜨는거 같지만 output 폴더는 만들어짐 오류: could not find or load main class org.apache.hadoop.mapred.yarnchild => output 폴더가 비어있음. 잘 안된거지

해결: mapred-site.xml 에

넣어서 해결

=> 이렇게 하면 작은 사이즈의 데이터로는 wordcount 실행 가능

** 6. 672MB 크기 정도의 대용량 데이터 wordcount 실행하였을 때 오류 **

hadoop jar ./wordcount.jar WordCount /user/jiyeon/wordcount/input /user/jiyeon/wordcount/output

WordCount 실행 코드

원인: YARN이 컨테이너를 할당함으로써 각 애플리케이션에 처리 용량을 제공. 현재는 컨테이너에 메모리가 부족하여 YARN이 자동으로 컨테이너를 종료. 이로 인한 오류 발생. 오류: Container killed on request. Exit code is 137 해결: yarn-site.xml 파일에 다음을 추가


yarn.nodemanager.vmem-check-enabled
false

처음 추가하였을 때는 오류가 해결되지 않았어서 헤맸었음 stop-all.sh로 종료하고 start-all.sh로 다시 hadoop을 실행한 후 wordcount 작업을 하였더니 첨부한 것과 같이 문제 없이 mapreduce가 작동

Django

Sun, 13 Nov 2022 02:42:22 GMT

Django

Django는 파이썬으로 만들어진 무료 오픈소스 웹 애플리케이션 프레임워크 웹 사이트를 구축할 때 비슷한 요소들이 항상 필요하자 웹 개발자들은 바로 사용할 수 있는 구성요소들을 갖춘 프레임워크를 만들었고 그 중 하나가 Django임.

모델-뷰-컨트롤러(MVC) 패턴 따름 모델은 데이터에 관한 정보를 담고 있음 뷰는 어떤 데이터가 표시될 것인지를 정의 템플릿은 데이터가 어떻게 표시되는지를 정의

템플릿: 우리가 보는 html 화면이라 생각하면 된다 Django에서 템플릿을 띄워주는 과정은 다음과 같다.

URL로 요청 받아서 우리가 URL을 적어준 urls.py로 가서 해당 요청에 맞는 URL 분석
우리가 썼던 views 함수이름을 통해 해당 URL에 연결된 view로 가서 함수 찾아 기능 수행
view는 로직을 실행하며 데이텁이스 관련 처리는 model을 사용하여 결과 반환
마지막으로 view는 최종 결과로 templates(html파일)을 클라이언트에게 보내줌

Django 개발 환경 설정

명령 프롬포트 실행
원하는 폴더로 이동
$ django-admin start project blog 입력
프로젝트 폴더 내부로 이동
django가 사용할 데이터베이스 생성 migrate 하면 Splite3 파일 생성

프로젝트 실행 위해 서버 키기 $ python manage.py runserver

Django 내용 저장

Django에서는 Model을 이용해 게시판에서 각각의 게시글이 데이터베이스에 어떻게 저장될 지를 결정. => 예를 들어 게시글이라는 틀을 하나 만들면 그 틀을 이용해서 여러 가지 게시글을 만들고 이를 저장

Migrate

Django 공식 문서에는 migrate는 모델의 변경 내역을 DB 스키마에 적용시키는 방법이라 설명. 하나의 migration 파일은 해당 migration이 생성된 시점의 모델 구조를 담고 있음. ** 주의 각 migration은 이전 버전에 대해 의존성을 가지기 때문에 적용된 migration 파일은 절대로 삭제해서는 안된다. migration 파일을 삭제하려면 반드시 적용을 해제하고 삭제해야함

python manage.py makemigrations [app_name]

=> migration을 생성하는 명령어
프로젝트 생성 후 처음 migration을 생성할 때는 app_name 생략

python manage.py migrate [app_name][migration_name]

=> migration을 적용하는 명령어
이전 버전으로 되돌리는 것도 가능

Superuser

Django 프로젝트의 모든 앱과 object를 관리하는 계정 manage.py 통해 Superuser 생성 파이썬 터미널 창에서 작업

form 태그

html에서

태그는 내부의 정보를 한 번에 서버로 전송하는 역할. 이렇게 웹에서 정보를 서버에 전송할 때 주로 GET과 POST 방식으로 통신함

GET 방식은 원하는 데이터를 서버에 요청해서 받아오는 것. -> 주소창에 가져올 정보가 모두 표시되므로 중요한 정보는 GET을 사용하면 안됨.

POST 방식은 정보를 서버에 전송하여 서버 데이터베이스에 우리가 보낸 정보를 저장하는 방식.

csrf

사이트 간 요청 위조(cross-site request forgery)로 웹 애플리케이션의 취약점 중 하나. 사용자가 자신의 의지와 무관하게 공격자가 의도한 행동을 하며 특정 웹페이지를 보안에 취약하게 한다거나 수정, 삭제 등 작업을 하게 만드는 공격방법을 의미.

[백준 파이썬] 2637번 장난감 조립

Sat, 16 Jul 2022 04:33:02 GMT

그래프 이론

https://www.acmicpc.net/problem/2637

문제 우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다.

예를 들어보자. 기본 부품으로서 1, 2, 3, 4가 있다. 중간 부품 5는 2개의 기본 부품 1과 2개의 기본 부품 2로 만들어진다. 그리고 중간 부품 6은 2개의 중간 부품 5, 3개의 기본 부품 3과 4개의 기본 부품 4로 만들어진다. 마지막으로 장난감 완제품 7은 2개의 중간 부품 5, 3개의 중간 부품 6과 5개의 기본 부품 4로 만들어진다. 이런 경우에 장난감 완제품 7을 만드는데 필요한 기본 부품의 개수는 1번 16개, 2번 16개, 3번 9개, 4번 17개이다.

이와 같이 어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때 하나의 장난감 완제품을 조립하기 위하여 필요한 기본 부품의 종류별 개수를 계산하는 프로그램을 작성하시오.

입력 - 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. - 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주어지고, 그 다음 M개의 줄에는 어떤 부품을 완성하는데 필요한 부품들 간의 관계가 3개의 자연수 X, Y, K로 주어진다. 이 뜻은 "중간 부품이나 완제품 X를 만드는데 중간 부품 혹은 기본 부품 Y가 K개 필요하다"는 뜻이다. 두 중간 부품이 서로를 필요로 하는 경우가 없다.

출력 - 하나의 완제품을 조립하는데 필요한 기본 부품의 수를 한 줄에 하나씩 출력하되(중간 부품은 출력하지 않음), 반드시 기본 부품의 번호가 작은 것부터 큰 순서가 되도록 한다. 각 줄에는 기본 부품의 번호와 소요 개수를 출력한다.

정답은 2,147,483,647 이하이다.

입력예시
7 8 5 1 2 5 2 2 7 5 2 6 5 2 6 3 3 6 4 4 7 6 3 7 4 5

출력예시 1 16 2 16 3 9 4 17

** sol) 위상정렬 알고리즘 이용. **

먼저 입력을 받아 장난감 부품중 기본 부품을 따로 구분해서 큐에 넣어주고 기본 부품부터 순회를 시작
연결된 상위 부품의 개수를 계산하기 때문에 필요로 하는 하부 부품들의 개수를 하부 부품들을 만들 때 드는 개수에 곱해서 더해줌
그 뒤는 기본적인 위상정렬과 비슷하게 방문했다면 진입 차수 하나 줄인다. 그 뒤 진입 차수가 0인 장난감 부품을 방문
최종 부품을 만드는데 드는 기본 부품들의 개수 출력

from collections import deque

n = int(input())  # 완제품 번호 n 입력 받기
m = int(input())
indegree = [0] * (n+1)  # 모든 노드에 대한 진입차수는 0으로 초기화
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(n+1)]
# 각 제품을 만들때 필요한 부품
needs = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(m):  # 방향 그래프의 모든 간선 정보를 입력받기
    x, y, k = map(int, input().split())  # x를 만드는데 y가 k개 필요
    graph[y].append((x, k))
    indegree[x] += 1  # 진입 차수 1 증가

def topology_sort():  # 위상 정렬 함수
    result = []  # 알고리즘 수행 결과를 담을 리스트
    q = deque()  # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)
            needs[i][i] = 1  # 기본 부품만 시작값을 1로 할당

    while q:  # 큐가 빌 때까지 반복
        now = q.popleft()  # 큐에서 원소 꺼내기
        result.append(now)
        for i in graph[now]:  # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            for j in range(1, n+1):
                needs[i[0]][j] += i[1]*needs[now][i]
                print(needs[i[0]][j])
            indegree[i] -= 1
            if indegree[i] == 0:  # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                q.append(i[0])
    for i in range(1, n+1):
        if needs[n][i]:
            print(result[i])

topology_sort()

[코딩테스트] 그래프 이론

Fri, 15 Jul 2022 15:58:22 GMT

그래프 이론

Review

크루스칼 알고리즘: 그리디 알고리즘으로 분류
위상 정렬 알고리즘: 큐 자료구조 또는 스택 자료구조 활용해야 구현 가능

'서로 다른 개체가 연결되어 있다'라는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올리자.

서로소 집합

서로소 집합(Disjoint Sets): 공통 원소가 없는 두 집합

서로소 집합 자료구조

: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

union 연산: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find 연산: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

서로소 집합 자료구조 (=union-find 자료구조) => 두 집합이 서로소 관계인지를 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다는 말

서로소 집합 자료구조 구현

트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘

union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. 1) A와 B의 루트 노드 A', B'을 각각 찾는다. 2) A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다.)
모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

def find_parent(parent, x): # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        return find_parent(parent, parent[x]) # 루트 노드 찾을 때까지 재귀 호출
    return x

def union_parent(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for i in range(e):  # union연산 각각 수행
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print('각 원소가 속한 집합: ', end='')  # 각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

print()

print('부모 테이블: ', end='')  # 부모 테이블 내용 출력
for i in range(1, v+1):
    print(parent[i], end=' ')

find 함수를 다음과 같이 변경하면 경로 압축 기법의 구현 가능

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

개선된 서로소 집합 알고리즘 코드

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

def union_parent(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for i in range(e):  # union연산 각각 수행
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print('각 원소가 속한 집합: ', end='')  # 각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

print()

print('부모 테이블: ', end='')  # 부모 테이블 내용 출력
for i in range(1, v+1):
    print(parent[i], end=' ')

서로소 집합 알고리즘의 시간 복잡도

노드 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때 경로 압축 방법을 적용한 시간 복잡도 $$O(V+M(1+log_{2-M/V}V))$$

서로소 집합을 활용한 사이클 판별

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용 가능 간선을 하나씩 확인하면서 두 노드가 포합되어 있는 집합을 합치는 과정을 반복하여 사용

각 간선을 확인하며 두 노드의 루트 노드를 확인한다. 1) 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다. 2) 루트 노드가 서로 같다면 사이클이 발생한 것이다.
그래프에 포함되어있는 모든 간선에 대하여 1번 과정을 반복한다.

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

def union_parent(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)  # 부모 테이블 초기화

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

cycle = False  # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break  # 종료
    else:  # 사이클이 발생하지 않았다면
        union_parent(parent, a, b)  # union 연산 수행

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

크루스칼 알고리즘

신장 트리 (Spanning tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함

크루스칼 알고리즘 (Kruskal Algorithm) : 대표적인 최소 신장 트리 알고리즘. 이를 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있음. 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않는다.

간선 데이터를 비용에 따라 오름차순으로 정렬한다.
간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
모든 간선에 대하여 2번 과정을 반복한다.

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

def union_parent(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)  # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for _ in range(e):  # 모든 간선에 대한 정보를 입력받기
    a, b, cost = map(int, input().split())
    # 비용 순으로 정렬하기 위해 튜플의 첫번쨰 원소를 비용으로 설정
    edges.append((cost, a, b))

edges.sort()  # 간선을 비용순으로 정렬

for edge in edges:  # 간선을 하나씩 확인
    cost, a, b = edge
    # 사이클이 발생하지 않은 경우에만
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)  # union 연산 수행 (집합에 포함)
        result += cost

print(result)

크루스칼 알고리즘 시간 복잡도

간선의 개수가 E개일 때, $$O(ElogE)$$의 시간 복잡도를 가짐 -> 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업

위상 정렬

위상 정렬 (Topology Sort): 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

알고리즘

진입차수가 0인 노드를 큐에 넣는다.
큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

from collections import deque

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
indegree = [0] * (v+1)  # 모든 노드에 대한 집입차수는 0으로 초기화
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v+1)]

for _ in range(e):  # 방향 그래프의 모든 간선 정보를 입력받기
    a, b = map(int, input().split())
    graph[a].append(b)  # 정점 A에서 B로 이동 가능
    indegree[b] += 1  # 진입 차수 1 증가

def topology_sort():  # 위상 정렬 함수
    result = []  # 알고리즘 수행 결과를 담을 리스트
    q = deque()  # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:  # 큐가 빌 때까지 반복
        now = q.popleft()  # 큐에서 원소 꺼내기
        result.append(now)
        for i in graph[now]:  # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            indegree[i] -= 1
            if indegree[i] == 0:  # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                q.append(i)

    for i in result:  # 위상 정렬을 수행한 결과 출력
        print(i, end=' ')

topology_sort()

위상 정렬 시간 복잡도

$$O(V+E)$$

실전문제

Ex1) 팀 결성

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.

'팀 합치기' 연산은 두 팀을 합치는 연산이다.
'같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.

입력조건 - 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 $\leq$ N,M $\leq$ 100,000) - 다음 M개의 줄에는 각각의 연산이 주어진다. - '팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다. - '같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산이다. - a와 b는 N 이하의 양의 정수이다.

출력조건 - '같은 팀 여부 확인' 연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

*sol) 서로소 집합 알고리즘 문제 N,M의 범위가 모두 최대 100,000이므로 경로 압축 방식의 서로소 집합 자료구조 이용하여 시간 복잡도 계산 *

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

def union_parent(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split())
parent = [0] * (n+1)  # 부모 테이블 초기화

for i in range(1, n+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for i in range(m):  # 각 연산을 하나씩 확인
    oper, a, b = map(int, input().split())
    if oper == 0:  # union 연산인 경우
        union_parent(parent, a, b)
    if oper == 1:  # find 연산인 경우
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

Ex2) 도시 분할 계획

동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대로 회의 중이었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 론자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들을 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

입력조건 - 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. (2 $\leq$ N $\leq$ 100,000 , 1 $\leq$ M $\leq$ 1,000,000) - 그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집과 B번 집을 연결하는 유지비가 C(1 $\leq$ C $\leq$ 1,000) 라는 뜻이다.

출력조건 - 첫째 줄에 길을 없애고 남은 유지비의 합의 최솟값을 출력한다.

*sol) 전체 그래프에서 2개의 최소 비용 신장 트리를 만들어야함. -> 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거함. => 이렇게 되면 최소 신장 트리가 2개의 부분 그래프로 나누어짐. *

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

def union_parent(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)  # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for _ in range(e):  # 모든 간선에 대한 정보를 입력받기
    a, b, cost = map(int, input().split())
    # 비용 순으로 정렬하기 위해 튜플의 첫번쨰 원소를 비용으로 설정
    edges.append((cost, a, b))

edges.sort()  # 간선을 비용순으로 정렬
last = 0  # 최소 신장 트리에 포함되는 간선 중 가장 비용이 큰 간선

for edge in edges:  # 간선을 하나씩 확인
    cost, a, b = edge
    # 사이클이 발생하지 않은 경우에만
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)  # union 연산 수행 (집합에 포함)
        result += cost
        last = cost

print(result - last)

Ex3) 커리큘럼

동빈이는 온라인으로 컴퓨터공학 강의를 듣고 있다. 이때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 예를 들어 '알고리즘' 강의의 선수 강의로 '자료구조'와 '컴퓨터 기초'가 존재한다면, '자료구조'와 '컴퓨터 기초'를 모두 들은 이후에 '알고리즘' 강의를 들을 수 있다. 동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N=3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 있고, 1번과 2번 강의는 선수 강의가 없다고 가정하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자.

1번 강의: 30시간
2번 강의: 20시간
3번 강의: 40시간

이 경우 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 강의를 수강하기까지의 최소 시간은 20시간, 3번 강의를 수강하기까지의 최소 시간은 70시간이다. 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.

입력조건 - 첫째 줄에 동빈이가 듣고자 하는 강의의 수 N (1 $\leq$ N $\leq$ 500)이 주어진다. - 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분한다. 이때 강의 시간은 100,000 이하의 자연수이다. - 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝난다.

출력조건 - N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다 .

*sol) 위상 정렬 알고리즘 사용 각 강의에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있음. => 위상 정렬을 수행하면서, 매번 간선 정보를 확인하여 결과 테이블 갱신 *

from collections import deque
import copy

v = int(input())  # 노드 개수 입력 받기
indegree = [0] * (v+1)  # 모든 노드에 대한 집입차수는 0으로 초기화
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v+1)]
time = [0] * (v+1)  # 각 강의 시간을 0으로 초기화

for i in range(1, v+1):  # 방향 그래프의 모든 간선 정보를 입력받기
    data = list(map(int, input().split()))
    time[i] = data[0]  # 첫번째 수는 시간 정보를 담고 있음
    for x in data[1:-1]:
        indegree[i] += 1
        graph[x].append(i)

def topology_sort():  # 위상 정렬 함수
    result = copy.deepcopy(time)  # 알고리즘 수행 결과를 담을 리스트
    q = deque()  # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:  # 큐가 빌 때까지 반복
        now = q.popleft()  # 큐에서 원소 꺼내기
        for i in graph[now]:  # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            result[i] = max(result[i], result[now] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:  # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                q.append(i)

    for i in range(1, v+1):  # 위상 정렬을 수행한 결과 출력
        print(result[i])

topology_sort()

각 강의를 수강하기까지 최소 시간을 result 리스트에 담음
각 강의 시간은 time 리스트에 담겨있는데, 위상 정렬 함수 초기 부분에서 deepcopy() 함수
이용하여 time 리스트의 변수 값 복사하여 result 리스트 변수의 값으로 설정하는 작업이 수행.
리스트의 경우, 단순히 대입 연산을 하면 값이 변경될 때 문제가 발생할 수 있으므로 
리스트의 값을 복제해야할 때는 deepcopy() 함수 이용하자

기출문제

Q43 어두운 길

한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요.

입력조건 - 첫째 줄에는 집의 수 N (1 $\leq$ N $\leq$ 200,000)과 도로의 수 M (N-1 $\leq$ M $\leq$ 200,000)이 주어집니다. - 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X,Y,Z가 주어지며, 공백으로 구분합니다. (0 $\leq$ X,Y $<$ N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미입니다. 단, X와 Y가 동일한 경우는 없으며, 마을을 구성하는 모든 도로의 길이 합은 $2^{31}$보다 작습니다.

출력조건 - 첫째 줄에 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력합니다.

*sol) 가로등이 켜진 도로만을 이용해서, 모든 두 집이 서로 도달이 가능해야한다는 조건이 제시되어있음. 이때 최소한의 비용으로 모든 집을 연결해야 하기 때문에 최소 신장 트리 알고리즘 사용. (그래프에서 각 노드가 서로 연결되어 있는 연결 그래프와 같음) => 크루스칼 알고리즘 사용하여 '전체 가로등을 켜는 비용-최소 신장 트리 구성 비용'의 출력값을 구한다. *

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

def union_parent(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (n+1)  # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

for i in range(1, n+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for _ in range(m):  # 모든 간선에 대한 정보를 입력받기
    x, y, z = map(int, input().split())
    # 비용 순으로 정렬하기 위해 튜플의 첫번쨰 원소를 비용으로 설정
    edges.append((z, x, y))

edges.sort()  # 간선을 비용순으로 정렬
total = 0  # 전체 가로등 비율

for edge in edges:  # 간선을 하나씩 확인
    cost, a, b = edge
    total += cost
    # 사이클이 발생하지 않은 경우에만
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)  # union 연산 수행 (집합에 포함)
        result += cost

print(total-result)

입력

출력

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

[백준 파이썬] 17182번 우주 탐사선

Sat, 09 Jul 2022 07:20:27 GMT

최단 경로

https://www.acmicpc.net/problem/17182

문제 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

입력 - 첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N) - 다음 N 줄에 걸쳐 각 행성 간 이동 시간 $$T_{ij}$$ 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ $$T_{ij}$$ ≤ 1000)

출력 - 모든 행성을 탐사하기 위한 최소 시간을 출력한다.

입력예시1
3 0 0 30 1 1 0 29 28 1 0

출력예시1 2

입력예시2
4 1 0 83 38 7 15 0 30 83 67 99 0 44 14 46 81 0

출력예시2 74

** sol) 플로이드-워셜 알고리즘 이용 (N 범위가 크지 않고, 방문한 행성 중복도 가능하므로 이를 사용하는 것이 유리) 점화식: $$D_{ij} = min(D_{ij},~~ D_{ik}+D_{kj})$$ **

import sys

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, k = map(int, input().split())  # 행성 개수, 행성 위치 입력 받기
# 2차원 리스트 행성 간 이동시간 입력받기
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

visit = [False] * n
visit[k] = True
result = INF

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n):
    for i in range(1, n):
        for j in range(1, n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

def find_min(curr, count, cost):
    global result
    if count == n:
        result = min(result, cost)
        return
    for i in range(n):
        if not visit[i]:
            visit[i] = True
            find_min(i, cost + graph[curr][i], count + 1)
            visit[i] = False

find_min(k,1,0)
print(result)

[코딩테스트] 최단 경로

Sat, 09 Jul 2022 06:01:31 GMT

최단 경로

: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

보통 그래프를 이용해 표현, 각 지점은 '노드', 지점간 연결된 도로는 '간선'
코딩테스트에서 주로 단순히 최단 거리를 출력하도록 요구
그리디 알고리즘, 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용되는 특징

다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm)

: 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

다익스트라 알고리즘 원리

출발 노드를 설정한다.
최단 거리 테이블을 초기화한다.
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
위 과정에서 3과 4번을 반복한다.

특징

음의 간선을 표현되지 않으므로 GPS 소프트웨어의 기본 알고리즘으로 채택
기본적으로 그리디 알고리즘으로 분류 => 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정 반복
최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트(=최단 거리 테이블)에 저장하며 리스트 갱신
매번 현재 처리하고 있는 노드를 기준으로 주변 간선 확인
방문하지 않은 노드 중 현재 최단 거리가 가장 짧은 노드 확인
한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾음

간단한 다익스트라 알고리즘

시간 복잡도: $$O(V^2)$$ ($$V$$: 노드 개수)
총 $$O(V)$$번에 걸쳐서 최단 거리 가장 짧은 노드 매번 선형 탐색, 현재 노드와 연결된 노드 매번 일일이 확인
처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트 선언 그 후 단계마다 '방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)

import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
start = int(input())  # 시작 노드 번호 입력 받기
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
visited = [False] * (n+1)  # 방문한 적이 있는지 체크하는 목적의 리스트 만들기
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    a,b,c = map(int, input().split())
    graph[a].append((b,c))  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0  # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    distance[start] = 0  # 시작 노드에 대해서 초기화
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    for i in range(n-1):  # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:  # 현재 노드와 연결된 다른 노드를 확인
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:  
                distance[j[0]] = cost

dijkstra(start)  # 다익스트라 알고리즘 수행

for i in range(1, n+1):  # 모든 노드로 가기 위한 최단 거리 출력
    if distance[i] == INF:  # 도달할 수 없는 경우
        print("INFINITY")  # 무한이라고 출력
    else:  # 도달할 수 있는 경우
        print(distance[i])  # 거리 출력

입력되는 데이터 수가 많다는 가정하에 파이썬 내장 함수인 input()을 더 빠르게 동작하는 
sys.std.realine()으로 치환하여 사용
모든 리스트는 (노드의 개수+1)의 크기로 할당
노드의 번호를 인덱스로 하여 바로 리스트 접근 가능

입력

출력

개선된 다익스트라 알고리즘

노드의 개수 및 간선의 개수가 많을 때 사용
시간 복잡도: $$O(ElogV)$$ ($$V$$: 노드 개수, $$E$$: 간선 개수)
힙 자료구조 사용
특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리 => 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빨리 찾기 가능
현재 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐 추가 이용
거리 짧은 노드 선택할 때 우선순위 큐에서 그냥 노드를 꺼내면 된다.
우선순위 큐에서 노드 꺼낸 뒤 해당 노드를 이미 처리한 적 있다면 무시, 아직 처리하지 않은 노드에 대해서만 처리.
'최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체

힙 자료구조

힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 사용
우선순위 큐: 우선순위가 가장 높은 데이터를 가장 먼저 삭제
PriorityQueue 또는 heapq 사용
우선순위 큐 라이브러리에 데이터 묶음 넣으면 첫 번째 원소를 기준으로 우선순위 설정
최소 힙 이용: 값이 낮은 데이터가 먼저 삭제 최대 힙 이용: 값이 큰 데이터가 먼저 삭제
파이썬 라이브러리에서는 기본적으로 최소 힙 구조 이용 (최소 힙을 최대 힙처럼 사용하기 위해 우선순위에 해당하는 값에 (-) 부호를 붙여 넣었다가 우선순위 큐에서 꺼낸 다음에 다시 (-) 부호 붙여 원래 값으로
우선순위 큐에서 데이터 개수가 $$N$$개일 때 힙 자료구조를 이용하면 전체 시간 복잡도: $$O(NlogN)$$

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
start = int(input())  # 시작 노드 번호 입력 받기
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    a,b,c = map(int, input().split())
    graph[a].append((b,c))  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0  # 시작 노드에 대해서 초기화

    while q:  # 큐가 비어있지 않다면
        dist, now = heapq.heappop(q)  # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        if distance[now] < dist:  # 현재 노드가 이미 처리된 적 있는 노드면 무시
            continue
        for i in graph[now]:  # 현재 노드와 연결된 다른 입접한 노드들 확인
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)  # 다익스트라 알고리즘 수행

for i in range(1, n+1):  # 모든 노드로 가기 위한 최단 거리 출력
    if distance[i] == INF:  # 도달할 수 없는 경우
        print("INFINITY")  # 무한이라고 출력
    else:  # 도달할 수 있는 경우
        print(distance[i])  # 거리 출력

=> 한 번 처리된 노드는 처리되지 않음

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용되는 알고리즘

단계마다 거쳐 가는 노드를 기준으로 알고리즘 수행
매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요 없음
시간 복잡도: $$O(N^3)$$
다이나믹 프로그래밍
노드의 개수가 N개일 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신
점화식: $$D_{ab} = min(D_{ab},~~ D_{ak}+D_{kb})$$ => 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교해서 더 작은 값으로 갱신
'바로 이동하는 거리'가 특정한 노드를 거쳐서 이동하는 거리'보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n = int(input())  # 노드 수 입력 받기
m = int(input())  # 간선 수 입력 받기

# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c  # a번 노드에서 b번 노드로 가는 비용이 c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:  # 도달할 수 없는 경우
            print("INFINITY", end=" ")
        else:  # 도달할 수 있는 경우
            print(graph[a][b], end=" ")  # 거리 출력
    print()

입력

출력

실전문제

Ex1) 미래도시

방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해있으며, X번 방문해 물건을 판매하고자 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 방문 판매원 A는 1번 회사에 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표이다. 이 때 방문 판매원 A는 가능한 한 빠르게 이동하고자 한다. 방문 판매원이 회사 사이를 이동하게 되는 최서 시간을 계산하는 프로그램을 작성하시오. 이때 소개팅의 상대방과 커피를 마시는 시간을 고려하지 않는다고 가정한다. 예를 들어 N=5, X=4, K=5이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있을 때를 가정할 수 있다.

(1번, 2번), (1번, 3번), (1번, 4번), (2번, 4번), (3번, 4번), 
(3번, 5번), (4번, 5번)

이 때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1번-3번-5번-4번)으로 설정하면, 소개팅에 참석할 수 있으면서 총 3만큼의 시간으로 이동할 수 있다. 따라서 이 경우 최소 이동시간은 3이다.

입력조건 - 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다. (1 $\leq$ N,M $\leq$ 100) - 둘째 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다. - M+2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다. (1 $\leq$ K $\leq$ 100)

출력조건 - 첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다. - 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

*sol) 플로이드-워셜 알고리즘 사용 (N 범위가 한정적이므로 이를 사용하는 것이 유리) 1번 노드에서 X를 거쳐 K로 가는 최단 거리 = (1번 노드에서 X까지 최단거리) + (X에서 K까지의 최단 거리) *

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split())  # 노드 수, 간선 수 입력 받기
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    a, b = map(int, input().split())
    # A와 B가 서로에게 가는 비용은 1이라 설정
    graph[a][b] = 1
    graph[b][a] = 1

# 거쳐갈 노드 X, 최종 목적지 노드 K 입력 받기
x, k = map(int, input().split())

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
distance = graph[1][k] + graph[k][x]

if distance >= INF:  # 도달할 수 없는 경우
    print("-1")
else:  # 도달할 수 있는 경우
    print(distance)  # 거리 출력

Ex2) 전보

어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메세지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.

입력조건 - 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다. (1 $\leq$ N $\leq$ 30,000, 1 $\leq$ M $\leq$ 200,000, 1 $\leq$ C $\leq$ N) - 둘째 줄부터 M+1번째 줄에 걸쳐서 통로에 대한 정보 X, Y, Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메세지가 전달되는 시간이 Z라는 의미다.

출력조건 - 첫째 줄에 도시 C에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.

*sol) 다익스트라 알고리즘 사용 (한 도시에서 다른 도시까지의 최단 거리로 치환 가능) N,M의 범위가 충분히 크므로 우선순위 큐를 이용하여 다익스트라 알고리즘 작성 *

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m, start = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    x,y,z = map(int, input().split())
    graph[x].append((y,z))  # z번 노드에서 y번 노드로 가는 비용이 z라는 의미

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0  # 시작 노드에 대해서 초기화

    while q:  # 큐가 비어있지 않다면
        dist, now = heapq.heappop(q)  # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        if distance[now] < dist:  # 현재 노드가 이미 처리된 적 있는 노드면 무시
            continue
        for i in graph[now]:  # 현재 노드와 연결된 다른 입접한 노드들 확인
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)  # 다익스트라 알고리즘 수행

count = 0  # 도달할 수 있는 노드 개수
max_distance = 0  #도달할 수 있는 노드 중, 가장 멀리 있는 노드와의 최단 거리
for d in distance:
    if d != INF:  # 도달할 수 있는 경우
        count += 1
        max_distance = max(max_distance, d)

# 시작 노드는 제외해야하므로 count-1 출력
print(count-1, max_distance)

기출문제

Q40 숨바꼭질

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1~N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 헛간으로 도달이 가능한 형태로 주어집니다. 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하시오.

입력조건 - 첫째 줄에는 N과 M이 공백으로 구분하여 주어집니다. (2 $\leq$ N $\leq$ 20,000), (1 $\leq$ M $\leq$ 50,000) - 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다. (1 $\leq$ A,B $\leq$ N)

출력조건 - 첫째 줄에는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러 개면 가장 작은 헛간 번호를 출력합니다), 두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야 합니다.

*sol) 다익스트라 알고리즘을 이용하여 1번 헛간으로부터 다른 모든 노드로의 최단 거리를 계산한 뒤 가장 최단 거리가 긴 노드를 찾는다. *

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split()) # n:노드 개수, m: 간선 개수 입력받기
start = 1  # 시작 노드를 1번 헛간으로 설정
graph = [[] for i in range(n+1)]  # 각 노드에 연결되어 있는 노드 정보 담는 리스트
distance = [INF] * (n+1)  # 최단 거리 테이블을 모두 무한으로 초기화

for _ in range(m):  # 모든 간선 정보 입력 받기
    a, b = map(int, input().split())
    # a번 노드와 b번 노드의 이동 비용이 1 (양방향)
    graph[a].append((b,1))
    graph[b].append((a, 1))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0  # 시작 노드에 대해서 초기화

    while q:  # 큐가 비어있지 않다면
        dist, now = heapq.heappop(q)  # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        if distance[now] < dist:  # 현재 노드가 이미 처리된 적 있는 노드면 무시
            continue
        for i in graph[now]:  # 현재 노드와 연결된 다른 입접한 노드들 확인
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)  # 다익스트라 알고리즘 수행

max_node = 0  # 최단 거리가 가장 먼 노드 번호 (동빈이가 숨을 헛간의 번호)
max_distance = 0  #도달할 수 있는 노드 중, 최단 거리가 가장 먼 노드와의 최단 거리
result = []  # 최단 거리가 가장 먼 노드와의 최단 거리와 동일한 최단 거리를 가지는 노드들의 리스트

for i in range(1, n+1):
    if max_distance < distance[i]:
        max_node = i
        max_distance = distance[i]
        result = [max_node]
    elif max_distance == distance[i]:
        result.append(i)

print(max_node, max_distance, len(result))

입력

출력

4 2 3

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

[백준 파이썬] 16401번 과자 나눠주기

Sat, 02 Jul 2022 13:23:34 GMT

이진 탐색

https://www.acmicpc.net/problem/16401

문제 다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다. 모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

입력 - 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. - 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.

출력 - 첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.

입력예시1
5 ABCD 145C A A910 Z321

출력예시1 A ABCD Z321 145C A910

입력예시2
4 34H2BJS6N PIM12MD7RCOLWW09 PYF1J14TF FIPJOTEA5

출력예시2 FIPJOTEA5 PYF1J14TF 34H2BJS6N PIM12MD7RCOLWW09

** sol) **

m, n = map(int, input().split())  #m:조카수, n:과자수 입력받기
snack_len = list(map(int, input().split()))

start = 1
end = max(snack_len)
result = 0

while start <= end:
    mid = (start + end) // 2
    count = 0
    for l in snack_len:
        count += l // mid
    if count >= m:
        result = max(result, mid)
        start = mid + 1
    else:
        end = mid - 1
print(result)

[백준 파이썬] 1149번 RGB거리

Sat, 02 Jul 2022 12:52:59 GMT

다이나믹 프로그래밍

https://www.acmicpc.net/problem/1149

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력 - 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. - 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력 - 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

입력예시1 출력예시1 3 96 26 40 83 49 60 57 13 89 99

입력예시2 출력예시2 3 3 1 100 100 100 1 100 100 100 1

입력예시3 출력예시3 6 208 30 19 5 64 77 64 15 19 97 4 71 57 90 86 84 93 32 91

** sol) 두번째 부터는 집이 연속된 색상을 가지지 말아야하므로 현재의 rgb[i][0](i번째 집을 빨강으로 칠했을 때) rgb[i-1][1]과 rgb[i-1][2] 중 작은 값을 넣어 구한다. 이를 초록, 파랑 집에도 똑같이 적용 => 결국 이 중 최솟값 선택**

n = int(input())
rgb = []  #빨강, 초록, 파랑으로 칠하는 비용에 대한 리스트

for i in range(n):  #n개의 집에 대해 빨강, 초록, 파랑으로 칠하는 비용 입력 받기
    rgb.append(list(map(int, input().split())))

for i in range(1, len(rgb)):
    #0은 빨강, 1은 초록, 2은 파랑
    rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) + rgb[i][0]  #i번째 집을 빨강으로 칠했을 때의 최솟값
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]  #i번째 집을 초록으로 칠했을 때의 최솟값
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]  #i번째 집을 파랑으로 칠했을 때의 최솟값

print(min(rgb[n - 1][0], rgb[n - 1][1], rgb[n - 1][2]))

[백준 파이썬] 1431 시리얼 번호

Sat, 02 Jul 2022 12:38:51 GMT

정렬 알고리즘

https://www.acmicpc.net/problem/1431

시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

출력 - 첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.

입력예시1
5 ABCD 145C A A910 Z321

출력예시1 A ABCD Z321 145C A910

입력예시2
4 34H2BJS6N PIM12MD7RCOLWW09 PYF1J14TF FIPJOTEA5

출력예시2 FIPJOTEA5 PYF1J14TF 34H2BJS6N PIM12MD7RCOLWW09

** sol) 각 시리얼의 리스트를 만들어서 입력 받는다. 리스트의 원소를 정렬할 때 sort() 함수의 key 속성에 값을 대입하여 원하는 조건에 맞게 튜플 정렬 시킨다. key=lambda x:(len(x),sum(int(a) for a in x if a.isnumeric()))**

n = int(input())
num = []  #시리얼 정보를 담을 리스트

for i in range(n):
    num.append(input())

num.sort()
num.sort(key=lambda x:(len(x),sum(int(a) for a in x if a.isnumeric())))

for k in num:
    print(k)

[코딩테스트] 다이나믹 프로그래밍

Sat, 02 Jul 2022 11:59:17 GMT

다이나믹 프로그래밍

: 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

중복되는 연산을 줄이자

피보나치 수열

n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

-> 이는 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어남 -> 이미 한 번 계산했지만 계속 호출될 때마다 계산 -> 시간 복잡도 $$O(2^N)$$

다이나믹 프로그래밍 사용 전제 조건

큰 문제를 작은 문제로 나눌 수 있다.
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션(Memoization) 기법

: 다이나믹 프로그래밍 구현 방법 중 하나, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 (= 캐싱)

구현 : 한 번 구한 정보를 리스트에 저장하고 필요할 때 이미 구현된 정답을 그대로 가져옴

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

#피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    if x == 1 or x == 2:  #종료 조건 (1 또는 2일 때 1 반환)
        return 1
    if d[x] != 0:  #이미 계산한 적 있는 문제라면
        return d[x]  #그대로 반환

    #아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))

출력결과

218922995834555169026

다이나믹 프로그래밍: 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 (문제들이 서로 영향을 미침) -> 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결, 이는 이미 해결된 것이기 때문에 다시 해결하지 않고 반환 -> 다이나믹 프로그래밍 사용했을 때 피보나치 수열 알고리즘 시간 복잡도: $$O(N)$$

# 호출되는 함수 확인용 피보나치 수열 함수
d = [0] * 100

#피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:  #종료 조건 (1 또는 2일 때 1 반환)
        return 1
    if d[x] != 0:  #이미 계산한 적 있는 문제라면
        return d[x]  #그대로 반환

    #아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

fibo(6)

출력결과

f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

탑다운(Top-Down) 방식

: 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법, 큰 문제를 해결하기 위해 작은 문제를 호출 => 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현

보텀업(Bottom-Up) 방식

: 단순히 반복문을 이용하여 소스코드를 작성하는 방법, 작은 문제부터 차근차근 답 도출 -> 여기서 사용되는 결과 저장용 리스트: 'DP 테이블' => 다이나믹 프로그래밍은 전형적인 보텀업 방식

# 앞서 계산된 결과 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현 (보텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

출력결과

218922995834555169026

실전문제

Ex1) 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

X가 5로 나누어떨어지면, 5로 나눈다.

X가 3으로 나누어떨어지면, 3으로 나눈다.

X가 2로 나누어떨어지면, 2로 나눈다.

X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수와 최솟값을 출력하시오.

입력조건 - 첫째 줄에 정수 X가 주어진다. (1 $\leq$ X $\leq$ 30,000)

출력조건 - 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

*sol) $$a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5})+1$$ 점화식을 토대로 보텀업 다이나믹 프로그래밍 구현 *

x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

# 다이나믹 프로그래밍 진행 (보텀업)
for i in range(2, x+1):
    d[i] = d[i-1] +1  #현재 수에서 1을 빼는 경우
    if i % 2 == 0:  #현재의 수가 2로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i//2]+1)
    if i % 3 == 0:  #현재의 수가 3로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i//3]+1)
    if i % 5 == 0:  #현재의 수가 5로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i//5]+1)

print(d[x])

Ex2) 개미 전사

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량을 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야한다. 예를 들어 식량 창고 4개가 다음과 같이 존재한다고 가정하자. {1 ,3 ,1, 5} 이 때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량 창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있ㄴ느 식량의 최댓값을 구하는 프로그램을 작성하시오.

입력조건 - 첫째 줄에 식량창고의 개수 N이 주어진다. (3 $\leq$ N $\leq$ 100) - 둘째 줄에 공백으로 구분되어 각 식량 창고에 저장된 식량의 개수 K가 주어진다. (0 $\leq$ K $\leq$ 1,000)

출력조건 - 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

**sol) 왼쪽부터 차례대로 식량창고를 털지 안털지를 결정하는 경우와 특정한 i번째 식량창고에 대해서 털지 안털지의 여부를 결정할 때, 2가지를 생각한다.

(i-1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 없다.
(i-2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있다. 이 둘 중 더 많은 식량을 털 수 있는 경우 선택 $$a_i = max(a_{i-1}, a_{i-2}+k_i)$$ 보텀업 방식 사용

n = int(input())
array = list(map(int, input().split()))  #모든 식량정보 입력받기

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
    d[i] = max(d[i-1], d[i-2] + array[i])

print(d[n-1])

Ex3) 바닥 공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다.

입력조건 - 첫째 줄에 N이 주어진다. (1 $\leq$ N $\leq$ 1,000)

출력조건 - 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

**sol) 타일링 문제 유형, 796,796으로 나눈 나머지를 출력하기 때문에 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 함 왼쪽부터 차례대로 바닥을 덮개로 채운다 생각

왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 2x1의 덮개를 채우는 하나의 경우 밖에 존재하지 않는다.
왼쪽부터 i-2까기 길이가 덮개로 이미 채워져 있으면 1x2의 덮개 2개를 넣는 경우, 혹은 2x2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다. $$a_i = a_{i-1} + a_{i-2}*2$$ 보텀업 방식 사용

n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n+1):
    d[i] = (d[i-1] + 2 * d[i-2]) % 796796

print(d[n])

Ex4) 효율적인 화폐 구성

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것도 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력조건 - 첫째 줄에 N, M이 주어진다. (1 $\leq$ N $\leq$ 100, 1 $\leq$ M $\leq$ 10,000) - 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

출력조건 - 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다. - 불가능할 때는 -1을 출력한다.

*sol) 그리디의 거스름돈 문제와 유사하지만 항상 화폐의 단위가 작은 단위의 배수는 아님 다이나믹 프로그래밍 이용하여 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾는다. 금액 $$i$$를 만들 수 있는 최소한의 화폐 개수 $$a_i$$, 화폐의 단위 $$k$$라 했을 때 * ($$a_{i-k}$$는 금액 ($$i-k$$)를 만들 수 있는 최소한의 화폐 개수) *1. $$a_{i-k}$$를 만드는 방법이 존재하는 경우=> $$a_i = min(a_i, a_{i-k}+1)$$ 2. $$a_{i-k}$$를 만드는 방법이 존재하지 않는 경우=> $$a_i=10,001$$ 해당 점화식을 모든 화폐 단위에 대하여 적용 가장 먼저 K 크기의 리스트 할당하고 각 인덱스를 금액으로 고려하여 메모이제이션 진행 *

n, m = map(int, input().split())
array = []
for i in range(n):  #N개의 화폐 단위 정보 입력 받기
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m+1)

# 다이나믹 프로그래밍 진행 (보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m+1):
        if d[j-array[i]] != 10001:  #(i-k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j-array[i]]+1)

if d[m] == 10001:  #최종적으로 M원 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

기출문제

Q32 정수 삼각형

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습입니다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하세요. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있습니다. 삼각형의 크기는 1 이상 500 이하입니다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 그 값의 범위는 0 이상 9999 이하입니다.

입력조건 - 첫째 줄에 삼각형의 크기 n (1 $\leq$ n $\leq$ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어집니다.

출력조건 - 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력합니다.

sol) 특정 위치에 도달하기 위해 왼쪽 위 또는 오른쪽 위 2가지 위치에서만 내려올 수 있음 => 모든 위치를 기준으로 이전 위치로 가능한 2가지 위치까지의 최적의 합 중 더 큰 합 가지는 경우 선택 dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i-1][j]) *단, dp 테이블에 접근해야 할 때마다 리스트의 범위를 벗어나지 않는지 체크 *

n = int(input())
dp = []  #다이나믹 프로그래밍을 위한 DP 테이블 초기화

for _ in range:
    dp.append(list(map(int, input().split())))

# 다이나믹 프로그래밍으로 두 번째 줄부터 내려가면서 확인
for i in range(1, n):
    for j in range(i+1):
        if j == 0:  #왼쪽 위에서 내려오는 경우
            up_left = 0
        else:
            up_left = dp[i-1][j-1]
        if j == i:  #오른쪽 위에서 내려오는 경우
            up_right = 0
        else:
            up_right = dp[i-1][j]
        dp[i][j] = dp[i][j] + max(up_left, up_right)  #최대 합 저장

print(max(dp[n-1]))

입력

출력

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

[코딩테스트] 이진탐색

Fri, 01 Jul 2022 17:03:00 GMT

이진 탐색 (Binary Search)

: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

순차탐색 (Sequential Search)

: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

보통 정렬되지 않은 리스트에서 데이터 찾아야할 때 사용
리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있음
리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사 => 구현 간단
순차 탐색이 사용되는 예
리스트에 특정 값의 원소가 있는지 확인할 때
리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드 이용할 때
데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차탐색의 최악의 경우 시간 복잡도는 $$O(N)$$

#순차 탐색 코드 구현
def sequential_search(n, target, array):
    for i in range(n): #각 원소를 하나씩 확인
        if array[i] == target:  #현재의 원소가 찾고자 하는 원소와 동일할 경우
            return i + 1  #현재의 위치 반환

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0])  #원소의 개수
target = input_data[1]  #찾고자 하는 문자열

print("앞서 적은 원소의 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

print(sequential_search(n, target, array))

<결과>
생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.
5 dongbin
앞서 적은 원소의 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.
hanul joggu dongbin taeil sangwook
3

이진탐색: 반으로 쪼개며 탐색

배열 내부의 데이터가 정렬되어 있어야만 사용 가능한 알고리즘
탐색 범위를 절반씩 좁혀가며 데이터를 탐색
위치를 나타내는 변수 3개 사용: 시작점, 끝점, 중간점
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
한 번 확인할 때마다 확인하는 원소의 개수가 절반으로 줄어듦
시간 복잡도: $$O(logN)$$

재귀함수 이용 코드

# 이진탐색 코드 (재귀함수)
def binary_search(array, target, start, end):
    if start > end:  #정렬 안되어있는 경우
        return None
    mid = (start + end) // 2
    if array[mid] == target:  #찾은 경우
        return mid  #중간점 인덱스 반환
    elif array[mid] > target: #중간점의 값보다 target이 작은 경우
        return binary_search(array, target, start, mid-1)  #왼쪽 확인
    else: #중간점의 값보다 target이 큰 경우
        return binary_search(array, target, mid+1, end) #오른쪽 확인

n, target = list(map(int, input().split())) #n:원소 개수, target: 찾고자 하는 문자열
array = list(map(int, input().split()))  #전체 원소 입력받기

result = binary_search(array, target, 0, n-1)  #이진탐색 수행 결과 출력
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)

반복문 이용 코드

# 이진탐색 코드 (반복문)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:  #찾은 경우
            return mid  #중간점 인덱스 반환
        elif array[mid] > target: #중간점의 값보다 target이 작은 경우
            end = mid-1  #왼쪽 확인
        else: #중간점의 값보다 target이 큰 경우
            start = mid+1 #오른쪽 확인
    return None

n, target = list(map(int, input().split())) #n:원소 개수, target: 찾고자 하는 문자열
array = list(map(int, input().split()))  #전체 원소 입력받기

result = binary_search(array, target, 0, n-1)  #이진탐색 수행 결과 출력
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)

<결과>
10 7
1 3 5 7 9 11 13 15 17 19
4

<결과>
10 7
1 3 5 6 9 11 13 15 17 19
원소가 존재하지 않습니다.

트리 자료구조

노드와 노드의 연결로 표현 (노드란 정보의 단위)
트리는 부모 노드와 자식 노드의 관계로 표현
트리의 최상단 노드를 루트 노드
트리의 최하단 노드를 단말 노드
트리에서 일부를 떼어내도 트리 구조이며 이를 서브트리라 함
트리는 파일 시스템과 같이 계층적이고 정렬된 데이터 다루기 적합

이진탐색 트리

이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
부모 노드보다 왼쪽 자식 노드가 작다.
부모 노드보다 오른쪽 자식 노드가 크다. => 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

빠르게 입력 받기

이진탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편 -> 입력 데이터 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려 시간 초과로 오답 판정 받을 수 있음. => 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수 이용

#한 줄 입력받아 출력하는 코드
import sys
input_data = sys.stdin.readline().rstrip(). #하나의 문자열 데이터 입력받기

print(input_data) #입력받은 문자열 그대로 출력

sys 라이브러리 사용할 때, 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야함.
readline()을 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 
이 공백 문자를 제거하기 위해 rstrip() 함수 사용해야함.

실전문제

Ex1) 부품 찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이 때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

입력조건 - 첫째 줄에 정수 N이 주어진다. (1 $\leq$ N $\leq$ 1,000,000) - 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이 때 정수는 1보다 크고 1,000,000 이하이다. - 셋째 줄에는 정수 M이 주어진다.(1 $\leq$ M $\leq$ 100,000) - 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이 때, 정수는 1보다 크고 1,000,000 이하이다.

출력조건 - 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

sol 1) 다량의 데이터 검색은 이진 탐색 알고리즘 이용 -> N개의 부품을 번호 기준으로 정렬, 그 후 M개의 찾고자 하는 부품이 각각 매장에 존재하는지 검사 => 이 때, 매장의 부품들은 정렬이 되어있기 때문에 이진 탐색 가능 -> 이 때, 최악의 경우 시간 복잡도 $$O((M+N) * logN)$$

이진 탐색 이용 코드

# 이진 탐색 코드 구현 (반복문)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:  # 찾은 경우
            return mid  # 중간점 인덱스 반환
        elif array[mid] > target:  # 중간점의 값보다 target이 작은 경우
            end = mid - 1  # 왼쪽 확인
        else:  # 중간점의 값보다 target이 큰 경우
            start = mid + 1  # 오른쪽 확인
        return None

    n = int(input())  #N(가게의 부품 개수) 입력
    array = list(map(int, input().split())) #가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
    array.sort()  #이진 탐색 수행 위해 사전에 정렬 수행
    m = int(input())  # M(손님이 확인 요청한 부품 개수) 입력
    x = list(map(int, input().split()))  #손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력

    for i in x: #손님이 확인 요청한 부품 번호를 하나씩 확인
        result = binary_search(array, i, 0, n-1)
        # 해당 부품이 존재하는지 확인
        if result != None:
            print("yes", end=' ')
        else:
            print("no", end=' ')

sol 2) 계수 정렬 이용 -> 모든 원소의 버호를 포함할 수 있는 크기의 리스트를 만든 후 리스트의 인덱스에 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인

계수 정렬 이용 코드

n = int(input())  #N(가게의 부품 개수) 입력
array = [0] * 1000001

#가게에 있는 전체 부품 번호를 입력받아서 기록
for i in input().split():
    array[int(i)] = 1

m = int(input())  # M(손님이 확인 요청한 부품 개수) 입력
x = list(map(int, input().split()))  #손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력

for i in x:  # 손님이 확인 요청한 부품 번호를 하나씩 확인
    # 해당 부품이 존재하는지 확인
    if array[i == 1:
        print("yes", end=' ')
    else:
        print("no", end=' ')

sol 3) 단순히 특정한 수가 한 번이라도 등장했는지 검사 => 집합 자료형 이용 집합 자료형은 단순히 특정한 데이터가 존재하는지 검사할 때 매우 효과적 (set() 함수는 집합 자료형을 초기화 할 때 사용)

집합 자료형 이용 코드

n = int(input())  #N(가게의 부품 개수) 입력
array = set(map(int, input().split())) #가게에 있는 전체 부품 번호를 공백으로 구분하여 입력

m = int(input())  # M(손님이 확인 요청한 부품 개수) 입력
x = list(map(int, input().split()))  #손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력

for i in x:  # 손님이 확인 요청한 부품 번호를 하나씩 확인
    if i in array:
        print("yes", end=' ')
    else:
        print("no", end=' ')

Ex2) 떡볶이 떡 만들기

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어, 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm익다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력조건 - 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 $\leq$ N $\leq$ 1,000,000, 1 $\leq$ M $\leq$ 2,000,000) - 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력조건 - 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

sol) 이진탐색 문제, 파라메트릭 서치(Parametric Search) 유형의 문제 적절한 높이를 찾을 때까지 절단기 높이 H를 반복해서 조정 -> '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 후 조건의 만족 여부에 따라 탐색 범위를 좁혀서 해결 (범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩) => 시작점을 0, 끝점을 가장 긴 떡의 길이로 설정한후 중간점을 초기의 H로 설정 이 때, 필요한 떡 길이보다 크면 시작점을 증가시킨다. 이를 반복 만약, 필요한 떡의 길이보다 작다면 끝점을 감소시킨다. => 중간값은 시간이 지날수록 '최적한 값'을 찾는다.

파라메트릭 서치: 최적화 문제를 결정 문제로 바꾸어 해결 => '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에서 주로 사용

#떡의 개수(N)와 요청한 떡의 길이(M)을 입력받기
n, m = list(map(int, input().split(' ')))
array = list(map(int, input().split()))  #각 떡의 개별 높이 정보 입력받기

#이진 탐색을 위한 시작점, 끝점 설정
start = 0
end = max(array)

#반복문 이용하여 이진탐색 수행
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        if x > mid:  #잘랐을 때의 떡의 양 계산
            total += x - mid
    if total < m: #떡의 양이 부족한 경우
        end = mid - 1 #더 많이 자르기(왼쪽 부분 탐색)
    else: #떡의 양이 충분한 경우
        result = mid #최대한 덜 잘랐을 때가 답이므로 여기에서 result에 기록
        start = mid + 1  #덜 자르기(오른쪽 부분 탐색)

print(result)

기출문제

Q28 고정점 찾기

고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2] = 2이므로, 고정점은 2가 됩니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 한 개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다. 단, 이 문제는 시간 복잡도 $$O(logN)$$으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력조건 - 첫째 줄에 N이 입력됩니다.. (1 $\leq$ N $\leq$ 1,000,000) - 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. ($$-10^9$$ $\leq$ 각 원소의 값 $\leq$ $$10^9$$)

출력조건 - 고정점을 출력한다. 고정점이 없다면 -1을 출력한다.

sol) 시간 복잡도 $$O(logN)$$를 만족시키기 위해 이진 탐색 사용. (이미 정렬 완료) '찾고자 하는 값'이 '중간점'과 동일하다 가정하고 탐색 수행 => 중간점이 가르키는 위치보다 중간점이 작을 때 왼쪽 탐색, 중간점이 클 때 오른쪽 탐색

#이진 탐색 코드 구현 (재귀 함수)

def binary_search(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == mid: #고정점 찾은 경우
        return mid  #인덱스 반환
    elif array[mid] > mid:  #중간점이 가르키는 위치의 값보다 중간값이 작은 경우
        return binary_search(array, start, mid-1)  #왼쪽 탐색
    else:  #중간점이 가르키는 위치의 값보다 중간값이 큰 경우
        return binary_search(array, mid+1, end)  #오른쪽 탐색

n = int(input())
array = list(map(int, input().split()))

index = binary_search(array, 0, n-1)

if index == None: #고정점이 없는 경우
    print(-1)
else:  #고정점이 있는 경우
    print(index)  #해당 인덱스 출력

입력 출력

5                                     3
-15 -6 1 3 7

입력 출력

7                                    -1
-15 -4 3 8 9 12 15

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

[코딩테스트] 정렬

Fri, 01 Jul 2022 02:42:54 GMT

정렬 (Sorting)

: 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘

정렬 알고리즘으로 데이터 정렬하면 이진 탐색이 가능 (이진탐색의 전처리 과정)
'알고리즘의 효율성' 이해 가능

선택 정렬

: 데이터가 무작위로 여러 개가 있을 때, 이 중 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 => 매번 '가장 작은 것'을 선택

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] #스와프

print(array)

스와프: 특정 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

#인덱스 0과 인덱스 1의 원소 교체하기
array = [3,5]
array[0], array[1] = array[1], array[0]

print(array)

선택 정렬의 시간 복잡도: $$O(N^2)$$
2중 반복문 사용

삽입 정렬

: 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입 -> 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬 되어있다고 가정. 정렬 되어있는 데이터 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    for j in range (i, 0, -1): #인덱스의 i부터 1까지 감소하며 반복
        if array[j] < array [j-1]: 
            array[j], array[j-1] = array[j-1], array[j] #한 칸씩 왼쪽으로 이동
        else: #자기보다 작은 데이터를 만날 때
            break #그 위치에서 멈춤

print(array)

삽입 정렬의 시간 복잡도: $$O(N^2)$$
2중 반복문 사용

퀵 정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작 -> 피벗 사용
피벗: 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'
피벗을 어떻게 설정할 것인지에 따라 퀵 정렬 구분
퀵 정렬은 재귀 함수 형태로 작성했을 때 구현 간결
퀵 정렬 끝나는 조건: 현재 리스트의 데이터 개수가 1개일 때
이는 이미 정렬 되어있다고 간주, 분할 불가능

호어 분할 (Hoare Partition) : 리스트의 첫 번째 데이터를 피벗으로 설정 -> 왼쪽에서 부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터 찾기 -> 그 다음, 큰 데이터와 작은 데이터의 위치를 서로 교환 => 이 결과는 피벗에 대한 정렬

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end:  #원소가 1개인 경우
        return  #종료
    pivot = start  #피벗은 첫 번째 원소
    left = start + 1
    right = end

    while left <= right:
        #피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right: #엇갈렸다면
            array[right], array[pivot] = array[pivot], array[right] #작은데이터와 피벗 교체
        else: #엇갈리지 않았다면 
            array[left], array[right] = array[right], array[left]  # 작은데이터와 큰 데이터 교체

    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

python의 장점을 살린 퀵 정렬

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1:  #리스트가 하나 이하의 원소만을 담고 있다면
        return array  #종료
    pivot = array[0]  #피벗은 첫번째 원소
    tail = array[1:]  #피벗을 제외한 리스트 tail

    left_side = [x for x in tail if x <= pivot]  #분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]  # 분할된 오른쪽 부분

    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

퀵 정렬의 시간 복잡도: $$O(NlogN)$$

계수 정렬

: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

계수 정렬의 시간 복잡도: $$O(N +K)$$ (데이터 개수: $$N$$, 데이터 중 최댓값: $$K$$)
계수 정렬의 공간 복잡도: $$O(N +K)$$
일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음
먼저, 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트 생성
처음에는 리스트의 모든 데이터가 0이 되도록 초기화

그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴 => 결과적으로 리스트에는 각 데이터에 몇 번 등장했는지 횟수 기록

#모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5 ,9, 0, 3, 1, 6, 2, 9, 1, 4, 8,  0, 5, 2]
#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0]*(max(array)+1)

for i in range(len(array)): count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): #리스트에 기록된 정렬 정보 확인 for j in range(count[i]): print(i, end=' ') #띄어쓰기를 구분으로 드앙한 횟수만큼 인덱스 출력




### 파이썬 정렬 라이브러리
- sorted() : 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어짐
-> sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력 받아 결과 출력
```python
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
print(result)

sort(): 리스트 변수가 하나 있을 때, 내부 원소 바로 정렬
별도의 정렬된 리스트가 반환되지 않고, 내부 원소가 바로 정렬
```
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
```

array.sort() print(array)


- key 매개변수 활용
-> key 값으로 하나의 함수가 들어가야하며 이는 정렬의 기준
```python
array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)

정렬 라이브러리 시간 복잡도: $$O(NlogN)$$

코딩테스트에서 정렬 알고리즘이 사용되는 경우

정렬 라이브러리로 풀 수 있는 문제: 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있음
정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 풀 수 있음
더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용해서 문제에서 기존의 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있음

실전문제

Ex1) 위에서 아래로

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

sol) 기본적인 정렬 가능한지 묻는 문제, 수의 개수가 적기 때문에 어떠한 정렬 알고리즘 사용해도 무방 but 코드가 간결해지는 파이썬 기본 정렬 라이브러리 사용하는 것이 효과적

입력조건 - 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 $\leq$ N $\leq$ 500) - 둘째 줄부터 N+1번째 줄까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다.

출력조건 - 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다.

n = int(input())  #N 입력 받기

array = []
for i in range(n):  #N개의 정수 입력 받아 리스트에 저장
    array.append((int(input())))

#파이썬 기본 정렬 라이브러리 이용하여 정렬 수행
array = sorted(array, reverse=True) 

for i in array:
    print(i, end=' ')  #정렬이 수행된 결과 출력

Ex2) 성적이 낮은 순서로 학생 출력하기

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

sol) 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 $$O(NlogN)$$을 보장하는 알고리즘 또는 $$O(N)$$을 보장하는 계수정렬 이용 학생 정보를 (이름, 점수)로 묶은 뒤 점수를 기준으로 정렬 수행 -> 파이썬 튜플 문법 이용하여 파이썬 기본 정렬 라이브러리 이용하는 것이 효과적

입력조건 - 첫째 줄에 학생의 수 N이 입력된다. (1 $\leq$ N $\leq$ 100,000) - 둘째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

출력조건 - 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

n = int(input())  #N 입력 받기

array = []
for i in range(n):  #N명의 학생 정보 입력 받아 리스트에 저장
    input_data = input().split()
    #이름은 문자열 그대로, 점수는 정수형을 변환하여 저장
    array.append((input_data[0], int(input_data[1])))

#키를 이용하여 정수를 기준으로 정렬
array = sorted(array, key = lambda student: student[1])

for student in array:
    print(student[0], end=' ')  #정렬이 수행된 결과 출력

Ex3) 두 배열의 원소 교체

동빈이는 두 개의 배열 A, B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다. N, K 그리고 배열 A, B의 정보가 주어졌을 때, 최대 K번 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

*sol) 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체 -> 단, 배열 A에서 가장 작은 원소가 배열 B에서의 가장 큰 원소보다 작을 때에만 교체 수행 가능. 이러한 과정을 K번 반복 배열 A의 원소를 오름차순으로 정렬, 배열 B의 원소를 내림차순으로 정렬 ->두 배열의 원소를 가장 첫 번째 인덱스부터 차례로 비교하여 A의 원소가 B의 원소보다 작을 때에만 교체 수행. 두 배열의 원소가 최대 100,000개까지 입력 가능 ->$$O(NlogN)$$ 보장하는 정렬 알고리즘 사용 *

입력조건 - 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1 $\leq$ N $\leq$ 100,000, 0$\leq$K$\leq$N) - 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다. - 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.

출력조건 - 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

n, k = map(int, input().split())  #N,K 입력 받기
a = list(map(int,  input().split())) #배열 A 모든 원소 입력 받기
b = list(map(int,  input().split())) #배열 B 모든 원소 입력 받기

a.sort()  #배열 A 오름차순 정렬
b.sort(reverse=True)  #배열 B 내림차순 정렬

for i in range(k): #첫번째 인덱스부터 두 배열의 원소를 최대 K번 비교
    if a[i] < b[i]: #A의 원소가 B의 원소보다 작을 경우
        a[i], b[i] = b[i], a[i] #두 원소 교체
    else: #A의 원소가 B의 원소보다 크거나 같을 때
        break  #반복문 탈출

print(sum(a))  #배열 A의 모든 원소의 합 출력

기출문제

Q23 국영수

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어집니다. 이 때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

국어점수가 감소하는 순서로

국어 점수가 같으면 영어 점수가 증가하는 순서로

국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로

모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞으로 옵니다)

*sol) 학생 정보를 튜플을 원소로 하는 리스트로 만들고 리스트를 정렬한다. 리스트의 원소를 정렬할 때 sort() 함수의 key 속성에 값을 대입하여 원하는 조건에 맞게 튜플 정렬 시킨다. sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0])) *

입력조건 - 첫째 줄에 도현이네 반의 학생 수 N이 입력됩니다. (1 $\leq$ N $\leq$ 100,000) - 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어집니다. - 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수입니다. - 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않습니다.

출력조건 - 문제에 나와 있는 정렬 기준으로 정렬한 후 첫째줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력합니다.

n = int(input())  #N 입력 받기
students = []  #학생 정보를 담을 리스트

for _ in range(n):  #모든 학생 정보를 입력받기
    students.append(input().split())

'''
[정렬기준]
1) 두 번쨰 원소를 기준으로 내림차순 정렬
2_ 두 번쨰 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬
4) 네 번째 원소가 같은 경우, 첫 번째 원소를 기준으로 오름차순 정렬
'''
students.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

for student in students:
    print(student[0])

입력

12
Junkyu 50 60 100
Sangkeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Haebin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90
Sanghyun 70 70 80
nsj 80 80 80
Taehwan 50 60 90

출력

Donghyuk
Sangkeun
Sunyoung
nsj
Wonseob
Sanghyun
Sei
Kangsoo
Haebin
Junkyu
Soong
Taehwan

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

[백준 파이썬] 10026번 적록색약

Sat, 21 May 2022 12:55:34 GMT

https://www.acmicpc.net/problem/10026
문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력 - 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) - 둘째 줄부터 N개 줄에는 그림이 주어진다.

출력 각 테스트 케이스마다 점수를 출력한다.

입력예시
5 RRRBB GGBBB BBBRR BBRRR RRRRR

출력예시 4 3

** sol) BFS를 이용. 적록색맹이 아닐 때 영역의 개수를 구한 후 적록색맹일 때는 G를 R로 바꾸어 영역의 개수를 구함 **

from collections import deque

visited = [[False] * n for _ in range(n)]
move = [(0, 1), (0, -1), (-1, 0), (1, 0)] #상,하,좌,우
graph = [[] * n for _ in range(n)]

for i in range(n):
    color = str(input()) #색 입력 받기
    for x in color:
        graph[i].append(x)

def bfs(x, y, color):
    q = deque() #큐 구현 위해 deque 라이브러리 이용
    q.append([x, y])

    while q: #큐가 빌 때까지 반복
        loc = q.popleft()
        x = loc[0]
        y = loc[1]

        if visited[x][y] == False: #비어있을 때
            visited[x][y] = True #방문
            for i in range(4): #네 방향 확인
                nx, ny = x + move[i][0], y + move[i][1]
                if nx >= 0 and nx < n and ny >= 0 and ny < n: #영역 내
                    if graph[nx][ny] == color:
                        q.append([nx, ny])

# 색약 아닐 때
cnt = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] == False: #방문하지 않은 곳
            color = graph[i][j]
            bfs(i, j, color)
            cnt += 1

# 색약일 때
visited = [[False] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G': #초록색을 
            graph[i][j] = 'R' #빨간색으로 취급

cnt_color_weakness = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            color = graph[i][j]
            bfs(i, j, color)
            cnt_color_weakness += 1

print(cnt)
print(cnt_color_weakness)

[코딩테스트] 탐색 알고리즘 DFS/BFS

Sat, 21 May 2022 12:27:46 GMT

DFS(Depth-First Search)

깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 (그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것) 그래프 표현 방법
- 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식, 모든 관계를 저장하기 때문에 노드의 개수가 많을수록 메모리 낭비
- 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식, 연결된 정보만을 저장하기 때문에 메모리 효율적 사용 가능 but 정보 얻는 속도 느림
동작과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. (방문처리는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않기 위함)
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 두번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.
DFS의 기능을 생각하면 순서와 상관없이 처리해도 되지만, 코딩 테스트에서는 번호가 낮은 순서부터 처리하도록 명시하는 경우가 종종 있다. 따라서 관행적으로 번호가 낮은 순서부터 처리하도록 구현하는 편이다.
데이터 개수가 n개인 경우 O(n)의 시간복잡도
재귀함수를 이용했을 때 매우 간단하게 구현 가능

def dfs(graph, v, visited): #DFS 메서드 정의
    visited[v] = True  #현재 노드를 방문 처리
    print(v, end=' ')
    for i in graph[v]: #현제 노드와 연결된 다른 노드를 재귀적으로 방문
        if not visited[i]:
            dfs(graph, i, visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[], [2,3,8], [1,7], [1,4,5],
         [3,5], [3,4], [7], [2,6,8], [1,7]] 

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 

dfs(graph, 1, visited)

BFS(Breadth First Search)

너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
FIFO 방식인 큐 자료주고 이용
인접한 노드를 반복적으로 큐에 넣게되면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색 진행 가능
동작방식
- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 두번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.
시간복잡도: O(n)
일반적으로 실제 수행 시간은 DFS보다 좋은 편

from collections import deque

def bfs(graph, start, visited): #BFS 메서드 정의
    queue = deque([start]) #큐 구현 위해 deque 라이브러리 사용
    visited[start] = True #현재 노드 방문 처리
    while queue: #큐가 빌 때까지 반복
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]: #인접하고 아직 방문하지 않은 원소들 큐에 삽입
            if not visited[i]:
                queue.append(i)
                visited[i] = True

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[], [2,3,8], [1,7], [1,4,5],
         [3,5], [3,4], [7], [2,6,8], [1,7]] 

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 

bfs(graph, 1, visited)

Ex1) 음료수 얼려 먹기

N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫혀있는 부분끼리 상,하,좌,우로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때, 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

*sol) DFS로 해결, 얼음 얼리는 공간을 그래프 형태로 모델링 '0'인 값이 상,하,좌,우로 연결되어 있는 노드를 묶는 프로그램을 작성 *

특정 지점의 주변 상,하,좌,우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

방문한 지점에서 다시 상,하,좌,우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

1,2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

입력조건 - 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M 주어진다. (1 $\leq$ N,M $\leq$ 1,000) - 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다. - 이 때, 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력조건 - 한 번에 만들수 있는 아이스크림의 개수를 출력한다.

n, m = map(int, input().split())

graph = [] #2차원 리스트의 맵 정보 입력받기
for i in range(n):
    graph.append(list(map(int, input()))) #2차원 리스트의 맵 정보 입력받기

#DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x,y):
    if x<=-1 or x>=n or y<=-1 or y>=m:
        return False #주어진 범위를 벗어나는 경우에는 즉시 종료
    if graph[x][y] == 0: #현재 노드를 방문하지 않았다면
        graph[x][y] ==1 #해당 노드 방문 처리
        #상,하,좌,우의 위치도 재귀적으로 호출
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True: #현재 위치에서 DFS 수행
            result += 1

print(result)

Ex2) 미로탈출

N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

*sol) BFS로 해결 (1,1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. *

맨 처음 (1,1)의 위치에서 시작하며, (1,1)의 값은 항상 1이라고 문제에서 언급되어있다.

(1,1) 좌표에서 상,하,좌,우로 탐색을 진행하면 바로 옆 노드인 (1,2) 위치의 노드를 방문하게 되고 새롭게 방문하는 (1,2) 노드의 값을 2로 바꾸게 된다.

마찬가지로 BFS를 계속 수행하면 결과적으로 최단 경로의 값이 1씩 증가하는 형태로 변경된다.

입력조건 - 첫 번째 줄에 두 정수 N,M (4 $\leq$ N,M $\leq$ 200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력조건 - 첫째 줄에 최소 이동 칸의 개수를 출력한다.

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

#이동할 네 방향 정의(상,하,좌,우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x,y): #BFS 
    queue = deque() #큐 구현 위해 deque 라이브러리 이용
    queue.append((x,y))
    while queue: #큐가 빌 때까지 반복
        x,y = queue.popleft()
        for i in range(4): #현재 위치에서 네 방향으로의 위치 확인
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny>0 or nx>=n or ny>=m: #미로 찾기 공간을 벗어난 경우 무시
                continue
            if graph[nx][ny] == 0: #벽인 경우 무시
                continue
            if graph[nx][ny] == 1: #해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n-1][m-1] #가장 오른쪽 아래까지의 최단 거리 반환

print(bfs(0,0))

실전문제) 특정 거리의 도시 찾기

어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때, 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

*sol) 모든 도로의 간선 비용이 동일하므로 BFS 사용. 시간 복잡도 O(N+M)으로 하는 소스 코드 작성. 특정한 도시 X를 시작점으로 BFS를 수행하여 모든 도시까지의 최단 거리를 계산한 뒤에, 각 최단 거리를 하나씩 확인하여 그 값이 K인 경우에 해당 도시의 번호 출력. *

입력조건 - 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 번호 X가 주어집니다. (2 $\leq$ N $\leq$ 300,000, 1 $\leq$ M $\leq$ 1,000,000, 1 $\leq$ K $\leq$ 300,000, 1 $\leq$ X $\leq$ N) - 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 주어지며, 각 자연수는 공백으로 구분합니다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미입니다. (1 $\leq$ A,B $\leq$ N) 단, A와 B는 서로 다른 자연수입니다.

출력조건 - X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력합니다. - 이 때, 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력합니다.

from collections import deque

#도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m): #모든 도로 정보 입력 받기
    a, b = map(ont, input().split())
    graph[a].append(b)

distance = [-1] * (n+1) #모든 도시에 대한 최단 거리 초기화
distance[x] = 0 #출발 도시까지의 거리는 0으로 설정

q = deque([x])
while q:
    now = q.popleft()
    for next_node in graph[now]: #현재 도시에서 이동할 수 있는 모든 도시 확인
        if distance[next_node] == -1: #아직 방문하지 않은 도시라면
            distance[next_node] = distance[now] + 1
            q.append(next_node)

check = False #최단 거리 K인 모든 도시의 번호를 오름차순으로 출력
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        check = True

if check == False: #만약 최단 거리가 K인 도시가 없다면, -1 출력
    print(-1)

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

[백준 파이썬] 8958번 OX 퀴즈

Sat, 14 May 2022 12:31:06 GMT

https://www.acmicpc.net/problem/8958
문제 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다.

"OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다.

OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다.

출력 각 테스트 케이스마다 점수를 출력한다.

입력예시
5 OOXXOXXOOO OOXXOOXXOO OXOXOXOXOXOXOX OOOOOOOOOO OOOOXOOOOXOOOOX

출력예시 10 9 7 55 30

sol) 테스트 개수만큼 반복문을 실행하여 각 테스트 케이스에서의 문자열을 입력 받는다. 그런 후 각 테스트 케이스의 문자열만큼 반복하여 O 또는 X를 확인하여 점수에 반영한다.

n = int(input())  #테스트 개수 입력받기

for _ in range(n):  #테스트 개수만큼 반복문 실행
    case = input()  #각 테스트 케이스 문자열 입력
    score = 0
    total = 0
    for j in case:  #각 테스트 케이스의 문자열만큼 반복
        if j == 'O':  #문자열이 'O'일 때 
            score += 1
        else:  #문자열이 'X'일 때
            score = 0
        total += score
    print(total)  #각 테스트 케이스에서의 점수 출력

교재에서의 예제와 비슷한 유형이라 쉽게 풀린 듯 하다.
하지만 print(total) 의 위치를 처음에는 잘못 설정하여 원하는 출력값이 나오지 않았지만
빠르게 원인을 찾아 첫번째 반복문 내에 넣어서 해결하였다.

[코딩테스트] 구현

Sat, 14 May 2022 12:13:18 GMT

구현

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기
구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함
언어의 문법을 잘 이해하는 것이 중요

구현 유형

완전 탐색: 모든 경우의 수를 주저 없이 다 계산 일반적으로 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 많을 때는 정상적으로 동작하지 않을 수 있음. (100만 개 이하일 때 사용하면 적절)
시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

cf) 구현이 어려운 문제 -> 알고리즘은 간단하지만 코드가 지나칠 만큼 길어지는 문제 -> 특정 소수점 자리까지 출력해야하는 문제 -> 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 파싱해야하는 문제 등

구현 시 고려해야할 메모리 제약 사항

C/C++ 또는 자바에서는 정수 자료형에 따라 자료형 범위가 제한적
Python은 프로그래머가 직접 자료형을 지정할 필요가 없음
-> 매우 큰 수 연산 또한 기본적으로 지원
하지만 Python에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라 연산 결과가 달라질 수 있음을 유의
Python에서 리스트 사용 => 코딩 테스트의 메모리 제한 고려해야함.
- 대체로 코딩 테스트에서는 128~512 MB 메모리 제한
- 알고리즘 문제 중 큰 데이터를 처리해야하는 문제일 때 메모리 제한 염두
- 리스트를 여러 개 선언하고 그 중 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없음

채점환경

: 시간 제한이 1초이고, 데이터 개수가 100만 개인 문제가 있다면 시간복잡도 O(NlogN) 이내의 알고리즘 이용하여 문제를 풀어야 함 => 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 후, 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측

** 코딩 테스트에서 가장 난이도가 낮은 1~2번 문제는 대부분 그리디 알고리즘 또는 구현 문항. 논리적 사고력을 확인할 수 있는 가장 기본 난이도의 문제로 적합 => 합격 좌우 가능

Ex1) 상하좌우

여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 상,하,좌,우 방향으로 이동할 수 있으며 N X N의 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

*sol) 시뮬레이션 유형, O(N)의 시간 복잡도 (이동 횟수에 연산 횟수 비례) *

입력조건 - 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 $\leq$ N $\leq$ 100) - 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 $\leq$ 이동횟수 $\leq$ 100)

출력조건 - 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.

n = int(input())
x, y = 1, 1
plans = input().split() #입력 받은 것을 띄어쓰기 기준으로 나누기

#L, R, U, D에 따른 이동 방향
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_types = ['L','R','U','D']

for plan in plans: #입력 받은 이동 계획에 따라 진행
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]  #이동 후 좌쵸 구하기
            ny = y + dy[i]

    if nx <1 or ny <1 or nx > n or ny > n:  #공간을 벗어나는 경우 무시
        continue

    x, y = nx, ny

print(x,y)

Ex2) 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

sol) 완전 탐색 유형, 모든 시각의 경우를 하나씩 모두 세서 풀기 (하루의 모든 초의 경우는 86,400개로 완전 탐색 알고리즘으로 수용 가능) -> 매 시각을 문자열로 바꾼 후 문자열에 '3'이 포함이 되었는지 검사

입력조건 - 첫째 줄에 정수 N이 입력된다. (0 $\leq$ N $\leq$ 23)

출력조건 - 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.


h = int(input())  #시간 입력 받기

count = 0
for i in range(h+1):
    for j in range(60):
        for k in range(60):
               #매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k): 
                count += 1

print(count)

Ex3) 왕실의 나이트

왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다. 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. Rule 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. (행:1~~8, 열:a~~h)

*sol) 나이트가 이동할 수 있는 이동 경로를 리스트에 넣고, 현재 위치에서 이동 경로를 더한 다음 8 X 8 좌표 평면에 있는지 반복문으로 확인 *

입력조건 - 첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

출력조건 - 첫째 줄에 나이트가 이동할 수 있는 경우를 출력하시오.

input_loc = input() #현재 위치 입력받기
row = int(input_loc[1])
col = int(ord(input_loc[0])) - int(ord('a')) + 1

#나이트가 이동할 수 있는 8가지 방향
steps = [(-2,1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)]

result = 0
for step in steps: #8가지 방향에 대해 이동가능한지 확인
    next_row = row + step[0]
    next_col = col + step[1]
    #이동 가능하다면 result 증가
    if next_row >=1 and next_row <= 8 and next_col >= 1 and next_col <=8:
        result += 1

print(result)

Ex4) 게임 개발

게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A,B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼이다.

Rule 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈수 없는 경우에는 움직임을 멈춘다.

위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트 하려고 한다. 매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

*sol) 시뮬레이션 문항, 별도의 알고리즘의 필요보다 문제에서 요구하는 내용을 오류 없이 성실히 구현만 할 수 있담녀 풀 수 있음. 방향을 설정하는 문제 유형 => dx, dy라는 별도의 리스트를 만드는 것이 효과적 2차원 리스트 선언 => 리스트 컴프리헨션 문법 사용 *

입력조건 - 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 $\leq$ N,M$\leq$ 50) - 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A,B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값은 4가지가 존재한다. (0:북, 1:동, 2:남, 3:서) - 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어있다. (0:육지, 1:바다)

출력조건 - 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

입력예시

4  4         # 4x4 맵 생성
1  1  0      # (1,1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1  1  1  1   # 첫 줄은 모두 바다
1  0  0  1   # 둘째 줄은 바다/육지/육지/바다
1  1  0  1   # 셋째 줄은 바다/바다/육지/바다
1  1  1  1   # 넷째 줄은 모두 바다

출력예시 3

n, m = map(int, input().split())  #N,M을 공백으로 구분하여 입력 받기

#방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]

#현재 캐릭터의 X, Y 좌표, 방향을 입력받기
x, y, direc = map(int, input().split())
d[x][y] = 1 #현재 좌표 방문 처리

#전체 맵 정보를 입력 받기
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

#북,동,남,서 방향 정의
dx = [-1,0,1,0]
dy = [0,1,0,-1]

#왼쪽으로 회전
def turn_left():
    global direc #함수 바깥에서 선언된 전역변수이므로 global 사용
    direc -= 1
    if direc == -1:
        direc = 3

#시뮬레이션 시작
count = 1
turn_time = 0
while True:
     #왼쪽으로 회전
    turn_left()
    nx = x + dx[direc]
    ny = y + dy[direc]

    if d[nx][ny] == 0 and array[nx][ny] == 0: #회전 후 정면에 가보지 않는 칸 있다면
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    else: #회전 후 정면에 가보지 않은 칸이 없거나 바다일 때
        turn_time += 1

    if turn_time == 4: #네 방향 모두 갈 수 없을 때
        nx = x - dx[direc]
        ny = y - dy[direc]

        if array[nx][ny] == 0: #뒤로 갈 수 있다면 이동하기
            x = nx
            y = ny
        else: #뒤가 바다로 막혀있는 경우
            break
        turn_time = 0
print(count)

실전문제) 럭키 스트레이트

게임의 아웃복서 캐릭터는 필살기인 '럭키 스트레이트' 기술이 있다. 이 기술은 매우 강력한 대신 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다. 특정 조건 현재 캐릭터의 점수를 N이라 할 때 자릿수를 기준으로 점수 N을 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황

현재 점수 N이 주어지면 럭키 스트레이트를 사용할 수 있는 상태인지 아닌지를 알려주는 프로그램을 작성하시오.

*sol) 입력받은 정수형 데이터를 각 자릿수를 구분하여 합을 계산한다. 문자열에서 문자를 하나씩 확인한 후 정수형으로 변환한 후에 합 변수에 더한다. *

입력조건 - 첫째 줄에 점수 N이 정수로 주어집니다. (10 $\leq$ N $\leq$ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어집니다. 예를 들어 자릿수가 5인 12,345와 같은 수는 입력으로 들어오지 않습니다.

출력조건 - 첫째 줄에 럭키 스트레이트를 사용할 수 있다면 "LUCKY"를, 사용할 수 없다면 "READY"를 출력합니다.

score = input() #점수 입력받기
length = len(score) #입력 받은 점수값의 자릿수
l_result = 0
r_result = 0

#왼쪽 부분 자릿수 합 구하기
for i in range(length//2):
    l_result += int(score[i])

#오른쪽 부분 자릿수 합 구하기
for i in range(length//2, length):
    r_result += int(score[i])

#왼쪽 부분과 오른쪽 부분의 자릿수 합이 동일한지 검사
if l_result == r_result:
    print("LUCKY")
else:
    print("READY")

나는 왼쪽 부분 자릿수 합과 오른쪽 부분 자릿수의 합을 각자 새로운 변수에 지정하여 비교함.
하지만 예시 답안에는 왼쪽 부분 자릿수 합은 result에 더하고 오른쪽 부분 자릿수 합은 result
에서 빼는 것을 이용하여 result가 0인지 아닌지를 이용함.
이렇게 되면 변수를 더 적게 사용할 수 있고, 코드도 한 줄 짧아지게 됨.

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

[데이터 분석] Kaggle_타이타닉 생존자 분석

Wed, 11 May 2022 06:17:22 GMT

타이타닉 생존자 분석

https://www.kaggle.com/competitions/titanic/overview

어떤 승객들이 살아 남았는가 (-성별, 연령)
머신러닝 모델로 승선한 사람들의 생존 유무 예측

data

train.csv: 예측 모델을 만들기 위해 사용하는 학습셋. 각 탑승객의 신상정보와 ground truth(생존유무)가 주어지며, 생존 유무를 예측하는 모델 만듦
test.csv: 학습셋으로 만든 모델을 가지고 예측할 탑승객 정보가 담긴 테스트셋 (test에 더 적은 승객 정보가 들어있음. shape 함수 통해 확인 가능)

Data fields

survival: 생존 유무, target 값 (0: 사망, 1: 생존) pclass: 티켓 클래스 (1: 1st, 2: 2nd, 3: 3rd) sex: 성별 age: 나이 sibsp: sibiling + spouse (=> 함께 탑승한 형제자매, 배우자 수 총합) parch: parent + children (=> 함께 탑승한 부모, 자녀 수 총합) ticket: ticket number fare: 탑승 요금 cabin: 객실 번호 embarked: 탑승 항구

데이터 분석

from google.colab import files
myfile = files.upload()

Saving test.csv to test.csv
Saving train.csv to train.csv

import pandas as pd
import numpy as np
train = pd.read_csv('train.csv')
test = pd.read_csv('test.csv')

train.head()
test.head()

train.shape #데이터의 행, 열 값 출력
test.shape

train.isnull()  #결측치 값 유무 확인 (False: 결측치값x, True: 결측치값o)

train.isnull().sum() #결측치값 쉽게 알아볼 수 있음
test.isnull().sum()

데이터 시각화

시각화: 어느 특성의 승객이 더 많이 살아남았는가
```
import matplotlib.pyplot as plt
%matplotlib inline 
import seaborn as sns
sns.set() #setting seaborn default for plots
```
=> %matplotlib inline: 시각화 한 결과를 바로 볼 수 있게 해줌

def bar_chart(feature):
  survived = train[train['Survived'] == 1][feature].value_counts()
  dead = train[train['Survived'] == 0][feature].value_counts()
  df = pd.DataFrame([survived, dead])
  df.index = ['Survived', 'Dead']
  df.plot(kind = 'bar', stacked = True, figsize = (10,5))

bar_chart('Sex')

bar_chart('Pclass')

bar_chart('SibSp')

bar_chart('Parch')

bar_chart('Embarked')

[데이터 분석] 데이터 준비하기: 조인, 병합, 변형

Wed, 11 May 2022 05:43:16 GMT

계층적 색인: 축에 대해 다중 색인 단계를 지정할 수 있도록 함. 높은 차원의 데이터를 낮은 차원의 형식으로 다룰 수 있게 해주는 기능

import pandas as pd
import numpy as np

계층적 색인

data = pd.Series(np.random.randn(9), #리스트의 리스트를 색인으로 하는 Series 생성
                index = [['a','a','a','b','b','c','c','d','d'],[1,2,3,1,3,1,2,2,3]])

data

a  1   -0.718279
   2   -1.293206
   3    0.838317
b  1    0.587797
   3    0.416080
c  1    2.074077
   2   -1.228737
d  2   -0.503776
   3    1.030454
dtype: float64

MultiIndex를 색인으로 하는 Series. 색인의 계층을 보여주고 있음

data.index #바로 위 단계의 색인 이용하여 하위 계층 직접 접근 가능

MultiIndex([('a', 1),
            ('a', 2),
            ('a', 3),
            ('b', 1),
            ('b', 3),
            ('c', 1),
            ('c', 2),
            ('d', 2),
            ('d', 3)],
           )

계층적으로 색인된 객체는 데이터의 부분집합을 부분적 색인으로 접근 가능

data['b']

1    0.587797
3    0.416080
dtype: float64

data['b':'c']

b  1    0.587797
   3    0.416080
c  1    2.074077
   2   -1.228737
dtype: float64

data.loc[['b','d']]

b  1    0.587797
   3    0.416080
d  2   -0.503776
   3    1.030454
dtype: float64

data.loc[:,2]  #하위 계층의 객체 선택 가능

a   -1.293206
c   -1.228737
d   -0.503776
dtype: float64

계층적 색인은 데이터를 재형성하고 피벗테이블 생성 같은 그룹 기반의 작업할 때 중요하게 사용

data.unstack()  #unstack 메서드 이용하여 데이터 새롭게 배열

	1	2	3
a	-0.718279	-1.293206	0.838317
b	0.587797	NaN	0.416080
c	2.074077	-1.228737	NaN
d	NaN	-0.503776	1.030454

data.unstack().stack()  #stack 메서드는 unstack 메서드의 반대 작업

a  1   -0.718279
   2   -1.293206
   3    0.838317
b  1    0.587797
   3    0.416080
c  1    2.074077
   2   -1.228737
d  2   -0.503776
   3    1.030454
dtype: float64

frame = pd.DataFrame(np.arange(12).reshape((4,3)),
                    index = [['a','a','b','b'],[1,2,1,2]],
                    columns = [['Ohio','Ohio','Colorado'],['Green','Red','Green']])

frame  # 두 축 모두 계층적 색인

		Ohio		Colorado
		Green	Red	Green
a	1	0	1	2
a	2	3	4	5
b	1	6	7	8
b	2	9	10	11

frame.index.names = ['key1','key2']  #색인 이름 설정

frame.columns.names = ['state','color']

frame

	state	Ohio		Colorado
	color	Green	Red	Green
key1	key2
a	1	0	1	2
a	2	3	4	5
b	1	6	7	8
b	2	9	10	11

frame['Ohio'] #부분적 색인

	color	Green	Red
key1	key2
a	1	0	1
a	2	3	4
b	1	6	7
b	2	9	10

MultiIndex는 따로 생성한 다음에 재사용 가능

계층의 순서를 바꾸고 정렬

swaplevel: 넘겨받은 두 개의 계층 번호나 이름이 뒤바뀐 새로운 객체 반환 (but 데이터는 변경되지 x)

frame.swaplevel('key1','key2')

	state	Ohio		Colorado
	color	Green	Red	Green
key2	key1
1	a	0	1	2
2	a	3	4	5
1	b	6	7	8
2	b	9	10	11

sort_index: 단일 계층에 속한 데이터 정렬

frame.sort_index(level=1)

	state	Ohio		Colorado
	color	Green	Red	Green
key1	key2
a	1	0	1	2
b	1	6	7	8
a	2	3	4	5
b	2	9	10	11

frame.swaplevel(0,1).sort_index(level=0)

	state	Ohio		Colorado
	color	Green	Red	Green
key2	key1
1	a	0	1	2
1	b	6	7	8
2	a	3	4	5
2	b	9	10	11

계층별 요약 통계

level 옵션: 어떤 한 축에 대해 합을 구하고 싶은 단계 지정

frame.sum(level='key2')

/var/folders/1b/6fw3j9nd4_qgymn82k3hygww0000gn/T/ipykernel_4080/2004046222.py:1: FutureWarning: Using the level keyword in DataFrame and Series aggregations is deprecated and will be removed in a future version. Use groupby instead. df.sum(level=1) should use df.groupby(level=1).sum().
  frame.sum(level='key2')

state	Ohio		Colorado
color	Green	Red	Green
key2
1	6	8	10
2	12	14	16

원하는 출력은 나오지만 warning이 있다..

frame.sum(level='color', axis=1)

/var/folders/1b/6fw3j9nd4_qgymn82k3hygww0000gn/T/ipykernel_4080/4133796543.py:1: FutureWarning: Using the level keyword in DataFrame and Series aggregations is deprecated and will be removed in a future version. Use groupby instead. df.sum(level=1) should use df.groupby(level=1).sum().
  frame.sum(level='color', axis=1)

	color	Green	Red
key1	key2
a	1	2	1
a	2	8	4
b	1	14	7
b	2	20	10

DataFrame에서 로우나 컬럼을 계층별로 합할 수 있음

DataFrame의 컬럼 사용하기

frame = pd.DataFrame({'a':range(7), 'b':range(7,0,-1),
                     'c':['one','one','one','two','two','two','two'], 'd':[0,1,2,0,1,2,3]})

frame

	a	b	c	d
0	0	7	one	0
1	1	6	one	1
2	2	5	one	2
3	3	4	two	0
4	4	3	two	1
5	5	2	two	2
6	6	1	two	3

set_index: 하나 이상의 컬럼을 색인으로 하는 새로운 DataFrame 생성

frame2 = frame.set_index(['c','d'])

frame2

		a	b
c	d
one	0	0	7
	1	1	6
	2	2	5
two	0	3	4
	1	4	3
	2	5	2
	3	6	1

컬럼을 명시적으로 남겨두지 않으면 DataFrame에서 삭제됨

frame.set_index(['c','d'], drop=False)

		a	b	c	d
c	d
one	0	0	7	one	0
	1	1	6	one	1
	2	2	5	one	2
two	0	3	4	two	0
	1	4	3	two	1
	2	5	2	two	2
	3	6	1	two	3

reset_index: 계층적 색인 단계가 컬럼으로 이동

frame2.reset_index()

	c	d	a	b
0	one	0	0	7
1	one	1	1	6
2	one	2	2	5
3	two	0	3	4
4	two	1	4	3
5	two	2	5	2
6	two	3	6	1

데이터 합치기

pandas.merge: 하나 이상의 키를 기준으로 DataFrame의 로우를 합침. SQL 또는 다른 관계형 데이터베이스의 join 연산과 유사
pandas.concat: 하나의 축을 따라 객체를 이어 붙임
combine_first: 두 객체를 포개서 한 객체에서 누락된 데이터를 다른 객체에 있는 값으로 채울 수 있도록 함

데이터베이스 스타일로 DataFrame 합치기

병합, 조인 연산: 하나 이상의 키를 사용하여 데이터 집합의 로우를 합칩

df1 = pd.DataFrame({'key':['b','b','a','c','a','a','b'],'data1':range(7)})

df2 = pd.DataFrame({'key':['a','b','d'], 'data2':range(3)})

df1 #key 컬럼에 여러 개의 a,b 로우

	key	data1
0	b	0
1	b	1
2	a	2
3	c	3
4	a	4
5	a	5
6	b	6

df2 #key 컬럼에 유일한 로우

	key	data2
0	a	0
1	b	1
2	d	2

pd.merge(df1,df2) #merge 함수는 중복된 컬럼 이름을 키로 사용 but 지정해주는 것이 좋음

	key	data1	data2
0	b	0	1
1	b	1	1
2	b	6	1
3	a	2	0
4	a	4	0
5	a	5	0

만약, 두 객체에 중복된 컬럼 이름이 없다면 따로 지정.

df3 = pd.DataFrame({'1key':['b','b','a','c','a','a','b'], 'data1':range(7)})

df4 = pd.DataFrame({'rkey':['a','b','d'],'data2':range(3)})

pd.merge(df3, df4, left_on = '1key', right_on = 'rkey')

	1key	data1	rkey	data2
0	b	0	b	1
1	b	1	b	1
2	b	6	b	1
3	a	2	a	0
4	a	4	a	0
5	a	5	a	0

merge 함수는 기본적으로 내부 조인을 수행하여 교집합인 결과를 반환
외부 조인은 합집합인 결과 반환(how 인자 사용)

pd.merge(df1, df2, how = 'outer')  #how = 'outer' : 양쪽 테이블에 존재하는 모든 키 조합 사용

	key	data1	data2
0	b	0.0	1.0
1	b	1.0	1.0
2	b	6.0	1.0
3	a	2.0	0.0
4	a	4.0	0.0
5	a	5.0	0.0
6	c	3.0	NaN
7	d	NaN	2.0

다대다 병합은 직관적이지 않음.

df1 = pd.DataFrame({'key':['b','b','a','c','a','b'],'data1':range(6)})

df2 = pd.DataFrame({'key':['a','b','a','b','d'],'data2':range(5)})

df1

	key	data1
0	b	0
1	b	1
2	a	2
3	c	3
4	a	4
5	b	5

df2

	key	data2
0	a	0
1	b	1
2	a	2
3	b	3
4	d	4

pd.merge(df1, df2, on = 'key', how = 'left')  #how = 'left' : 왼쪽 테이블에 존재하는 모든 키 조합 사용

	key	data1	data2
0	b	0	1.0
1	b	0	3.0
2	b	1	1.0
3	b	1	3.0
4	a	2	0.0
5	a	2	2.0
6	c	3	NaN
7	a	4	0.0
8	a	4	2.0
9	b	5	1.0
10	b	5	3.0

다대다 조인은 두 로우의 데카르트 곱 반환 => 조인 메서드는 결과에 나타나는 구별되는 키에 대해서만 적용

pd.merge(df1, df2, how = 'inner')

	key	data1	data2
0	b	0	1
1	b	0	3
2	b	1	1
3	b	1	3
4	b	5	1
5	b	5	3
6	a	2	0
7	a	2	2
8	a	4	0
9	a	4	2

겹치는 컬럼 이름에 대한 처리

축 이름 변경하여 수동으로 컬럼 이름 겹치게 하기
suffixes 인자로 DataFrame 객체에서 겹치는 컬럼 이름 뒤에 붙일 문자열 지정

left = pd.DataFrame({'key1':['foo','foo','bar'],
                    'key2':['one','two','one'],
                    'lval':[1,2,3]})

right = pd.DataFrame({'key1':['foo','foo','bar','bar'],
                    'key2':['one','one','one','two'],
                    'rval':[4,5,6,7]})

pd.merge(left, right, on = 'key1')

	key1	key2_x	lval	key2_y	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

pd.merge(left, right, on = 'key1', suffixes=('_left','_right'))

	key1	key2_left	lval	key2_right	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

색인 병합하기

병합하는 키가 DataFrame의 색인일 경우
left_index = True 혹은 right_index = True 옵션 사용하여 해당 색인을 병합 키로 사용

left1 = pd.DataFrame({'key':['a','b','a','a','b','c'], 'value':range(6)})

right1 = pd.DataFrame({'group_val':[3.5, 7]}, index = ['a','b'])

left1

	key	value
0	a	0
1	b	1
2	a	2
3	a	3
4	b	4
5	c	5

right1

	group_val
a	3.5
b	7.0

pd.merge(left1, right1, left_on = 'key', right_index = True)

	key	value	group_val
0	a	0	3.5
2	a	2	3.5
3	a	3	3.5
1	b	1	7.0
4	b	4	7.0

pd.merge(left1, right1, left_on = 'key', right_index = True, how = 'outer') #외부 조인 실행하여 합집합

	key	value	group_val
0	a	0	3.5
2	a	2	3.5
3	a	3	3.5
1	b	1	7.0
4	b	4	7.0
5	c	5	NaN

계층 색인된 데이터는 암묵적으로 여러 키 병합

lefth = pd.DataFrame({'key1': ['Ohio','Ohio','Ohio','Nevada','Nevada'], 
                     'key2': [2000, 2001, 2002, 2001, 2002],
                     'data': np.arange(5.)})

righth = pd.DataFrame(np.arange(12).reshape((6,2)),
                     index = [['Nevada','Nevada','Ohio','Ohio','Ohio','Ohio'], 
                     [2001, 2000, 2000, 2000, 2001, 2002]], columns = ['event1', 'event2'])

lefth

	key1	key2	data
0	Ohio	2000	0.0
1	Ohio	2001	1.0
2	Ohio	2002	2.0
3	Nevada	2001	3.0
4	Nevada	2002	4.0

righth

		event1	event2
Nevada	2001	0	1
Nevada	2000	2	3
Ohio	2000	4	5
	2000	6	7
	2001	8	9
	2002	10	11

=> 리스트로 여러 개의 컬럼을 지정해서 병합해야함. (how = 'outer' 사용)

pd.merge(lefth, righth, left_on = ['key1','key2'], right_index = True)

	key1	key2	data	event1	event2
0	Ohio	2000	0.0	4	5
0	Ohio	2000	0.0	6	7
1	Ohio	2001	1.0	8	9
2	Ohio	2002	2.0	10	11
3	Nevada	2001	3.0	0	1

pd.merge(lefth, righth, left_on = ['key1','key2'], right_index = True, how = 'outer')

	key1	key2	data	event1	event2
0	Ohio	2000	0.0	4.0	5.0
0	Ohio	2000	0.0	6.0	7.0
1	Ohio	2001	1.0	8.0	9.0
2	Ohio	2002	2.0	10.0	11.0
3	Nevada	2001	3.0	0.0	1.0
4	Nevada	2002	4.0	NaN	NaN
4	Nevada	2000	NaN	2.0	3.0

left2 = pd.DataFrame([[1.,2.], [3.,4.], [5.,6.]], index = ['a','c','e'], columns = ['Ohio', 'Nevada'])

right2 = pd.DataFrame([[7.,8.], [9.,10.], [11.,12.], [13,14]], index = ['b','c','d','e'], 
                      columns = ['Missouri', 'Alabama'])

left2

	Ohio	Nevada
a	1.0	2.0
c	3.0	4.0
e	5.0	6.0

right2

	Missouri	Alabama
b	7.0	8.0
c	9.0	10.0
d	11.0	12.0
e	13.0	14.0

pd.merge(left2, right2, how = 'outer', left_index = True, right_index = True)

	Ohio	Nevada	Missouri	Alabama
a	1.0	2.0	NaN	NaN
b	NaN	NaN	7.0	8.0
c	3.0	4.0	9.0	10.0
d	NaN	NaN	11.0	12.0
e	5.0	6.0	13.0	14.0

색인으로 병합할 때 join 메서드 이용하면 편리.
join 메서드는 컬럼이 겹치지 않으며 완전히 같거나 유사한 색인 구조를 가진 여러 개의 DataFrame 객체를 병합할 때 사용 가능

left2.join(right2, how='outer')

	Ohio	Nevada	Missouri	Alabama
a	1.0	2.0	NaN	NaN
b	NaN	NaN	7.0	8.0
c	3.0	4.0	9.0	10.0
d	NaN	NaN	11.0	12.0
e	5.0	6.0	13.0	14.0

left1.join(right1, on='key')

	key	value	group_val
0	a	0	3.5
1	b	1	7.0
2	a	2	3.5
3	a	3	3.5
4	b	4	7.0
5	c	5	NaN

색인 대 색인으로 두 DataFrame 병합

another = pd.DataFrame([[7.,8.], [9.,10.], [11.,12.], [16.,17.]], index = ['a','c','e','f'], 
                      columns = ['New York', 'Oregon'])

another

	New York	Oregon
a	7.0	8.0
c	9.0	10.0
e	11.0	12.0
f	16.0	17.0

left2.join([right2, another])

	Ohio	Nevada	Missouri	Alabama	New York	Oregon
a	1.0	2.0	NaN	NaN	7.0	8.0
c	3.0	4.0	9.0	10.0	9.0	10.0
e	5.0	6.0	13.0	14.0	11.0	12.0

left2.join([right2, another], how='outer')

	Ohio	Nevada	Missouri	Alabama	New York	Oregon
a	1.0	2.0	NaN	NaN	7.0	8.0
c	3.0	4.0	9.0	10.0	9.0	10.0
e	5.0	6.0	13.0	14.0	11.0	12.0
b	NaN	NaN	7.0	8.0	NaN	NaN
d	NaN	NaN	11.0	12.0	NaN	NaN
f	NaN	NaN	NaN	NaN	16.0	17.0

축 따라 이어 붙이기

numpy에서는 ndarray를 이어붙이는 concatenate 함수 이용

arr = np.arange(12).reshape((3,4))

arr

array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11]])

np.concatenate([arr,arr], axis = 1)

array([[ 0,  1,  2,  3,  0,  1,  2,  3],
       [ 4,  5,  6,  7,  4,  5,  6,  7],
       [ 8,  9, 10, 11,  8,  9, 10, 11]])

at pandas.. => 축마다 이름이 있어서 배열을 쉽게 이어붙일 수 있도록 구성

고려사항

만약 연결하려는 두 객체의 색인이 서로 다르면 결과는 그 색인의 교집합? 합집합?
합쳐진 결과에서 합쳐지기 전 객체의 데이터 구분할 수 있어야할까?
어떤 축으로 연결할 것인지 고려해야하나? (많을 경우 DataFrame의 기본 정수 라벨이 가장 먼저 무시)

pandas에서는 concat 함수 이용

s1 = pd.Series([0,1], index=['a','b'])

s2 = pd.Series([2,3,4], index=['c','d','e'])

s3 = pd.Series([5,6], index=['f','g'])

pd.concat([s1,s2,s3])

a    0
b    1
c    2
d    3
e    4
f    5
g    6
dtype: int64

concat 함수는 axis=0을 기본값으로 하며 새로운 Series 객체 생성
만약 axis=1 이상이라면 결과는 Series가 아닌 DataFrame (axis=1은 칼럼 의미)

pd.concat([s1,s2,s3], axis=1)

	0	1	2
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0

s4 = pd.concat([s1,s3])

s4

a    0
b    1
f    5
g    6
dtype: int64

pd.concat([s1,s4], axis=1)

	0	1
a	0.0	0
b	1.0	1
f	NaN	5
g	NaN	6

pd.concat([s1,s4], axis=1, join='inner')

	0	1
a	0	0
b	1	1

join_axes: 병합하려는 축을 직접 지정 가능

pd.concat([s1,s4], axis=1, join_axes = [['a','c','b','e']])

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

/var/folders/1b/6fw3j9nd4_qgymn82k3hygww0000gn/T/ipykernel_4080/1941623965.py in 
----> 1 pd.concat([s1,s4], axis=1, join_axes = [['a','c','b','e']])


~/opt/anaconda3/lib/python3.9/site-packages/pandas/util/_decorators.py in wrapper(*args, **kwargs)
    309                     stacklevel=stacklevel,
    310                 )
--> 311             return func(*args, **kwargs)
    312 
    313         return wrapper


TypeError: concat() got an unexpected keyword argument 'join_axes'

join_axes를 지원하지 않는다는 것 같다... => reindex 사용!

pd.concat([s1,s4], axis=1).reindex(['a','c','b','e'])

	0	1
a	0.0	0.0
c	NaN	NaN
b	1.0	1.0
e	NaN	NaN

계층적 색인을 생성하려면 keys 인자 사용
Series를 이어붙이기 전의 개별 Series를 구분할 수 없으므로 이어 붙인 축에 대해 계층적 색인 생성하여 식별 가능하도록 함!)

result = pd.concat([s1,s1,s3], keys=['one','two','three'])

result

one    a    0
       b    1
two    a    0
       b    1
three  f    5
       g    6
dtype: int64

result.unstack()

	a	b	f	g
one	0.0	1.0	NaN	NaN
two	0.0	1.0	NaN	NaN
three	NaN	NaN	5.0	6.0

Series를 axis=1로 병합하게 되면 keys는 DataFrame의 컬럼 제목이 됨

pd.concat([s1,s2,s3], axis=1, keys=['one','two','three'])

	one	two	three
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0

DataFrame 객체에 대해서도 이와 같음

df1 = pd.DataFrame(np.arange(6).reshape(3,2), index=['a','b','c'], columns=['one','two'])

df2 = pd.DataFrame(5+np.arange(4).reshape(2,2), index=['a','c'], columns=['three','four'])

df1

	one	two
a	0	1
b	2	3
c	4	5

df2

	three	four
a	5	6
c	7	8

pd.concat([df1,df2], axis=1, keys=['level1','level2'])

	level1		level2
	one	two	three	four
a	0	1	5.0	6.0
b	2	3	NaN	NaN
c	4	5	7.0	8.0

리스트 대신 객체의 사전을 넘기면 사전의 키가 keys 옵션으로 사용

pd.concat({'level1':df1, 'level2':df2}, axis=1)

	level1		level2
	one	two	three	four
a	0	1	5.0	6.0
b	2	3	NaN	NaN
c	4	5	7.0	8.0

pd.concat([df1,df2], axis=1, keys=['level1','level2'], names=['upper','lower'])  #names인자=> 새로 생성된 계층 이름 지정

upper	level1		level2
lower	one	two	three	four
a	0	1	5.0	6.0
b	2	3	NaN	NaN
c	4	5	7.0	8.0

df1 = pd.DataFrame(np.random.randn(3,4), columns=['a','b','c','d'])

df2 = pd.DataFrame(np.random.randn(2,3), columns=['b','d','a'])

df1

	a	b	c	d
0	-0.031695	-0.074865	-0.567876	-0.106580
1	0.175408	-0.300737	1.752298	0.311653
2	0.383386	0.625466	-0.717174	0.603836

df2

	b	d	a
0	-0.865482	-0.811584	0.205644
1	0.506437	0.279058	-1.258077

=>DataFrame의 로우 색인이 분석에 필요한 데이터를 포함하고 있지 않을 때
ignore_index=True 옵션 사용

pd.concat([df1,df2], ignore_index=True)

	a	b	c	d
0	-0.031695	-0.074865	-0.567876	-0.106580
1	0.175408	-0.300737	1.752298	0.311653
2	0.383386	0.625466	-0.717174	0.603836
3	0.205644	-0.865482	NaN	-0.811584
4	-1.258077	0.506437	NaN	0.279058

겹치는 데이터 합치기

a = pd.Series([np.nan, 2.5, np.nan, 3.5, 4.5, np.nan], index=['f','e','d','c','b','a'])

b = pd.Series(np.arange(len(a), dtype=np.float64), index=['f','e','d','c','b','a'])

b[-1] = np.nan

f    NaN
e    2.5
d    NaN
c    3.5
b    4.5
a    NaN
dtype: float64

f    0.0
e    1.0
d    2.0
c    3.0
b    4.0
a    NaN
dtype: float64

np.where(pd.isnull(a), b, a)

array([0. , 2.5, 2. , 3.5, 4.5, nan])

b[:-2].combine_first(a[2:])

a    NaN
b    4.5
c    3.0
d    2.0
e    1.0
f    0.0
dtype: float64

df1 = pd.DataFrame({'a':[1., np.nan, 5., np.nan], 'b':[np.nan, 2., np.nan, 6.], 'c': range(2,18,4)})

df2 = pd.DataFrame({'a':[5., 4., np.nan, 3., 7.], 'b':[np.nan, 3., 4., 6., 8.]})

df1

	a	b	c
0	1.0	NaN	2
1	NaN	2.0	6
2	5.0	NaN	10
3	NaN	6.0	14

df2

	a	b
0	5.0	NaN
1	4.0	3.0
2	NaN	4.0
3	3.0	6.0
4	7.0	8.0

df1.combine_first(df2)

	a	b	c
0	1.0	NaN	2.0
1	4.0	2.0	6.0
2	5.0	4.0	10.0
3	3.0	6.0	14.0
4	7.0	8.0	NaN

재형성과 피벗

: 표 형식의 데이터를 재배치하는 기본 연산

계층적 색인으로 재형성하기

stack: 데이터의 컬럼을 로우로 피벗(또는 회전) 시킨다.
unstack: 로우를 컬럼으로 피벗시킨다.

data = pd.DataFrame(np.arange(6).reshape((2,3)), index = pd.Index(['Ohio','Colorado'], name='state'),
                                         columns = pd.Index(['one','two','three'], name='number'))

data

number	one	two	three
state
Ohio	0	1	2
Colorado	3	4	5

result = data.stack() #컬럼이 로우로 피벗되어서 Series 객체 반환

result

state     number
Ohio      one       0
          two       1
          three     2
Colorado  one       3
          two       4
          three     5
dtype: int64

result.unstack()  #계층적 색인을 가진 Series로부터 다시 DataFrame 얻을 수 있음

number	one	two	three
state
Ohio	0	1	2
Colorado	3	4	5

result.unstack(0)

state	Ohio	Colorado
number
one	0	3
two	1	4
three	2	5

result.unstack('state')

state	Ohio	Colorado
number
one	0	3
two	1	4
three	2	5

해당 레벨에 있는 모든 값이 하위 그룹에 속하지 않을 경우 => unstack을 하게 되면 누락된 데이터 생길 수 있음

s1 = pd.Series([0,1,2,3], index=['a','b','c','d'])

s2 = pd.Series([4,5,6], index=['c','d','e'])

data2 = pd.concat([s1,s2], keys=['one','two'])

data2

one  a    0
     b    1
     c    2
     d    3
two  c    4
     d    5
     e    6
dtype: int64

data2.unstack()

	a	b	c	d	e
one	0.0	1.0	2.0	3.0	NaN
two	NaN	NaN	4.0	5.0	6.0

stack 메서드는 누락된 데이터를 자동으로 걸러냄 => 연산을 쉽게 원상 복구 가능

data2.unstack().stack()

one  a    0.0
     b    1.0
     c    2.0
     d    3.0
two  c    4.0
     d    5.0
     e    6.0
dtype: float64

data2.unstack().stack(dropna=False)

one  a    0.0
     b    1.0
     c    2.0
     d    3.0
     e    NaN
two  a    NaN
     b    NaN
     c    4.0
     d    5.0
     e    6.0
dtype: float64

DataFrame을 unstack()할 때 unstack 레벨은 결과에서 가장 낮은 단계가 됨

df = pd.DataFrame({'left': result, 'right': result+5}, columns = pd.Index(['left','right'], name='side'))

df

	side	left	right
state	number
Ohio	one	0	5
	two	1	6
	three	2	7
Colorado	one	3	8
	two	4	9
	three	5	10

df.unstack('state')

side	left		right
state	Ohio	Colorado	Ohio	Colorado
number
one	0	3	5	8
two	1	4	6	9
three	2	5	7	10

stack 호출할 때 쌀을 축의 이름 지정 가능

df.unstack('state').stack('side')

	state	Colorado	Ohio
number	side
one	left	3	0
one	right	8	5
two	left	4	1
two	right	9	6
three	left	5	2
three	right	10	7

긴 형식에서 넓은 형식으로 피벗하기

db 또는 csv 파일에 여러 개의 시게열 데이터를 저장하는 일반적인 방법: 시간 순서대로 나열

data = pd.read_csv('/Users/cha/Desktop/숙명 데분 스터디/data/macrodata.csv')

data.head()

	year	quarter	realgdp	realcons	realinv	realgovt	realdpi	cpi	m1	tbilrate	unemp	pop	infl	realint
0	1959.0	1.0	2710.349	1707.4	286.898	470.045	1886.9	28.98	139.7	2.82	5.8	177.146	0.00	0.00
1	1959.0	2.0	2778.801	1733.7	310.859	481.301	1919.7	29.15	141.7	3.08	5.1	177.830	2.34	0.74
2	1959.0	3.0	2775.488	1751.8	289.226	491.260	1916.4	29.35	140.5	3.82	5.3	178.657	2.74	1.09
3	1959.0	4.0	2785.204	1753.7	299.356	484.052	1931.3	29.37	140.0	4.33	5.6	179.386	0.27	4.06
4	1960.0	1.0	2847.699	1770.5	331.722	462.199	1955.5	29.54	139.6	3.50	5.2	180.007	2.31	1.19

periods = pd.PeriodIndex(year = data.year, quarter = data.quarter, name = 'date')

columns = pd.Index(['realgdp', 'infl','unemp'], name='item')

data = data.reindex(columns = columns)

data.index = periods.to_timestamp('D','end')

ldata = data.stack().reset_index().rename(columns={0: 'value'})

ldata[:10]

	date	item	value
0	1959-03-31 23:59:59.999999999	realgdp	2710.349
1	1959-03-31 23:59:59.999999999	infl	0.000
2	1959-03-31 23:59:59.999999999	unemp	5.800
3	1959-06-30 23:59:59.999999999	realgdp	2778.801
4	1959-06-30 23:59:59.999999999	infl	2.340
5	1959-06-30 23:59:59.999999999	unemp	5.100
6	1959-09-30 23:59:59.999999999	realgdp	2775.488
7	1959-09-30 23:59:59.999999999	infl	2.740
8	1959-09-30 23:59:59.999999999	unemp	5.300
9	1959-12-31 23:59:59.999999999	realgdp	2785.204

pivot 메서드

pivoted = ldata.pivot('date','item','value')

pivoted

item	infl	realgdp	unemp
date
1959-03-31 23:59:59.999999999	0.00	2710.349	5.8
1959-06-30 23:59:59.999999999	2.34	2778.801	5.1
1959-09-30 23:59:59.999999999	2.74	2775.488	5.3
1959-12-31 23:59:59.999999999	0.27	2785.204	5.6
1960-03-31 23:59:59.999999999	2.31	2847.699	5.2
...	...	...	...
2008-09-30 23:59:59.999999999	-3.16	13324.600	6.0
2008-12-31 23:59:59.999999999	-8.79	13141.920	6.9
2009-03-31 23:59:59.999999999	0.94	12925.410	8.1
2009-06-30 23:59:59.999999999	3.37	12901.504	9.2
2009-09-30 23:59:59.999999999	3.56	12990.341	9.6

203 rows × 3 columns

ldata['value2'] = np.random.randn(len(ldata))

ldata[:10]

	date	item	value	value2
0	1959-03-31 23:59:59.999999999	realgdp	2710.349	0.244226
1	1959-03-31 23:59:59.999999999	infl	0.000	0.962365
2	1959-03-31 23:59:59.999999999	unemp	5.800	0.404761
3	1959-06-30 23:59:59.999999999	realgdp	2778.801	0.471211
4	1959-06-30 23:59:59.999999999	infl	2.340	-0.817099
5	1959-06-30 23:59:59.999999999	unemp	5.100	-0.114613
6	1959-09-30 23:59:59.999999999	realgdp	2775.488	-0.432555
7	1959-09-30 23:59:59.999999999	infl	2.740	-0.918431
8	1959-09-30 23:59:59.999999999	unemp	5.300	0.523383
9	1959-12-31 23:59:59.999999999	realgdp	2785.204	1.649171

pivoted = ldata.pivot('date','item')

pivoted[:5]

	value			value2
item	infl	realgdp	unemp	infl	realgdp	unemp
date
1959-03-31 23:59:59.999999999	0.00	2710.349	5.8	0.962365	0.244226	0.404761
1959-06-30 23:59:59.999999999	2.34	2778.801	5.1	-0.817099	0.471211	-0.114613
1959-09-30 23:59:59.999999999	2.74	2775.488	5.3	-0.918431	-0.432555	0.523383
1959-12-31 23:59:59.999999999	0.27	2785.204	5.6	0.672839	1.649171	1.146470
1960-03-31 23:59:59.999999999	2.31	2847.699	5.2	-1.015282	1.491567	-0.210033

pivoted['value'][:5]

item	infl	realgdp	unemp
date
1959-03-31 23:59:59.999999999	0.00	2710.349	5.8
1959-06-30 23:59:59.999999999	2.34	2778.801	5.1
1959-09-30 23:59:59.999999999	2.74	2775.488	5.3
1959-12-31 23:59:59.999999999	0.27	2785.204	5.6
1960-03-31 23:59:59.999999999	2.31	2847.699	5.2

unstacked = ldata.set_index(['date','item']).unstack('item')

unstacked[:7]

	value			value2
item	infl	realgdp	unemp	infl	realgdp	unemp
date
1959-03-31 23:59:59.999999999	0.00	2710.349	5.8	0.962365	0.244226	0.404761
1959-06-30 23:59:59.999999999	2.34	2778.801	5.1	-0.817099	0.471211	-0.114613
1959-09-30 23:59:59.999999999	2.74	2775.488	5.3	-0.918431	-0.432555	0.523383
1959-12-31 23:59:59.999999999	0.27	2785.204	5.6	0.672839	1.649171	1.146470
1960-03-31 23:59:59.999999999	2.31	2847.699	5.2	-1.015282	1.491567	-0.210033
1960-06-30 23:59:59.999999999	0.14	2834.390	5.2	1.492080	0.398274	-1.866305
1960-09-30 23:59:59.999999999	2.70	2839.022	5.6	2.580628	0.629838	-0.291634

긴 형식에서 긴 형식으로 피벗하기

pandas.melt: pivot과 반대되는 연산, 반드시 어떤 컬럼을 그룹 구분자로 사용할 것인지 지정.

df = pd.DataFrame({'key': ['foo','bar','baz'], 'A':[1,2,3], 'B':[4,5,6], 'C':[7,8,9]})

df

	key	A	B	C
0	foo	1	4	7
1	bar	2	5	8
2	baz	3	6	9

melted = pd.melt(df,['key'])

melted

	key	variable	value
0	foo	A	1
1	bar	A	2
2	baz	A	3
3	foo	B	4
4	bar	B	5
5	baz	B	6
6	foo	C	7
7	bar	C	8
8	baz	C	9

reshaped = melted.pivot('key', 'variable', 'value')

reshaped

variable	A	B	C
key
bar	2	5	8
baz	3	6	9
foo	1	4	7

reshaped.reset_index()

variable	key	A	B	C
0	bar	2	5	8
1	baz	3	6	9
2	foo	1	4	7

pd.melt(df,id_vars=['key'], value_vars=['A','B'])

	key	variable	value
0	foo	A	1
1	bar	A	2
2	baz	A	3
3	foo	B	4
4	bar	B	5
5	baz	B	6

pd.melt(df, value_vars=['A','B','C'])

	variable	value
0	A	1
1	A	2
2	A	3
3	B	4
4	B	5
5	B	6
6	C	7
7	C	8
8	C	9

pd.melt(df, value_vars=['key','A','B'])

	variable	value
0	key	foo
1	key	bar
2	key	baz
3	A	1
4	A	2
5	A	3
6	B	4
7	B	5
8	B	6

[백준 파이썬] 11399번 ATM

Thu, 05 May 2022 08:19:24 GMT

https://www.acmicpc.net/problem/11399

입력 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

sol) 걸리는 시간을 오름차순으로 정렬한 후 차례로 합한다.

n = int(input())  # 사람 수 입력 받기
p = list(map(int, input().split())) # 각 사람이 걸리는 시간 입력 받기

time = 0
p.sort() # 걸리는 시간 오름차순으로 정렬

for i in range(n): 
    for j in range(i+1):
        time += p[j]

print(time)

[코딩테스트] 그리디 알고리즘

Thu, 05 May 2022 08:09:49 GMT

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만을 고르는 방법의 알고리즘
매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향 고려 x
사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 (but 예외로 다익스트라(Dujkstra) 알고리즘은 암기가 필요한 알고리즘)
보통 코딩 테스트에서 해당 알고리즘 유형은 창의력, 최소한의 아이디어를 요구
기준에 따라 좋은 것을 선택해야하기 때문에 문제를 통해 기준 제시 => 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문항은 주로 정렬 알고리즘과 짝을 이뤄 출제가 됨

그리디 알고리즘의 정당성

그리디 알고리즘을 이용했을 때 '최적의 해' 찾을 수 없을 가능성 높음
그리디 알고리즘으로 해를 찾았을 때 해법이 정당한지 검토해야함
대부분 그리디 알고리즘의 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있음

Ex1) 거스름돈

sol) 가장 큰 화폐 단위부터 돈을 거슬러 주기

N원을 거슬러줘야할 때, N=1260

n = 1260
count = 0

#큰 단위의 화폐부터 차례대로 확인 
coin_types = [500, 100, 50, 10]

for coin in coin_types: #화폐의 종류만큼 반복 수행
    count += n//coin  #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

-> 여기서 시간 복잡도가 화폐 종류에 영향 받음. 금액에는 무관.
-> 이 문항을 그리디 알고리즘으로 해결할 수 있는 이유
  : 항상 가지고 있는 동전의 큰 단위가 작은 단위의 배수이기 때문에 
    작은 단위 동전들을 조합하여 다른 해가 나올 수 없음

Ex2) 큰 수의 법칙

배열의 크기 N, 숫자가 더해지는 횟수 M, 같은 인덱스에 해당하는 수가 K번을 초과하여 연속해서 더해질 수 없는 조건을 가질 때 가장 큰 수를 만드는 경우

sol) 입력받은 배열에서 가장 큰 수와 두 번째로 큰 수만을 저장하고, 가장 큰 수를 K번 더한 후 두 번째로 큰 수를 1번 더하는 것을 반복한다.

입력조건 - 첫째 줄에 N (2 $\leq$ N $\leq$ 1,000), M (1 $\leq$ M $\leq$ 10,000),
K (1 $\leq$ K $\leq$ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. - 둘째 줄에는 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다. - 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력조건 - 첫째 줄에 큰수의 법칙을 따라 더해진 값을 출력한다.

n, m, k = map(int, input(),split())  #n,m,k를 공백으로 구분하여 입력받기
data = list(map(int, input().split()) #n개의 수를 공백으로 구분하여 입력받기

data.sort() # 가장 큰 수와 두 번째로 큰 수 찾기 위해 정렬
first = data[n-1]
second = data[n-2]

result = 0

while True:
    for i in range(k): #가장 큰 수 k번 더하기
        if m == 0: #m이 0일 때 반복문 탈출
            break
        result += first 
        m -= 1
    if m == 0 :
        break
    result += second # 두 번째로 큰 수 한 번 더하기
    m -= 1 #더할 때마다 m을 1씩 줄이기

print(result)

여기서 M이 매우 크다면 시간 초과 판정을 받을 것.
이를 해결하기 위해 '반복되는 수열에 대해 파악'
=> 가장 큰 수 K번 + 두 번째로 큰 수 1번; (K+1)번
=> M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수

=> 가장 큰 수가 더해지는 횟수: int (M / (K+1) * K + M % (K+1))

이를 이용한 코드

n, m, k = map(int, input(),split()) 
data = list(map(int, input().split()) 

data.sort() 
first = data[n-1]
second = data[n-2]

#가장 큰 수가 더해지는 횟수 계산 (count)
count = int(m / (k+1) * k + m % (k+1))
count += m % (k+1)

result = 0
result += (count) * first #'횟수*값'을 결과 값에 더하기
result += (m-count) * second

print(result)

Ex3) 숫자 카드 게임

각 행의 여러 개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한 장 뽑는 게임

Rule

숫자가 쓰인 카드들이 N x M 형태로 놓여있다. (N:행, M:열)
먼저 뽑고자 하는 카드가 포함되어 있는 행 선택한다.
그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

sol) 각 행마다 가장 작은 수를 찾은 뒤 그 수 중 가장 큰 수를 찾는다.

입력조건 - 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 $\leq$ N,M $\leq$ 100) - 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력조건 - 첫째 줄에 게임의 룰에 맞게 선택된 카드에 적힌 숫자를 출력한다.

min() 함수를 이용한 코드

n, m = map(int, input(),split()) #N,M을 공백으로 구분하여 입력 받기

result = 0

for i in range(n): #각 행에 대하여
    data = list(map(int, input().split()) # 한 줄씩 입력 받기
    min_value = min(data) #min() 함수 이용하여 현재 행에서 가장 작은 수 찾기
    result = max(result, min_value) # 현재 행에서 찾은 가장 작은 수와 저장되어있던 result 값 중 큰 값 찾기

print(result)

2중 반복문 구조를 이용한 코드

n, m = map(int, input(),split()) 

result = 0

for i in range(n): #각 행에 대하여
    data = list(map(int, input().split()) # 한 줄씩 입력 받기
    min_value = 10001
    for a in data:
        min_value  min(min_value, a)

    result = max(result, min_value) #가장 작은 수들 중 가장 큰 수 찾기

print(result)

Ex4) 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나만을 선택하여 반복적으로 수행한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

N에서 1을 뺀다.
N을 K로 나눈다.

sol) 주어진 N에 대하여 최대한 많이 나누기 (2번을 최대한 많이 실행하기)

입력조건 - 첫째 줄에 N (2 $\leq$ N $\leq$ 100,000)과 K(2 $\leq$ K $\leq$ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이 때, 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력조건 - 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

n, k = map(int, input().split())
result = 0

while n >= k: #N이 K 이상일 때 
    while n % k != 0: #N이 K로 나누어 떨어지지 않을 때
        n-=1 #N에서 1 빼기
        result += 1
    n //= k #N이 K로 나누어 떨어질 때 K로 나누기
    result += 1

while n>1: #N이 K보다 작을 때
    n -= 1 #남은 N에 대하여 1 빼기
    result += 1

print(result)

but 1을 일일이 빼기 때문에 해당 코드에서는 N이 매우 클 때는 시간 초과 판정을 받을 것.

N이 K의 배수가 되도록 한 번에 빼는 방식의 코드

n, k = map(int, input().split())
result = 0

while True:
    # N == (K로 나누어 떨어지는 수) 될 때까지 1 빼기
    target = (n // k) * k
    result += (n - target)
    n = target

    if n





실전문제 #1
각 자리각 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수 구하는 프로그램 작성하시오. 단, 연산자 우선 순위를 고려하지 않고 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정)
sol) 연산하는 두 수 중 하나라도 1 이하일 때는 연산자 '+' 선택, 
           그 외의 경우는 'x' 연산자 선택


입력조건 
    - 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 $\leq$ S의 길이 $\leq$ 20)
출력조건
    - 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.
  

s = input() #문자열 입력 받음

result = int(s[0])  #첫번째 인덱스의 문자를 숫자로 변경하여 대입

for i in range(1, len(s)):
    num = int(s[i]) #i번째 문자를 숫자로 변경하여 대입
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)



출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

	key	data1	data2
0	b	0.0	1.0
1	b	1.0	1.0
2	b	6.0	1.0
3	a	2.0	0.0
4	a	4.0	0.0
5	a	5.0	0.0
6	c	3.0	NaN
7	d	NaN	2.0

	key	data1	data2
0	b	0	1.0
1	b	0	3.0
2	b	1	1.0
3	b	1	3.0
4	a	2	0.0
5	a	2	2.0
6	c	3	NaN
7	a	4	0.0
8	a	4	2.0
9	b	5	1.0
10	b	5	3.0

	key1	key2_x	lval	key2_y	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

	key1	key2_left	lval	key2_right	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

	0	1	2
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0

	one	two	three
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0

	key	data1	data2
0	b	0.0	1.0
1	b	1.0	1.0
2	b	6.0	1.0
3	a	2.0	0.0
4	a	4.0	0.0
5	a	5.0	0.0
6	c	3.0	NaN
7	d	NaN	2.0

	key	data1	data2
0	b	0	1.0
1	b	0	3.0
2	b	1	1.0
3	b	1	3.0
4	a	2	0.0
5	a	2	2.0
6	c	3	NaN
7	a	4	0.0
8	a	4	2.0
9	b	5	1.0
10	b	5	3.0

	key1	key2_x	lval	key2_y	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

	key1	key2_left	lval	key2_right	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

	0	1	2
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0

	one	two	three
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0

	key	data1	data2
0	b	0.0	1.0
1	b	1.0	1.0
2	b	6.0	1.0
3	a	2.0	0.0
4	a	4.0	0.0
5	a	5.0	0.0
6	c	3.0	NaN
7	d	NaN	2.0

	key	data1	data2
0	b	0	1.0
1	b	0	3.0
2	b	1	1.0
3	b	1	3.0
4	a	2	0.0
5	a	2	2.0
6	c	3	NaN
7	a	4	0.0
8	a	4	2.0
9	b	5	1.0
10	b	5	3.0

	key1	key2_x	lval	key2_y	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

	key1	key2_left	lval	key2_right	rval
0	foo	one	1	one	4
1	foo	one	1	one	5
2	foo	two	2	one	4
3	foo	two	2	one	5
4	bar	one	3	one	6
5	bar	one	3	two	7

	0	1	2
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0

	one	two	three
a	0.0	NaN	NaN
b	1.0	NaN	NaN
c	NaN	2.0	NaN
d	NaN	3.0	NaN
e	NaN	4.0	NaN
f	NaN	NaN	5.0
g	NaN	NaN	6.0