분류 전체보기

강한 연결 요소 (SCC) - 타잔 알고리즘

[백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 학교 알고리즘 수업 때 코사라주 알고리즘을 활용한 SCC풀이법을 배웠다. 하지만 구글링을 해보니 코사라주 알고리즘보다는 타잔 알고리즘이 구현이 어렵지만 활용도가 더 높다고 해서 공부해 보았다. 타잔 알고리즘 1번 정점에서 dfs를 시작해 2, 3, 4번 정점을 순서대로 방문했다고 하자. 타잔 알고리즘에서는 방문할 때마다 임의의 sta..

[백준 11266] 단절점 C++

11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net Cut vertex, DFS 1. 문제 해결 아이디어 dfs를 통해서 정점들의 방문순서를 기록해주는게 핵심이다. 현재 노드의 자식중에서 자신보다 더 빠른 방문순서를 가진 정점을 방문하지 않은 자식이 하나라도 있다면 현재 노드는 단절점이 된다. 단절점을 구할 때 중요한 점은 root정점이 단절점인 경우는 따로 구해줘야 하는 것이다. root정점이 자식을 둘 이상 가지고, 자식간에 연결되어있지 않다면 root정점도 Cut vertex가 된..

[백준 1208] 부분수열의 합2 C++

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 N이 40개 이므로 모든 부분수열을 다 구하려면 2^40번의 연산이 필요하다. -> 1초안에 풀 수 없다. 주어진 수열을 절반씩 나누어서 계산해 보자 수열의 길이가 40이라고 가정하자. 20번째 수열부터 40번째 수열(이를 right수열이라고 하자)까지의 모든 부분수열의 합을 구해본다. 이때 시간복잡도는 O(2^20)이므로 시간은 충분하다. right 부분 수열의 합을 sum이라고 하면 ..

[백준 1688] 지민이의 테러 C++

1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있 www.acmicpc.net 기하학, 선분 교차, 레이 캐스팅 알고리즘 1. 문제 해결 아이디어 많은 예외 케이스 때문에 10번넘게 틀린 문제... 오래 고민한 만큼 정이 들어버린 문제다.. [백준 17387] 선분 교차 2 C++ 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을....

[백준 16197] 두 동전 C++

16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net DFS, BFS 1. 문제 해결 아이디어 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다. 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다. 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다. 문제에 나와있는 그대로 구현했다. DFS를 통해서 잘못된 길에 들어선 뒤에 백트래킹이 가능하게 구현을 하였다. memset(Map..

Cache Lab trans.c #2

cache lab에서 trans.c를 통해 행렬을 전치시키는 작업에 있어서 cache miss가 얼마나 달라지는지 시뮬레이션해보자! 이전 포스팅 Cache Lab csim.c #1 cache lab에서 csim.c를 통해 cache의 동작 방식을 시뮬레이션해보자! SystemSoftware - Cache Memory #1 cache memory에 대해서 알아보자 Locality Temporal locality(시간 지역성) : 최근에 접근했던 data나 명.. hyeo-noo.tistory.com 연관 포스팅 SystemSoftware - Cache Memory #3 SystemSoftware - Cache Memory #2 SystemSoftware - Cache Memory #1 cache memor..

[백준 20181] 꿈틀꿈틀 호석 애벌레 - 효율성 C++

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 다이나믹 프로그래밍, 투 포인터 코딩꿈나무 조정현 : 네이버 블로그 빠르게 꾸준히 blog.naver.com 정현님의 추천문제를 풀어보았다! 1. 문제 해결 아이디어 [백준 1644] 소수의 연속합 C++ 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 수학, 두 포인터, 정수론 1. 문제풀이 아이디어 에라토스테네스의 체를 이용해서 N까지의 소수를 배열에 순서 hye..

단어 제한 끝말잇기 (WORDCHAIN)

algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 www.algospot.com DFS, 오일러 서킷, 오일러 트레일 1. 문제 해결 아이디어 끝말잇기에 사용되는 단어들이 주어진다. 주어진 단어 모두를 사용해서 끝말잇기를 만들면 된다. -> 오일러 회로임을 알 수 있다. 단어를 모두 사용해서 다시 시작점으로 돌아올 수도 있고, 시작점이 아닌 지점에서 끝날 수도 있다. 다시 시작점으로 돌아오는 경우는 오일러 서킷이라고 할 수 있다. 모든 간선을 한 번씩 통과하지만 시작점이 아닌 다른 정점에서 끝나는 경로를 오일러 트레일 이라..

[백준 1199] 오일러 회로 C++

1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net DFS, 오일러 1. 문제 해결 아이디어 오일러 서킷 오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접 hyeo-noo.tistory.com 이 문제는 오일러 서킷을 구하는 문제이다. 위 링크의 알고리즘에 따라서 구현을 하고, 간선정보를 받은 후 정점에 대한 degree가 홀수인 정점이 존..

오일러 서킷

오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접한다. v를 지나기 위해서 v로 들어가는데 하나, 나가는데 하나가 필요하다. 만약 v가 끝점이라면 v로 들어가는 간선에 대응하는 나가는 간선이 없다는 뜻이므로 v에 인접한 간선의 수가 홀수 일 수밖에 없다. 2. u == v 인 경우 : v는 항상 짝수 개의 간선과 인접한다. u에서 나가는 것으로 시작했기 때문에 u로 다시 들어왔다면 u(=v)에 인접하는 간선의 수는 짝수이다. 한 정점에 인접한 간선의 개수를 degree라고 하자. 오일러 서킷은 모든 정점에 들어가는 횟수와 나가는 횟수가 같아야하므로..