IT&컴퓨터공학/자료구조&알고리즘
-
[알고리즘] Level3 ) 섬 연결하기 - C++IT&컴퓨터공학/자료구조&알고리즘 2021. 2. 14. 22:24
Level 3으로 올라오니 확 어려워진 느낌이 든다. 상식으로 풀기보다 문제를 읽고 아 ! 이건 어떤 알고리즘으로 접근하면 되겠다. 라는 생각이 들도록 노력해야겠다. 무튼 이번 문제는 수업때 듣고 이제는 기억이 가물가물한.. 최소신장트리를 이용한 문제다. 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다...
-
[알고리즘] 최소신장트리 구하기 - 크루스칼 알고리즘 C++IT&컴퓨터공학/자료구조&알고리즘 2021. 2. 14. 22:09
앞에서 최소신장트리를 구하는 두가지 알고리즘을 살펴봤다. 두개 중 먼저 크루스칼 알고리즘을 구현해보려 한다. 크루스칼 알고리즘 크루스칼 알고리즘은 간선의 cost 를 오름차순으로 정렬하고 제일 cost가 싼 간선 순서대로 연결시키는 알고리즘이다. 이때 사이클이 만들어지면 안되므로, 간선 추가 시 사이클이 발생하는지를 판단하는 알고리즘이 따로 필요한데, 이는 Union Find 를 이용하면 된다 Union Find 총 1 부터 10까지 10개의 노드가 존재한다. 노드는 서로 연결되어 있는데, 1-2-3-4 5-6-7-8 9-10 총 3 그룹으로 나눌 수 있다. 여기서 우리는 Parent[] 라는 배열을 사용하는데, 윗칸은 노드의 번호 , 아래칸은 해당 노드의 부모 노드를 의미한다. 연결정보를 갱신하는데, ..
-
[알고리즘] 최소 신장 트리IT&컴퓨터공학/자료구조&알고리즘 2021. 2. 14. 20:43
신장트리 Spanning Tree 라고 불린다. original 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프 신장트리의 조건 본래의 그래프의 모든 노드를 포함해야 한다. 모든 노드가 연결되어있어야 하지만 사이클이 존재하지 않아야 한다 ( 트리 이므로 ) 최소 신장트리 MST 라고 불린다. 가능한 신장트리 중에서 간선의 가중치 합이 최소인 신장트리 최소 신장트리를 찾는 알고리즘 2개 크루스칼 알고리즘 프림 알고리즘 크루스칼 알고리즘 모든 간선들의 가중치를 오름차 순으로 정렬 가중치가 가장 작은 간선을 선택 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다. ( 이때 사이클이 만들어지면 안된다 !) 이 과정을 반복 프림 알고리..
-
[알고리즘] Level 3) 삼각달팽이 - C++IT&컴퓨터공학/자료구조&알고리즘 2021. 1. 26. 21:30
문제 설명 정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 1,000 이하입니다. 입출력 예 4 [1,2,9,3,10,8,4,5,6,7] 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] 접근방법 - 달팽이를 채우는 방법을 그대로 생각해보자 ! state 가 0 일때 : 아래로 이동 state 가 1 일때 : 오른쪽으로 이동 state 가 2..
-
[알고리즘]Level2 ) [3차]파일명 정렬 - C++IT&컴퓨터공학/자료구조&알고리즘 2021. 1. 17. 22:46
파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다. 버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 [img12.png, img10.png, img2.png, img1.png]일 경우, 일반적인 정렬은 [img1.png, img10.png, img12.png, img2.png] 순이 되지만, 숫자 순으로 정렬된 [img1.png, im..
-
[알고리즘] C++ STL ) sort 와 stable_sort 의 차이IT&컴퓨터공학/자료구조&알고리즘 2021. 1. 17. 22:33
sort : 퀵 소트 기반 알고리즘 : 정렬 알고리즘 중에서 인덱스가 변경되는 알고리즘 ex ) selection , quick, heap sort 의 경우 unstable 하다. 특히, 각 문자가 같은 경우 뭐가 앞으로 올지 알 수 없음 ! stable_sort : 머지소트 기반 알고리즘 -> 즉 안정적인 정렬 ( 같은 원소값의 순서 보장 ) 이 필요하면 이걸 사용하자 ! 일반적으로 sort 가 더 빠르긴 하다
-
[알고리즘] Level 2 ) 짝지어 제거하기 - C++IT&컴퓨터공학/자료구조&알고리즘 2021. 1. 14. 19:23
문제 설명 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다. 제한사항 문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다. ..
-
[알고리즘]Level2 ) 피보나치 수IT&컴퓨터공학/자료구조&알고리즘 2021. 1. 14. 14:26
문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 제한 사항 * n은 1이상, 100000이하인 자연수입니다. 입출력 예 3 2 5 5 입출력 예 설명 피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 ..