Algorithm

[백준 3977] 축구 전술 C++

3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 강한 연결 요소 1. 문제 해결 아이디어 도미노 문제와 매우 비슷한 문제이다. 이 문장을 통해서 SCC임을 알 수 있다. 강한 연결 요소 (SCC) - 타잔 알고리즘 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으..

[SWEA 1206] View (D3)

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1000*255 = 25만 밖에 안되고, test case도 10개 뿐이므로 문제에서 주어진 아파트를 배열에 모두 구현하는 방법을 사용했다. 현재 아파트의 현재 층에서 좌우로 1, 2개 의 칸이 비어있다면 조망권이 있는 집으로 분류했다. 아파트의 구조를 2차원 배열에 담지않고 [1000]인 1차원 배열에 아파트의 최대 층수만 가지고 있어도 거의 비슷하게 풀릴듯 하다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ..

근거리 네트워크 (LAN)

algospot.com :: LAN 근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일 algospot.com 최소 스패닝 트리 문제 설명 더보기 N개의 정점의 좌표가 주어지고 가중치 없이 연결할 수 있는 정점의 번호가 주어진다. 양방향 간선이지만 u에서 v로 가는 간선 하나만 저장해주면 된다. (u < v) 2중 for문을 통해서 모든 정점끼리 연결될 수 있는 가중치가 포함된 간선을 구해준다. 크루스칼 알고리즘을 적용하기 전에 주어지는 정점들을 Union해버리면 가중치 없이 정점을 미리 연결해줄 수 있다. 그리고 나머지 정점들을 크루스칼 알고리..

선거 공약 (PROMISES)

algospot.com :: PROMISES 선거 공약 문제 정보 문제 경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국 algospot.com 플로이드-와샬 문제 설명 더보기 우선 기존에 있던 고속도로들을 가지고 플로이드 알고리즘을 통해서 최단거리를 구해준다. 그리고 새로운 고속도로(a에서 b로 가는)가 건설 될 때마다 현재 최단거리와 비교해서 비용이 같거나 오히려 더 크다면 해당 고속도로를 설치할 필요가 없다. 하지만 새로운 고속도로를 설치하는게 이득이 된다면 a에서 b로 가는 고속도로를 추가하고 플로이드 알고리즘을 통해서 모든 간선의 최소비용을 갱신해 준다. r에서 c로 가는 비용을 갱신..

[백준 1504] 특정한 최단경로 C++

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 반드시 방문해야 하는 정점이 2개 주어진다. 예를 들어 1번 정점에서 4번 정점으로 가야하는데 2, 3번 정점을 반드시 거쳐야 한다고 하자 첫 번째로 1 -> 2 -> 3 -> 4 순으로 정점을 방문할 수 있다. 위 순서는 각 정점이 방문된 시점을 순서대로 나열한 것에 불과하다. 1에서 2, 2에서 3, 3에서 4로 가는 최단 거리를 구하기 위해서 중간에 다양한 정점을 방문할 수 있..

[백준 2213] 트리의 독립집합 C++

2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 트리 DP 1. 문제 해결 아이디어 [백준 1949] 우수 마을 C++ 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, hyeo-noo.tistory.com 위 문제와 표현하는 말만 다르지 결국 똑같이 서로 인접하지 않는 정점들의 가중치의 최댓값을 찾는 문제이다. 하지만..

[백준 2458] 키 순서 C++

2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 자신보다 키가 큰 게 확실한 사람, 키가 작은 게 확실한 사람들의 수를 구하면 된다. 주어진 방향그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 큰 학생임을 알 수 있다. 자신보다 키가 작은 학생들도 알아야 하므로 입력이 주어질 때 역방향 그래프도 같이 저장한다. 역방향 그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 작은 학생임을 알 수 있다. 따라서 임의의 정점에서 다른 모든 정점으로 갈 수 ..

음주 운전 단속 (DRUNKEN)

algospot.com :: DRUNKEN Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day, www.algospot.com 플로이드-와샬 문제 설명 더보기 플로이드 알고리즘은 아무 정점도 경우하지 않는 최단 거리에서 시작해 경유할 수 있는 정점을 하나씩 추가해 가며 최단 거리를 갱신한다. 이 과정에서 경유하는 정점을 1번부..

[백준 15684] 사다리 조작 C++

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 완전 탐색, 백트래킹 삼성 SW 기출 1. 문제 해결 아이디어 처음에 문제에 대한 감이 안 왔다. 백트래킹이라기엔 H가 너무 커 보였고 그래프라 하기엔 간선 정보를 어떻게 담아야 할지 생각이 안 났다. 그러다 완전 탐색 문제라는 말을 듣고 힘들게 접근을 시도할 수 있었다. 지금까지 만든 사다리에서 사다리 타기를 했을 때 각 line의 도착점이 시작 line의 번호와 같아야 true를 return 하는 함수를 만들었다. 그리고 사다리를 놓지 못하는 조건을 걸어주고..

[백준 17144] 미세먼지 안녕! C++

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 [백준 17143] 낚시왕 C++ 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래 hyeo-noo.tistory.com 낚시왕 문제와 느낌이 비슷했다. 시뮬레이션 문제는 문제에 어떻게 구현해야 하는지 자세히 나와있어서 풀이라고 할 게 없다. ..