본문 바로가기

전체 글

 (336)
백준 12893번 - 적의 적(C++) https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 문제를 처음 접했을 때 그래프 문제라는 것은 바로 파악할 수 있었다. 그러나 이 문제는 이분 그래프의 정석이라고 난이도 기여에서 말하던데 이분 그래프를 자세히 공부해본적이 없어서 조금 어려웠던 듯 하다. 우선 먼저 적대관계 그래프를 그려서 문제의 의미를 파악해보자. 1 2 2 3 3 4 4 5 입력이 들어온다면 위와 같은 적대 그래프가 만들어질 것이..
백준 1786번 - 찾기(C++) https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 알고리즘의 기본 문제이다. 문제에서도 친절하게 KMP알고리즘에 대해 설명하고 있다. https://tigerfrom2.tistory.com/400 문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 tige..
문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 아이디어는 접미사와 접두사이다. 접미사와 접두사는 단어를 반으로 잘라 왼쪽이 접두사 오른쪽이 접미사가 된다. ABCDAB 가 있으면 ABC는 접두사 DEF는 접미사가 된다. 자, 이걸 어떻게 쓸 수 있을까. 위 단어는 접두사와 접미사가 일치하는 것이 없다. 그러니 다른 예제를 보자. ABA 라고 생각하자. 접두사와 접미사에 모두 A가 있다. 그리고 ABAABA 라는 인풋에서 ABA를 찾는다고 생각해보자. ABAABA ABA 1개를 찾았다. 원래같으면 ABAABA ABA ABA 이런식으로 슬라이딩 윈도우처럼 ..
최소 스패닝 트리 (MST) - 프림 알고리즘 최단거리 알고리즘에는 우리가 익히 잘 아는 다익스트라 알고리즘, BFS가 대표적이다. 그러나 이 두개의 알고리즘은 모든 정점을 지나지 않고 무조건 최단거리를 찾는다. 그래서 모든 정점을 방문해야하는 문제를 해결할 수 없다. 때문에 MST 최소 스패닝 트리가 필요하다. 그래프에서 모든 정점을 지나는 트리를 그린다는 의미이다. 1. 프림 알고리즘 프림 알고리즘은 "정점" 을 아무거나 한 개 선택한다. 그리고 정점의 인접 정점들 중 가장 거리가 가까운 정점으로 이동한다. 그리고 지금까지 지나온 정점들 중 가장 가까운 곳으로 간다. 그림을 통해 이해하자. 자세히 설명해보면, 스탭1: 아무 정점이나 넣는다. 보통 1을 넣는다. 그리고 1에서 가장 가까운 곳으로 이동하면서 dist 배열을 업데이트한다. 스탭2: 현..
SWEA - 10806번 수 만들기 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC4piqD_IDFASe SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com A수 -> B수 이동 최소거리는 유서깊을 정도로 흔한 레파토리이다. 그래서 처음 생각한 풀이는 다익스트라였다. 왜냐하면 K = 1억이고 방문체크만해준다면 O(N)으로 풀이할 수 있기 때문이다. 그러나 이 방법을 사용하려면 최악의 경우 1억개 모두 dist 배열에 + 한 갯수를 저장해야하는데 이러면 int 배열을 사용하면 4억 바이트 = 4000KB = 약 400MB를 사용해야해서 불가능하다. 그래서..
백준 16928번 - 뱀과 사다리 게임(C++) https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 다익스트라, 그래프 등 많은 것을 고민했지만 그냥 bfs 풀이가 가장 쉬운 풀이이다. #include #include #include using namespace std; map jump; bool visited[101] = { false, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL..
백준 1967번 - 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 가장 먼저 생각난 풀이는 플로이드-워셜 알고리즘이었다. 그러나 플로이드 워셜의 시간복잡도는 O(N^3)이기 때문에 불가능했다. 그래서 트리에서의 DP를 생각해보았지만 딱히 해결법이 생각나지 않았다. 가장 쉬운 방법은 모든 지점에서 dfs를 수행하는 것이다. 노드의 개수가 1만이기 때문에 O( (V + E )^2 ) = 2만 제곱 = 4천만으로, 해결이 가능하지만 이게 정해라면 ..
백준 9466번 - 텀 프로젝트 (C++) https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 위 문제를 보고 그래프 문제라는 것을 깨닫는 것이 첫번째 단계다. 여기서 1~7을 노드라고 생각하자. 그리고 아래 숫자들은 노드가 가리키는 또다른 노드라고 생각하면, 위 표는 아래같은 그래프로 나타낼 수 있다. 이제 이 문제가 파악이 될 것이다. 이 문제는 그래프로 나타낸 뒤 사이클을 파악하는 것이 핵심이다. 이제 이것을 어떻게 파악해야할까. 가장 쉬운 것은 모든 노드에서 dfs를 돌리면서 자기 자신으..

티스토리툴바