[백준 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"라는 문자열이 있다고 가정하자. 우리는 각 문자의 길이에 따라 접두사와 접미사가 일치하는 최대 길이를 테이블에 저장할 것이다. 실패함수 테이블을..
[백준 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)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 ..
[백준 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..
[프로그래머스] - 배달(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이하입..
[백준 12865번] - 평범한 배낭(C/C++)
2022. 9. 3. 23:38
Problem Solving/백준
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net [문제 설명] [문제 풀이] 다이나믹 프로그래밍 문제 중 유명한 유형인 Knapsack Problem(배낭 문제)이다. 물건들은 각각 무게(W)와 가치(V)를 가지고 있다. 배낭에 넣을수 있는 무게의 한계(K)가 정해져있고, 무게 한도 안에서 넣을수있는 물건들(N)의 가치합의 최댓값을 구하면 된다. 물건들을 처음부터 차례로 확인한다. 2차원 배열 dp를 선언하여 dp[물건 인덱스][무게]의 가치의 ..
[백준 11000번] - 강의실 배정(C/C++)
2022. 9. 3. 23:35
Problem Solving/백준
[문제 설명] [문제 풀이] 풀다보니.. 답을 맞추긴 했지만.. 코드가 좀.. 그렇다.. 다른 사람들을 봤을때 우선순위 큐를 사용해서 문제를 푼거같은데.. 나중에 한번 다시 풀어봐야겠다. 내가 문제를 푼 방식은 아래와 같다. 1. sort함수를 사용해서 시작 시간이 빠른 순서로, 시작 시간이 같다면 강의 시간이 짧은 순서로 정렬했다. 2. isvisited 배열을 선언하여 방문 여부를 체크한다. 3. 방문하지 않은 인덱스일 경우 count를 증가시킨다. 4. 현재 강의가 끝나는 시간보다 큰 시작 시간을 갖는 인덱스를 lower_bound를 통해 구한다. 5. 찾은 인덱스가 방문하지 않은 곳이라면 방문 상태로 변경하고, 방문한 곳이라면 인덱스를 하나 증가시켜서 다시 확인한다. 6. lower_bound로 ..
[프로그래머스] - 큰 수 만들기(C/C++)
2022. 9. 3. 23:27
Problem Solving/프로그래머스
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. ..
[백준 5427번] - 불(C++)
2022. 8. 16. 13:06
Problem Solving/백준
5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net [문제 설명] 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 ..