문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 3가지 풀이 방법으로 풀었다. BFS 풀이방법이 실행시간이 제일 짧았으며 그 다음은 DFS, 마지막으로 플로이드-와샬 알고리즘을 사용한 방법이 제일 느렸다. 먼저 BFS로 푼 방법이다. 각 정점마다 방문했는지 visited에 저장하고 간선으로 해당 정점이 연결되어 있다면 check에 1을 기록하였다. 이때 visited는 각 정점을 방문하면서 방문했는지 기록해야 한다. # BFS from collections import deq..
분류 전체보기
문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 지역의 높이를 리스트로 입력받으면서 가장 큰 값을 찾음 1부터 가장 큰 값까지 물에 잠기지 않는 범위를 DFS/BFS 알고리즘을 통해 찾아서 결과 리스트에 저장 결과 리스트 중에서 가장 큰 값이 문제에서 찾고자 하는 답. # DFS 사용 import sys sys.setrecursionlimit(100000) n = int(input()) graph = [] max_num = 0 result ..
File System Implementation Allocation methods : File 저장을 위한 디스크 공간 할당 방법 Free space management : 디스크의 빈 공간 관리 Allocation Methods 연속된 공간 할당 (Continuous allocation) 비연속적인 공간 할당 (Discontinuous allocation) Linked allocation Indexed allocation Continuous Allocation 한 File을 디스크의 연속된 block에 저장 장점: 효율적인 file 접근 (순차, 직접 접근), (연속적인 것을 알고 있기 때문에) 문제점 새로운 file을 위한 공간 확보가 어렵다 (10개짜리 file을 넣을 때 compact해줘야 한다...
문제 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 오답 풀이 (시간초과) 아래 풀이는 시간초과가 발생한 풀이이다. 단순하게 i 번째 원소가 i+1 번째부터 전체 원소까지 탐색할 때 큰 원소를 만나면 인덱스 사이의 거리를 구해 결과에 추가하는 방법으로 코드를 작성하였는데 이렇게 하면 너무 많이 for문을 돌아서 시간초과가 발생한다. import sys input = sys.stdin.readline from collections imp..
문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 printer 순서를 저장할 큐를 생성 후에 여기에 프린터 중요도를 순서대로 입력한다 인덱스 번호를 저장할 큐를 생성하고 0부터 n-1까지 입력한다. 주의할 점은 프린터 중요도는 1이상 9 이하 숫자이며 프린터 인덱스 번호는 0부터 n-1까지이며 프린터 출력 순서는 1부터 n까지 이다. 현재 프린터 큐에서 몇 번째에 문서가 놓여있는지를 나타내는 M이 0부터 N 사이이다. (M을 0부터 N ..
문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제란? 1차 유대-로마 전쟁 당시 요세푸스(Flavius Josephus)는 동료 40명과 함께 로마군에게 포위됐다. 이들은 투항하는 대신, 제비를 뽑아 둥글게 둘러 앉은 후 두 명씩 건너 뛰고 세 번째마다 자살하기로 하였다. 이렇게 하여 39명이 죽은 뒤 요세푸스는 아직 살아남은 동료와 투항했고, 훗날 역사가가 되어 이 일을 기록에 남겼다고 한다. [네이버 지식백과] 요세푸스 문제 (365일 수학) 이를 애니메이션으로 나타내면 다음과 같다. 이미지 출처: The Jose..
Palindrome 알고리즘이란? 팰린드롬(회문) 은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다 - https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8 구현 def palindrome(a): if a == a[::-1]: return True else: return False print(palindrome([w for w in input()])) 이를 짧게 풀어서 다음과 같이 나타 낼 수 있다. def is_palindrome(word): return word[::-1]==word # True print( is_palindrome("kayak") ) print( is_palindrome("mad..
문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 시도한 풀이 (시간 초과) 리스트를 사용하면 시간 초과가 생길 것 같아 리스트보다 시간복잡도가 유리한 딕셔너리를 이용하였다. 생각과 다르게 시간초과가 발생하였는데 혼자서 고민하여 답을 찾을 수 없어 질문탭에서 확인하였다. 힌트를 찾을 수 있었다. "dict를 쓰지 않고 단순히 pair로 list에 저장한 것과 차이가 없는 코드입니다. 입력을 받으면 그걸 키로 직접..
문제 https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 제출한 풀이 A B C D E F 는 0, 1, 2, 3, 4, 5 인덱스를 부여하고 0이 마주보는 면을 5, 1이 마주보는 면을 3, 2가 마주보는 면을 4 ... 이런식으로 딕셔너리에 해당면의 짝을 지정함 맨 아래 면을 1부터시작하여 맨 아래 면과 마주보는 면을 옆면에 올 수있는 면 리스트에서 제외하면 4개의 면이 남는데 이 중 가장 큰 면을 max_dice_list에 저장함. 맨 아래 주사위..
문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 제출한 풀이 import sys input = sys.stdin.readline n, m = map(int, input().split()) num_list = list(map(int, input().split())) sum_list = [0] * (n+1) sum_list[1] = num_list[0] for i in range(2, n+1): sum_list[i] =..
