알고리즘16

• 

  [Programmers Level1] 콜라 문제(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] 오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다. 정답은 아무에게도 말하지 마세요. 콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가? 단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다. 문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을.. PS/Programmers 2022. 11. 22.

• 

  [BaekJoon 2252번] 줄 세우기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net [문제 설명] N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 .. PS/BaekJoon 2022. 10. 11.

• 

  [Algorithm] 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)에 대해서 공부하고 정리한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 위상 정렬(Topology Sort)이란? 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬입니다. 쉽게 이야기 하자면 '순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 그 순서를 정렬하기 위해 사용합니다. 위상 정렬의 실생활 예시는 대학교의 선수 과목 구조를 예로 들 수 있습니다. 웹 프로그래밍 과목을 듣기 위해 컴퓨터 기초, 컴퓨터 프로그래밍 그리고 UNIX 시스템 과목을 먼저 들어야 합니다. 이렇게 순서가 있는 작업이 있을 때 작업을 정확하게 정렬해주는 위상 정렬 알고리즘을 사용합니다. 위 예시의 순서를 찾는다면 아.. Algorithm 2022. 10. 11.

• 

  [BaekJoon 2230번] 수 고르기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net [문제 설명] N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M .. PS/BaekJoon 2022. 9. 22.

• 

  [Algorithm] LCS(최장 공통 부분 수열) LCS(최장 공통 부분 수열)에 대해서 공부하고 정리한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! LCS(최장 공통 부분 수열)이란? '두 문자열을 비교할 때 공통적으로 나타나는 부분 문자열 중 가장 긴 것' 이해를 위해 예를 들어 "ACAYKP" 문자열과 "CAPCAK" 문자열이 주어졌다면, ACAYKP CAPCAK 두 문자열을 비교할 때 공통적으로 나타나는 부분 문자들 중 가장 긴 것은 ACAK이고 길이는 4입니다. LCS(최장 공통 부분 수열) 동작 과정(LCS 길이 구하기) 위에서 예를 든 "ACAYKP"와 CAPCAK" 문자열의 LCS 길이를 구한다면 어떻게 구해야할지 생각해봅시다. ↪ LCS는 다이나믹 프로그래밍을 이용하여 풀 수 있는데, 2차원 배.. Algorithm 2022. 9. 10.

• 

  [Algorithm] 크루스칼(Kruskal) 크루스칼 알고리즘에 대한 내용을 정리해보려고 합니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! 크루스칼 알고리즘이란? 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그리디 알고리즘으로 분류됩니다. 그렇다면 크루스칼 알고리즘에 대해서 생각해봅시다. 아래 그림과 같은 그래프를 가장 적은 비용으로 모든 노드를 연결하기 위해선 어떻게 해야할까요? 의외로 간단합니다. 간선의 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. ↪ 간선 정보를 오름 차순으로 정렬하고 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. 일단 위 그림과 같이 모든 간선 정보를 저장합니다. 노드 1번부터 7번까지의 모든 간선 정보를 저장한 것이고, 노드6.. Algorithm 2022. 9. 5.

• 

  [Algorithm] 이분 탐색(Binary Search) 이분 탐색에 대한 내용을 정리해보려고 합니다. 이분 탐색 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법입니다. 이분 탐색을 사용해야하는 이유 ? 우리가 일반적으로 알고있는 선형 탐색의 경우에는 앞에서부터 순차적으로 탐색하기 때문에 시간 복잡도는 배열의 원소의 개수 만큼(O(n))이 됩니다. 만약 원소의 개수가 무수히도 많아진다면 굉장히 비효율적인 알고리즘이 되겠죠. 하지만 이분 탐색은 탐색 범위를 절반으로 나누어서 탐색하기 때문에 시간 복잡도는 O(log n)로 탐색이 가능합니다. 이분 탐색 동작 이분 탐색의 동작을 알아보도록 하겠습니다. 예를 들어서 배열 arr = {1, 3, 5, 7, 9, 10, 13, 15} .. Algorithm 2022. 8. 31.

