[백준 1786번] - 찾기(C/C++)
2022. 11. 7. 00:55
Problem Solving/백준
1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net [문제 설명] [문제 풀이] 해당 문제는 KMP알고리즘을 이용하여 문자열 패턴 매칭을 하는 문제이다. 따라서 KMP 알고리즘에 대한 이해가 필요하다. 혹시 해당 알고리즘에 대해 잘 모른다면 아래 포스트를 참고하길 바란다. [Algorithm] - 문자열 탐색 알고리즘 : KMP 이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열..
[Algorithm] - 문자열 탐색 알고리즘 : KMP
2022. 11. 7. 00:43
Problem Solving/Algorithm
이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열을 검색할 때, 특정 단어를 검색엔진에서 검색할때도 사용될 수 있다. 해당 알고리즘의 시간복잡도는 O(N+M)을 가진다. 구현 KMP 알고리즘은 접두사(prefix)와 접미사(suffix)의 개념을 활용하여 실패함수 테이블을 만들고, 테이블을 활용하여 반복되는 문자열을 건너뛰면서 패턴을 찾는 알고리즘이다. 접두사와 접미사에 대해 간단하게 정리해보고자 예를 들어보겠다. "abacabab"라는 문자열이 있다고 가정하자. 우리는 각 문자의 길이에 따라 접두사와 접미사가 일치하는 최대 길이를 테이블에 저장할 것이다. 실패함수 테이블을..
[Algorithm] - 문자열 검색 알고리즘 : Naive String Search
2022. 10. 21. 05:54
Problem Solving/Algorithm
이론 문자열 검색 알고리즘이란, 어떤 문자열 S에서 패턴 P가 있는지 찾아내는 알고리즘이다. Naive String Search 알고리즘은 문자열 검색 알고리즘 중에 효율이 좋지 않지만, 가장 구현하기 쉽고 작은 입력이라면 충분히 고려해볼만 한 알고리즘이다. 전체 문자열 S의 길이를 N, 찾고자하는 패턴 P의 길이가 M이라고 할때, 최악의 경우 O((N-M)*M)의 시간 복잡도를 갖는다. 구현 전체적인 흐름은 아래와 같다. 1. 문자열 S의 첫번째 문자와 패턴 P의 첫번째 문자를 비교하여 같다면 다음 문자를 비교한다. 2-1 다음 문자가 같다면 그 다음 문자를 비교한다. 2-2 다음 문자가 같지 않다면, 패턴 P를 한칸 밀어서 문자열 S의 두번째 문자와 패턴 P의 첫번째 문자를 비교한다. 3. 위와 같은..
[백준 2252번] - 줄세우기(C/C++)
2022. 10. 14. 09:55
Problem Solving/백준
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net [문제 설명] [문제 풀이] 이 문제를 풀기전에 위상정렬 알고리즘에 대해 알고 있으면 쉽게 풀 수 있다. 위상정렬 알고리즘에 대해 잘 모른다면 아래 포스트를 읽고오면 푸는데 도움이 될 것이다. [Algorithm] - Topology Sort(위상정렬) 위상정렬(Topology Sort) 란 ? 위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 ..
[Algorithm] - Topology Sort(위상정렬)
2022. 10. 12. 08:41
Problem Solving/Algorithm
위상정렬(Topology Sort) 란 ? 위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 그래프를 방향을 거스르지 않도록 나열하는 것이다. 아래 그림을 참고하자. 위상정렬을 가장 잘 설명해줄수 있는 예로 대학교의 선수과목 구조를 예로 들 수 있다. 만약, 특정 과목을 듣기위해 필요한 선수 과목이 있다면, 그 선수과목부터 수강해야 한다. 이때 위상정렬을 사용하면 올바른 강의 순서를 찾아 낼 수 있다. 그래프의 구조에 따라 여러개의 정렬이 나타날 수도 있다. 위상정렬을 사용하기 위해선 시작노드를 특정하기 위해 DAG(Directed Acyclic Graph)여야만 한다. DAG는 사이클이 존재하지 않고, 하나의 방향만을 가지는 그..
[프로그래머스] - 네트워크(C/C++)
2022. 10. 7. 00:00
Problem Solving/프로그래머스
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 soluti..
[백준 11779번] - 최소비용 구하기 2(C/C++)
2022. 10. 5. 00:49
Problem Solving/백준
11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net [문제 설명] [문제 풀이] 다익스트라 알고리즘 관련 문제이다. 만약, 다익스트라 알고리즘에 대해 잘 모른다면, 아래 포스트를 먼저 보고오는것이 좋다. [Algorithm] - Dijkstra(다익스트라) 알고리즘 이론 Dijkstra(다익스트라) 알고리즘이란, 그래프의 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘(최단경로 문제)이다. 처음 작성된 알고리즘은 시간복잡도 O(N^2)을 가지는데, mocha-bro.t..
[Algorithm] - Dijkstra(다익스트라) 알고리즘
2022. 10. 2. 04:52
Problem Solving/Algorithm
이론 Dijkstra(다익스트라) 알고리즘이란, 그래프의 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘(최단경로 문제)이다. 처음 작성된 알고리즘은 시간복잡도 O(N^2)을 가지는데, 이후 우선순위큐(=힙트리)를 이용한 개선 알고리즘이 나오면서 O(NlogN)으로 개선되었다. 다익스트라의 특징은 음의 가중치가 없다는 점이다. 따라서 현실세계에 적용할 수 있는 효율적인 알고리즘이라고 할 수 있다. 그래프의 방향은 상관없으나, 가중치가 하나라도 음수라면 다익스트라 알고리즘을 사용할 수 없다. 이때는 조건에따라 벨만-포드 알고리즘을 사용하여 최단거리를 구할 수 있다. 또한, 다익스트라 알고리즘은 하나의 노드로부터 최단 경로를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍..
[프로그래머스] - 배달(C/C++)
2022. 10. 2. 02:47
Problem Solving/프로그래머스
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다..
[Algorithm] - Kruskal's Algorithm(최소 스패닝 트리)
2022. 9. 13. 23:46
Problem Solving/Algorithm
이론 크러스컬 알고리즘은 Union-Find 알고리즘을 사용하기때문에 만약 Union-Find에 대해 잘 모른다면 [Algorithm] - Union-Find(Disjoint-set) 이론 여러개의 집합이 존재 할때, 두개의 집합을 선택해서 같은 그래프에 속하는지 판단하는 알고리즘이다. 간단하게 이야기 하자면, 교집합이 있다면 한개의 집합으로 보게 하겠다는 의미이다 mocha-bro.tistory.com 위 포스트를 한번 읽고 오면 이해하는데 수월 할 수 있다. 크러스컬 알고리즘? 크루스칼 알고리즘?을 정리해보려고 한다. 위 알고리즘의 이론은 최소 비용으로 신장 부분 트리(Spanning SubTree)를 찾는 알고리즘이다. 아래 나무위키에 크러스컬 알고리즘의 단계 별 예제가 있어서 가져왔다. 간단하고 ..
[Algorithm] - Union-Find(Disjoint-set)
2022. 9. 13. 23:24
Problem Solving/Algorithm
이론 여러개의 집합이 존재 할때, 두개의 집합을 선택해서 같은 그래프에 속하는지 판단하는 알고리즘이다. 간단하게 이야기 하자면, 교집합이 있다면 한개의 집합으로 보게 하겠다는 의미이다. 예를들어, A,B 집합이 다음과 같이 있다고 했을때 A = {1,2} , B = {2,3} 2라는 교집합이 있으므로 {1,2,3} 한개의 집합으로 보겠다는 것이다. 이때 집합을 병합하는 부분이 Union, 집합에 속해있는지 확인하는부분이 Find로 볼 수 있다. 두개가 함께 사용되어 Union-Find라는 이름이 붙었다. Disjoint-Set이라고도 불린다. 이름만 다르고, 동일한 알고리즘으로 볼 수 있다. 구현 다음과 같이 노드들의 간선이 주어졌다고 예를들어 설명하겠다. {1,2}, {2,3}, {3,4}, {1,5}..
[프로그래머스] - 섬 연결하기(C/C++)
2022. 9. 13. 10:32
Problem Solving/프로그래머스
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입..