어흥

문제 링크: https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 1. 주의할 점 - 에라토스테네스의 체를 이용하여 소수들을 구한다 - N=1일때 0을 출력한다 - 투 포인터를 이용하여 ..

문제 링크: https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다. 지도 밖으로 나가는 방향의 입력은 주어지지 않는다. www.acmicpc.net 1. 주의할 점 - DP(메모아이제이션) + DFS로 해결한다 2. 구현 - Check[][] 배열을 -1로 초기화 시킨다 - 2중 For문을 돌며 Check[][]값이 -1이면 DFS()를 수행하며, 끝나면 Cnt++를 해준다 - DFS(y,x)에서는 Check[y][x]값이 -1이 아니면..

문제 링크: https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다. 그래프의 정점은 1부터 www.acmicpc.net 1. 주의할 점 - 단절점/단절선의 원리를 알고 있어야 한다 - 단절점과 다르게 Root Node의 Child수를 몰라도 되..

문제 링크: https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 1. 주의할 점 - 단절점에 대한 이론을 알고 있어야 한다 - 단절점이란 해당 점을 끊었을때 컴포넌트의 수가 증가하며, Root가 아닌 경우 단절점을 지나지 않고는 그보다 앞선 번호에 도달 할 수 없거나, Root인 경우 연결된 간선의 수가 2개 이상이면 무조건 단절점이다 2. 구현 - V[]벡터에 간선의 정보를 모두 저장한다 - DFS()를 통해 단절점을..

문제 링크: https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 �� www.acmicpc.net 1. 주의할 점 - 양의 사이클이 아닌, 가중치를 전부 -1로 곱하여 음의 사이클을 구하도록 한다 - 경로를 어떤 방식으로 저장할 것인가 - 사이클이 있다고 무조건 -1을 출력하는 것이 아니다 -> 도착지점까지 이동중, 음의 사이클이 존재한다면 -1 출력 2. 구현 - 음의 사이클이 존재하므로 벨만포드 알고리즘을 사용한다 - Bellman_ford() 함수..

문제 링크: https://www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net 1. 주의할 점 - 경우의수를 직접 구현해보려다가 실패했다. Set도 생각해 봤지만 그 팀의 가능한 승무패인지 확인만 해줄 뿐 그 이상의 가치는 없다. 즉, DFS로 풀자 2. 구현 - 토너먼트 형식으로 이루어져 있으므로, A팀과 B팀이 붙을 수 있는 경우의 수를 미리 구하여 T1[], T2[]에 넣는다 - 각 라인별을 6등분해서 3개씩 입력받아 한팀에 대한 정보를 Win[], Draw[], Lose[]에 담는다 - 만약 전체 팀의 경기수가 30이 안된다면 잘못된 경우로 간주한다(N*(N-1)번 만큼 경기가 이뤄져야 한다. 양쪽의 입장에서 간주하므로 2로 나누지 않는다) - DF..

문제 링크: https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미 www.acmicpc.net 1. 주의할 점 - DP를 통해 해결한다 - 왼쪽, 위, 왼쪽위 대각선을 살핀다(처음엔 오랜쪽으로 했는데 바꿨다) 2. ..

문제 링크: https://www.acmicpc.net/problem/3108 3108번: 로고 문제 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 �� www.acmicpc.net 1. 주의할 점 - 문제를 DFS+BFS를 이용하여 푸는 방법도 있지만, 제가 푼 방법은 범위를 비교하고 만약 서로 겹치는 점이 있다면 부모를 같게 하는 Disjoint-set 방법으로 해결했다 - 초기 상태 (0,0)에서 고개를 내리고 있으므로, (0,0)에 대한 정보를 포함시키고 시작해야한다. 1.5 범위 비교 - 범위 비교할때 다음과 같은 6가지의 경우만 겹치지 않는다고 판단했다 2. 구..