백준52 [17135번] 캐슬 디펜스 17135번: 캐슬 디펜스 www.acmicpc.net 삼성 SW역량테스트 A형 기출문제다. 시험 당시는 풀지 못했다. 탐색보단 구현 능력을 중요시 하는 문제같다. 입력을 보고 맵을 이용해서 풀이를 진행하는 경우가 많을 것이다. 나도 그렇게 풀었다. 의도한 방법은 적들의 위치를 리스트에 저장후 거리 별로 정렬 후 진행하는 것 같다. 나의 풀이 설계는 맵을 이용해서 시뮬레이션을 하듯 풀었다. 1. 각 궁수 위치를 조합을 통해 지정 2. 각 궁수 위치에서 왼쪽부터 가장 가까운 적을 체크 3. 모든 궁수의 적 체크가 끝났으면 적 카운트를 줄인다. 4. 궁수의 위치(행 인덱스)를 감소 적들을 하단으로 전진 시키는 것이 아니라, 궁수의 인덱스만 감소시키면서 맵은 따로 업데이트를 하지 않고 진행하였다. #inclu.. 2020. 2. 12. [16985번] Maaaaaaaaaze 16985번: Maaaaaaaaaze www.acmicpc.net 5*5판 5개를 쌓고, 각 판을 회전 시키면서 cube[0][0][0] 에서 cube[4][4][4]로 갈수 있는 최소경로를 구하는 문제다. 조합 + 3차원 bfs문제다. 1. 각 판들을 쌓을 순서를 순열로 정한다. 2. 순서를 정했으면 각 판들을 회전시키면서 큐브를 만든다. 3. 큐브가 완성되었으면 bfs 주의할 점은 1. 각 판들을 순서를 바꿔서 쌓을수 있다. 2. 각 판들은 시계, 반시계 방향으로 자유롭게 회전가능 하지만 뒤집기는 안된다. #include #include #include #include #include #include #define min(a,b) a= 5 || c >= 5 || h >= 5)) return true;.. 2020. 2. 12. [1922번] 네트워크 연결 1922번: 네트워크 연결 www.acmicpc.net Union Find를 이용해 풀 수 있는 쉬운 문제 입력 받은 경로들의 비용을 기준으로 정렬해서 차례대로 Union을 진행한다. Union할 수 있을 때 비용들을 누적해서 최종적으로 출력하면 된다. 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 40 41 42 43 44 45 46 47 48 49 /*1922번 네트워크 */ #include #include #define SIZE 1001 using namespace std; struct info { int s, e, value; }V[100000]; bo.. 2019. 8. 15. [1708번] 볼록 껍질(Convex Hull) 링크 : https://www.acmicpc.net/problem/1708대표적인 기하알고리즘 문제풀이 방법은 보통 3가지가 있다.1. Jarvis March 알고리즘 : O(NH)1) 주어진 정점에서 극단점 중 하나를 찾는다.(극단점 : 볼록 외피의 정점이 되는 점, 보통 x좌표나 y좌표가 제일 크거나 작은점을 선택한다. 이 점들은 반드시 극단점에 포함된다.)2) 다음 극단점 찾기 : 현재까지 찾은 마지막 극단점 다음에 올 극단점을 모든 점을 보면서 탐색3) 찾은 극단점이 처음 찾은 극단점일 떄 까지 반복2. Graham Scan 알고리즘 : O(NlogN)1) 시작점으로 사용할 극단점 선택2) 시작점을 (0,0)기준으로 모든 점을 평행이동.3) 각 점들을 각도 정렬해서 각도가 적은 순서대로 방문4) .. 2019. 8. 13. 이전 1 2 3 4 5 6 7 ··· 13 다음