https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net row_check에 [행번호][숫자] = (해당 행에 해당 숫자가 있으면 : 1, 없으면 0), col_check에 [열번호][숫자] = (해당 열에 해당 숫자가 있으면 : 1, 없으면 0), area_check에 [구역번호][숫자] = (해당 구역에 해당 숫자가 있으면 : 1, 없으면 0)를 저장하여 해당 위치에 특정 숫자가 들어갈 수 있는지 판단하는 방법으로 문제를 해결했다. 코드 #inclu..

https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net LCA(최소 공통 조상)을 구하는 방법으로 최소 공통 조상을 구하고, 트리의 루트로부터 거리 차이를 이용하여 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n; int m; vector adj[40001]; //(거리, 정점) vector maked(40001, 0); vector cost(40001);..

https://www.acmicpc.net/problem/15559 15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net 유니온 파인드를 이용해 이동할 수 있는 칸들을 같은 구역으로 합친 뒤, 총 구역이 몇 개인지를 구해 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n, m; vector board; int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{..

https://www.acmicpc.net/problem/1108 1108번: 검색 엔진 새로운 검색 엔진을 만들었다. 이 검색 엔진은 구글을 뛰어넘는 세계 최고의 검색 엔진이기 때문에, 신뢰도가 높은 결과를 보여줘야 한다. 하지만, 사용자가 검색어를 입력했을 때, 이것에 맞는 www.acmicpc.net 타잔 알고리즘을 이용해 SCC를 구하고, SCC끼리의 그래프를 만드는데 SCC 간의 길이 여러 개 있어도 연결은 하나만 만든다. 그리고 SCC 그래프의 위상 정렬을 하며 here_scc와 there_scc에 속한 노드들 중 서로 직접적으로 연결된 길이 있을 때 점수를 부여하는 방식으로 문제를 해결했다. 코드 #include #include #include #include #include #include..

https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net 세그먼트 트리를 이용해 문제를 해결했다. 주어진 구간 중 크기가 가장 작은 값의 인덱스를 구하는 방법은 구간의 작은 값을 구하는 Query_sgmtt를 통해 Query_sgmtt의 결과가 더 작은쪽을 확인하는 방법(같은 값이라면 앞쪽을 확인한다)으로 문제를 해결했다. 코드 #include #include #includ..

https://www.acmicpc.net/problem/2152 2152번: 여행 계획 세우기 첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1≤A, B≤N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공로 www.acmicpc.net 타잔 알고리즘을 이용해 강한 연결 요소(SCC)를 구하고 SCC들의 그래프를 만든 뒤, 알고리즘 분류에 위상 정렬이 있는 것을 이용해 위상 정렬을 통해 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n, m, s, t; vector adj[10001];..