어흥

문제 링크: 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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 바꿀 열을 정한다. 단, 바뀌는 열의 색이 모두 같다는 보장이 없다(최근에 TC가 추가되어 이 부분을 구현 안했다면 50번째에서 틀릴 것이다) 2. 구현 - 바꿀 열의 개수 I개를 정하고, 바꿀 열의 위치를 구한다. - 열의 위치를 정한 후, 해당 열을 어떤 색으로 바꿀지 DFS를 수행하며 Color 벡터에 저장한다. 이후, Change() 함수를 수행한다 - 바꾸는..

문제 링크: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL | 해밀턴 순환회로 > 문제은행 첫 줄은 배달해야 하는 장소의 수 N(1≤N≤12)이 주어진다. 이때, 출발지(회사)는 1번이다. 둘째 줄은 N X N 크기의 장소와 장소를 이동하는 비용(0 ≤ 비용＜ 100)이 한 칸씩의 공백으로 구분하여 주어진다. 비용은 양방향이 아니라 단방향으로 가기 위한 비용이다. 예들 들어 첫 번째 행 두 번째 열에 적힌 비용은 1번 장소에서 2번 장소로 이동하기 위한 비용을 의미하며, 2번 장소에서 1번 장소로 이동하기 위한 비용은 두 번째 행 첫 번째 www.jungol.co.kr 1. 주의할 점 - 완탐으로 하지 않고 백..

문제 링크: 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. 구..