Dev_Diary

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적인 그래프 탐색 문제인데 추가 작업이 몇 개 있다. 물의 수위를 바꿔가며 반복적으로 카운팅을 해주면 된다. def solution(N, field): # 최대 지역 수 max_cnt = 0 # 물의 수위 max_water = max([max(row) for row in field]) # 물의 수위를 변경해가며 for water in range(max_water+1): # 지역 수 cnt = 0 # ..

절차적 프로그래밍 개념 절차적 프로그래밍은 절차지향 프로그래밍 혹은 절차지향적 프로그래밍이라고도 불립니다. 또 명령형 프로그래밍과 동의어로 쓰이기도 합니다. 그리고 일반적으로 프로시저 호출의 개념을 바탕으로 하는 프로그래밍 패러다임을 뜻합니다. 프로시저는 루틴, 서브루틴, 메서드, 함수 등으로 부르기도 합니다. 수행되어야 할 계산과정들을 포함하고 있고 아무 위치에서나 호출할 수 있으며 다른 프로시저, 자기 자신에서도 호출할 수 있다는 특징이 있습니다. 특징으로는 모듈성이 있는데, 코드의 재사용성이 늘어나고 프로그램의 흐름을 더 쉽게 파악할 수 있게 됩니다. 입력과 출력 그리고 그 사이의 규칙을 정하여 구현하는데 일반적으로 쓰는 함수가 그렇습니다. 또 스코프 개념을 통해 변수를 보호하고 프로시저 사이의 독..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제는 전형적인 그래프 탐색 문제입니다. BFS 와 DFS 중 적절하게 선택해 풀면 됩니다. # BFS 쓸거라 deque from collections import deque def solution(F, S, G, U, D): # 선택지 selects = [U, -D] # 방문한 위치 visited = [1 if floor != S else 0 for floor in range(F+1)] que = deq..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 전형적인 그래프 탐색 문제입니다. 일반적으로 DFS, BFS 중 선택해서 풀면 됩니다. def solution(a, b, n, m, data_list): # 방문기록 visited = [1 for _ in range(n+1)] visited[a] = 0 # 트리 tree = [[] for _ in range(n+1)] for parent, child in data_list: t..

명령형 프로그래밍 개념 명령형 프로그래밍은 선언형 프로그래밍과 반대되는 개념입니다. 프로그래밍의 상태와 상태를 변경시키는 구문의 관점에서 연산을 설명하는 프로그래밍 패러다임인데, 쉽게 설명하자면 컴퓨터가 수행할 명령들을 순서대로 써 놓은 것입니다. 즉 '어떻게' 수행할지에 주목하는 패러다임이라고 할 수 있습니다. 한번 조금만 더 쉽고 대략적으로 이해해보겠습니다. 어떤 리스트 안에 속한 수들의 합을 구할 때, 아래의 방식으로 for 문을 이용해 합을 구할 수 있습니다. 이런 일반적으로 풀어서 쓴 방식을 명령형 프로그래밍이라고 보면 될 것 같습니다. nums = [1, 2, 3, 4, 5] sum_nums = 0 for num in nums: sum_nums += num 거의 대부분의 하드웨어들은 기계어를 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 냅색 알고리즘이라고 불리는 알고리즘의 전형적인 문제입니다 간단하게 설명하자면 무게와 물체 두 축을 가진 2차원 memoization 이라고 할 수 있습니다. # 배낭문제 (냅색 알고리즘) def solution(N, K, objects): # 정렬 objects = sorted(objects, key=lambda x: (..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 기본 아이디어는 '무작위로 뽑아서 계산하지 말고 테이블 둘째 줄에 적혀있는 수로 이동하면 적어도 하나의 수는 첫째줄 집합에 포함된다' 입니다. 이런 아이디어를 갖고 어떻게 구현할지 생각해보니 단순히 DFS, 즉 스택을 이용하면 될 것 같다는 생각이 들었습니다. def solution(N, table): # 스택 리스트 stack_list = [] # 자신의 값을 가지면 미리 넣어두기 ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 수가 들어올 때 마다 정렬이 되어야 한다 그러므로 정렬에 많은 시간이 소요되면 안된다 다른 순서는 필요없고 중간만 맞으면 된다 라는 특성이 문제를 푸는데 가장 중요한 포인트였습니다. 우선 힙(우선순위큐)를 사용했는데, 이유는 다음과 같습니다. 수가 들어올 때 마다 정렬이 되어야 한다 -> 힙 삽입으로 해결 정렬에 많은 시간이 소요되면 안된다 -> 힙 정렬로 해결 다른 순서는 필요없..

https://www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 따로 핵심 아이디어는 없었고 구현만 하면 풀 수 있는 문제였습니다. 다만 몇 번째인지 구할 때 십자수가 아닌 수를 주의하면 쉽게 풀 수 있습니다. def solution(card): clock_num = find_min(card) return count_min(clock_num) # 시계수 찾기 def find_min(card): min_card = int(card) # 카드 돌리면서 최솟값 찾기 for _ in range..

구조적 프로그래밍 개념 구조적 프로그래밍은 절차적 프로그래밍 혹은 절차지향적 프로그래밍이라 불리는 패러다임의 하위 개념으로 볼 수 있는 프로그래밍 패러다임입니다. 비 구조적 프로그래밍의 문제점을 해결하고자 등장했으며 역사적으로 몇가지 다른 구조화 기법과 방법론이 개발되어왔는데, 가장 일반적인 세 가지는 다음과 같습니다. 잭슨의 구조적 프로그래밍 다익스트라의 구조적 프로그래밍 다익스트라의 관점에서 파생된 관점 하지만 대부분의 구조적 프로그래밍이라고 말하는 것은 첫 번째를 제외한 둘 중의 하나를 말하는 것인데, 일반적으로는 GOTO문을 없애거나 GOTO문에 대한 의존성을 줄여주는 것으로 유명합니다. 흐름제어를 사용하지 않기때문에 코드의 가독성이 좋고 유지보수가 쉬우며, 재사용성도 높습니다. 다익스트라는 Go..