본문 바로가기
728x90

전체 글224

<PART 2>그래프이론 예제 팀 결성 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용할 수 있다. 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다. 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인'연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오 입력 조건: 1. 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. 2. '팀 합치기' 연산은 0 a b 형태로 주어진다. 3. '같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 출력 .. 2022. 11. 13.
<PART 2> 그래프이론(위상 정렬) 위상 정렬: 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것 위상 정렬은 정렬 알고리즘의 일종입니다. 순서가 정해져 있는 일련의 작업을 차례대로 수행할 때 사용할 수 있는 알고리즘입니다. 또한, 시간 복잡도는 O(V+E)입니다. 1. 진입차수가 0인 노드를 큐에 넣습니다. 2. 큐가 빌 때까지 다음의 과정을 반복합니다. 2-1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거합니다. 2-2) 새롭게 진입차수가 0이 된 노드를 큐에 넣습니다. 이처럼 진입차수가 0인 노드부터 실행합니다. 만약에 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면, 답이 여러가지가 될 수 있다는 특징을 가집니다. (3,4)의 간선이 없다면 1-2-4-3-5, 1-4.. 2022. 11. 13.
<PART 2> 그래프이론 (크루스칼 알고리즘) 신장 트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이처럼 맨 위의 그래프에서는 여러 개의 신장 트리를 찾을 수 있습니다. 신장 트리가 아닌 부분은 1개의 노드라도 포함시키지 않거나 노드간에 사이클이 존재할 때입니다. - 크루스칼 알고리즘 크루스칼 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 알고리즘 1. 간선 데이터를 비용에 따라 오름차순으로 정렬합니다. 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인합니다. 2-1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킵니다. 2-2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않습니다. 3. 모든 간선에 대하여 2번의 과정을 반복합니다. 크루스칼 알고리즘의 핵심 .. 2022. 11. 12.
<PART 2>그래프이론 (서로소 집합) 그래프: 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 DFS/BFS, 최단경로 알고리즘에서 다룬 내용은 모두 그래프 알고리즘의 한 유형이라고 생각할 수 있습니다. 즉, 여기서 다룰 알고리즘은 앞서 배운 내용에 기반한 내용입니다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘은 앞서 배운 큐 자료구조 혹은 스택 자료구조를 활용해야 구현할 수 있습니다. 알고리즘 문제에 접했을 때 서로 다른 개체(혹은 개체)가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 합니다. 예를 들어 '여러 개의 도시가 연결되어 있다'와 같은 내용이 등장하면 그래프 알고리즘을 의심해야 합니다. 그래프 자료구조 중에 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억해.. 2022. 11. 12.
<PART 2>최단 경로 알고리즘 예제 미래도시 방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있습니다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사 끼리는 서로 도로를 통해 연결되어 있습니다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 합니다. - 특정 회사에 도착하는 방법은 회사끼리 연결되어 있는 도로를 이용해야만 함 - 연결된 2개의 회사는 양방향 이동가능 - 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동가능 또한, 방문 판매원 A는 기대하던 소개팅에도 참석하고자 합니다. 소개팅의 상대는 K번 회사에 존재합니다. 따라서 방문판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표입니다. 이때 가.. 2022. 11. 8.
<PART 2> 최단 경로 알고리즘 (플루이드 워셜) 다익스트라 알고리즘: 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘 플로이드 워셜 알고리즘: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘 플로이드 워셜 알고리즘은 소스코드가 매우 짧아서 다익스트라 알고리즘과 비교하면 구현 과정에서 어려움을 겪지는 않을 것입니다. 다만, 핵심 아이디어를 이해하는 것이 중요합니다. 다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용하였습니다. 반면에 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 다르게 2차원 리스트에 '최단 거리'정보를 저장한다는 특징이 있습니다. 모든 노드에 대하여 다른 모든.. 2022. 11. 8.
<PART 2> 최단 경로 알고리즘 (다익스트라) 최단경로: 말 그대로 가장 짧은 경로를 찾는 알고리즘 최단 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있습니다. 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'등의 다양한 사례가 존재합니다. 최단 경로 알고리즘은 보통 그래프로 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현됩니다. 또한, 실제 코딩 테스트에서는 최당 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제 됩니다. 컴공과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플.. 2022. 11. 8.
<PART 2> 다이나믹 프로그래밍 예제 1로 만들기 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지입니다. A. X가 5로 나누어떨어지면, 5로 나눈다. B. X가 3으로 나누어떨어지면, 3으로 나눈다. C. X가 2로 나누어떨어지면, 2로 나눈다. D. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 합니다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어 정수가 26이면 1. 26-1=25 2. 25/ 5 = 5 3. 5/ 5 =1 으로 3번의 연산이 최솟값입니다. (1 2022. 11. 7.
<PART 2> 다이나믹 프로그래밍 다이나믹 프로그래밍, 동적 계획법: 연산속도와 메모리공간 최대한 활용하는 방법 이는 중복되는 연산을 줄일 수 있습니다. 다이나믹 프로그래밍의 기본적인 아이디어를 먼저 소개한 후에 2가지 방식인 탑다운, 바텀업을 설명할 것입니다. 여기서의 다이나믹의 뜻은 '프로그램이 실행되는 도중에'라는 의미입니다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있습니다. 우선 피보나치 수열을 코드로 간단한게 표현하면 다음과 같습니다. 이처럼 단순히 재귀함수를 사용하여서 해결할 수 있습니다. 그러나 여기서 n이 기하급수적으로 커지면 시간 표기법이 O(2^N)정도로 올라가서 심각한 문제가 생길 수 있습니다. 항상 다이나믹 프로그래밍을 사용할 수 없으며, 다음 조건을 만족할 때 사용할 수 있습니다. .. 2022. 11. 7.
<PART 2> 이진탐색-예제 부품찾기 전자 매장에는 부품이 N개 있습니다. 그리고 부품마다 고유 부품 번호가 존재합니다. 여기서 손님이 M개의 부품과 고유 부품 번호를 물어봐서 각각이 있는지 확인해야 합니다. 있으면 yes, 없으면 no를 출력하는 프로그램을 작성해봅니다. (1 start,end(14,14)->(15,14) 원하는 total=7일때 start,end가 15라면-> (total start,end(15,15)->(15,14) 가 되서 결국 같은 값으로 되기 때문에 /2만 하면 덜 잘려지는 14가 된다. - 재귀함수가 아닌 for문을 이용한 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 n,m= list(map(int,input().spl.. 2022. 11. 6.
<PART 2> 트리 자료구조 데이터 베이스는 내부적으로 대용량 데이터 처리에 적합한 트리자료구조를 이용하여 항상 데이터가 정렬되어 있습니다. 따라서 데이터 베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠릅니다. 트리 자료구조는 노드와 노드의 연결로 표현합니다. 1. 트리는 부모 노드와 자식 노드의 관계로 표현합니다. 2. 트리의 최산당 노드를 루트 노드라고 합니다. 3. 트리의 최하단 노드를 단말노드라고 합니다. 4. 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 합니다. 5. 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합합니다. 정리하자면 큰 데이터를 처리하는 소프트웨어는 대부분 데.. 2022. 11. 6.
<PART 2> 이진 탐색: 범위를 반씩 좁혀가는 탐색 이진 탐색: 리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘 이진탐색을 공부하기 전에 순차 탐색을 먼저 이해할 필요가 있습니다. 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용합니다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있습니다. 그러므로 시간 복잡도는 O(N)입니다. count() 메서드도 내부에서는 순차 탐색이 수행됩니다. 위와 같이 처음부터 찾는 것을 순차탐색이라 합니다. - 이진 탐색 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 위치를 나타내는 변수 3개를 사용하는데.. 2022. 11. 5.
<PART 2> 정렬 예제 위에서 아래로 하나의 수열에는 다양한 수가 존재합니다. 이러한 수는 크기에 상관없이 나열되어 있습니다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 합니다. 수열을 내림차 순으로 정렬하는 프로그램을 만드시오 입력예시) 3 15 27 12 출력예시) 27 15 12 1 2 3 4 5 6 7 8 n = int(input()) array = [] for i in range(n): array.append(int(input())) array = sorted(array,reverse=True) for i in array: print(i, end= " ") cs 풀이 생략 배운 점: 출력할 때 리스트를 한 개씩 꺼내서 원소 한 개씩 출력시킬 때 위의 코드대로 하면 편리하다. 성적이 낮은 순서로 학생 출력하기 N명의.. 2022. 11. 5.
<PART 2> 정렬 정렬:데이터를 특정한 기준에 따라서 순서대로 나열하는 것 데이터를 가공할 때 오름차순, 내림차순 등으로 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램 작성할 때 가장 많이 사용되는 알고리즘 중 하나입니다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해집니다. 정렬의 종류가 많지만 선택정렬, 삽입정렬, 퀵정렬, 계수정렬만 적겠습니다. - 선택 정렬 데이터가 무작위로 있을 때, 가장 작은 데이터를 맨 왼쪽 데이터와 자리를 교환합니다. 그다음은 맨 왼쪽 데이터를 제외한 숫자 중에서 가장 작은 값과 그 다음 왼쪽의 값을 서로 바꿉니다. 이 과정을 반복합니다. 위는 저의 방법, 아래는 책의 방법입니다. 저는 맨왼쪽이 최솟값이면 그대로 두고 아니라면 temp를 두어서 바꿔주.. 2022. 11. 5.
<PART 2> DFS/BFS 예제 음료수 얼려먹기 N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 입력예시) 5 5 10101 00110 10101 01101 11111 출력예시) 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #크기 입력받기 n,m = map(int,input().split()) #2차원 리스트의 맵 정보 입력 받기 graph =[] for i in range(n): graph.append(list(map(int,input()))) count = 0 #dfs 정의 def.. 2022. 11. 5.
728x90

티스토리툴바