• 

  [BaekJoon 18352번] 특정 거리의 도시 찾기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net [문제 설명] 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호.. PS/BaekJoon 2022. 8. 29.

• 

  [Algorithm] 유니온 파인드(Union-Find) 그래프 알고리즘 중 Union-Find 에 대해서 공부한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 유니온 파인드(Union-Find)란? 여러개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속해있는지 판별하는 알고리즘입니다. 그래프에서 사이클이 존재하는지 여부를 판별할 때 유용하게 사용됩니다. 유니온 파인드(Union-Find) 그림 설명 위 그림과 같이 여러개의 노드가 모두 연결되지 않고, 자기 자신만을 집합의 원소로 가질 때 모든 값이 자기 자신을 가르키도록 합니다. 그리고 표를 보면 i는 노드 번호, parent[i]는 부모 노드 번호를 의미합니다. 즉, 자기 자신이 어떤 부모에 포함되어있는지를 의미합니다. 자 이제, .. Algorithm 2022. 8. 28.

• 

  [Algorithm] 다익스트라(Dijkstra) 다익스트라 알고리즘을 공부한 내용을 바탕으로 작성한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! 다익스트라(Dijkstra)란? 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 중 하나입니다. 도착 정점뿐만아니라 다른 모든 정점을 방문하며 각 정점까지의 최단 경로를 찾게됩니다. 동작 과정 1. 출발 정점과 도착 정점을 정합니다. 2. '최단 거리 테이블'을 초기화합니다. 3. 현재 정점에서 인접한 정점 중 방문하지 않은 정점들을 구별하고 방문하지 않은 정점들 중 가장 최단 거리의 정점을 선택합니다. 4. 해당 정점을 거쳐서 특정한 정점으로 가는 경우를 고려하여 최단 거리를 업데이트합니다. 5. 3~4번을 반복합니다. 동작 예시 출발 정점은 .. Algorithm 2022. 8. 23.

• 

  [Algorithm] 최장 증가 부분 수열(LIS) DP 문제인 LIS 문제를 풀기 위해 LIS 알고리즘을 공부했습니다. 제가 공부한 내용을 바탕으로 작성했습니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 최장 증가 부분 수열(LIS)이란? 수열이 주어지고 해당 수열에서 몇개의 수를 제거했을 때 부분 수열을 만들 수 있습니다. 부분 수열 중에서 오름 차순으로 정렬되고, 길이가 가장 긴 부분 수열을 최장 증가 부분 수열(LIS)이라고 합니다. 그렇다면 이해를 위해 예를 들어보도록 하겠습니다. {3, 5, 7, 9, 2, 1, 4, 8} 수열이 있습니다. 몇개의 수를 제거하여 부분 수열을 만들면 {3, 5, 7, 9, 2} {5, 7, 9} {3, 5, 7, 8} {3, 5, 7, 9} 등을 만들 수 있습니다. ✔ {3, 5,.. Algorithm 2022. 8. 17.

• 

  [Algorithm] 에라토스테네스의 체 위 짤은 인터넷을 돌아다니다가 재밌어서 가져와봤습니다. 무튼 글을 시작하자면 알고리즘 문제를 풀다보면 소수 판별하라는 문제가 종종 보입니다. 해당 문제를 해결하기 위해선 소수 판별하는 알고리즘을 사용해야 합니다. 그래서 알고리즘 중에 '에라토스테네스의 체'가 가장 시간 복잡도도 우수하기 때문에 머릿속에 저장할 겸 정리해보려고 합니다. 목차 소수란 에라토스테네스의 체에 대해서 에라토스테네스의 체 구현(C++) 소수란 소수는 1과 자기 자신만을 약수를 갖는 1보다 큰 자연수입니다. (참고로 1은 소수가 아닙니다.) 에라토스테네스의 체에 대해서 에라토스테네스의 체는 이름 그대로 무언가를 찾기 위해 체를 걸러내듯, 소수를 찾는 방법입니다. 알고리즘은 2부터 찾고자하는 수까지 나열하고 1을 지웁니다. 1 다음으로.. Algorithm 2022. 8. 2.