SuperM

Algorithm 검색 결과

해당 글 225건

[SWEA] 2383번 점심 식사시간

2383번 점심 식사시간 문제 링크 해결방법 문제를 처음 봤을 때는, BFS 로 계단을 나가야되나??? 라는 생각을 했다 하지만 TC를 보니 거리가 짧은 계단을 이용하는 것이 아니었다 또한 계단의 개수는 2개로 정해져있고, 사람의 수는 10명 이하였다 따라서 예전에 풀었던 스타트와 링크 문제처럼 2개의 그룹으로 나누고 계산을 해야했다 킹치만…!! 계단은 한번에 3명만 내려갈 수 있고, 그 이상의 인원이 도착하면 대기해야 된다는 부분을 솔루션 조차 생각해내지 못했다…. (블로그 참고했음) 꼭 2번 3번 다시 풀어봐야할 문제라고 생각한다 !!!! ⭐️ 솔루션 ⭐️ 각각의 사람과 계단1, 계단2의 거리를 구한 뒤, 그 거리를 Person 구조체에 저장한다 원래는 BFS를 통해 거리를 구했지만, 문제에서 맨해튼..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:29

[SWEA] 2382번 미생물 격리

2382번 미생물 격리 문제 링크 해결방법 주어진 조건대로 구현하는 시뮬레이션 문제이다 ⭐️ 솔루션 ⭐️ 군집이 2개 이상 모였을 경우를 처리하는 것이 가장 핵심인 문제이다 2차원 배열 map의 자료형을 vector 로 선언하여 미생물 번호를 가지도록 한다 각 시간동안, 군집 삭제 → 군집 이동 → 군집 확인 의 과정을 반복한다 만약 map[x][y] 의 크기가 1이 아니라면 여러 군집을 하나로 묶는 작업을 실행한다 문제의 조건 N ≤ 100 K : 군집의 수, M : 시간 1-북 2-남 3-서 4-동 시간 복잡도 m 의 시간(1000) 만큼 작업을 수행한다 각 시간마다, 미생물 제거 (1000) + 미생물 이동(1000) + 미생물 확인(4000) 의 과정을 겪는다 따라서, 시간복잡도는 O(M * 6 ..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:29

[SWEA] 2117번 홈 방범 서비스

2117번 홈 방범 서비스 문제 링크 해결방법 모든 경우를 탐색해보는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ SWEA 홈페이지에서 솔루션을 참고했다 ㅠㅠ 마름모를 만들지 않고, 두 점 사이의 거리의 비교를 통해 확인할 수 있다 k ≤ n+2 의 의미는 모든 맵을 포함하는 경우까지 k를 증가시켜야 한다는 뜻이다 문제의 조건 K : 서비스 영역 크기 운영 비용 : k * k + (k-1) * (k-1) M : 하나의 집이 낼 수 있는 비용 이익 : 집의 수 * M - 운영 비용 시간 복잡도 k는 1~n+2 까지 만들 수 있고, 각 k 마다 모든 노드를 탐색한다 (n^2) 해당 노드를 기점으로 마름모를 생성(n^2) 하여 최대 집의 수를 계산한다 따라서, 시간복잡도는 O(n^5) = 3,200,000 를 가진다 ..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:28

[SWEA] 2115번 벌꿀채취

2115번 벌꿀채취 문제 링크 해결방법 DFS + 백트래킹으로 모든 경우를 탐색해보는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 먼저 한 일꾼의 벌꿀 채취 범위를 정한다 가로 상의 m개의 벌통을 선택했다면 다음 일꾼이 벌통을 선택하는 탐색으로 넘어간다 두 일꾼 모두 벌통을 선택했다면, 각 범위에서 최대 벌꿀 채취양을 구한다 두명의 일꾼이 벌통을 선택하는 경우 + 선택된 벌통에서 최대 벌꿀의 양을 구하는 과정 모두 DFS 백트래킹을 사용해야한다 문제 조건 DFS + 백트래킹 N ≤ 10 M : 선택할 수 있는 벌통 C : 한명의 일꾼이 채취할 수 있는 최대 벌꿀의 양 소스코드 문제 해결 시간 : 1h 메모리 : 12640 KB 시간 : 107 ms #include #include #include #include ..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:27

[SWEA] 2105번 디저트 카페

1953번 탈주범 검거 문제 링크 해결방법 DFS + 백트래킹을 이용하여 모든 경우를 탐색하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 시작노드에서 ↙︎ 방향으로 출발을 시킨다 DFS 탐색으로 해당 노드에서 그대로 이동하는 경우 , 반시계 방향으로 회전하여 이동하는 경우 로 나눠 탐색을 이어나간다 기존에는 set 을 통해 중복된 값을 체크했는데 이는 시간초과 를 발생시켰다 문제의 조건을 잘 읽어보니 디저트의 종류는 1~100 으로 정해져있었다 따라서 set 이 아닌 1차원 배열을 통해 중복된 값을 체크하여 문제를 해결할 수 있었다 문제의 조건 N ≤ 20 디저트의 종류 ≤ 100 한 노드에서 출발하여 대각선 이동으로만 사이클을 형성해야한다 한 사이클에는 중복된 값 X 한 사이 시간 복잡도 시작 노드는 N*N ..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:27

[SWEA] 1953번 탈주범 검거

1953번 탈주범 검거 문제 링크 해결방법 BFS 탐색을 통해 방문한 노드의 개수를 파악하는 완전 탐색 문제이다 ⭐️ 솔루션 ⭐️ 터널입력 시, 비트연산자로의 변환이 필요하다 4자리 비트로 동 서 남 북 의 이동여부를 저장해야한다 만약 현재위치에서 오른쪽으로 이동이 가능하려면 현재 터널은 오른쪽으로 이동이 가능한 터널이어야 하며, 오른쪽 터널 또한 왼쪽으로 이동이 가능한 터널이어야한다 문제의 조건 N,M ≤ 50 소요시간 ≤ 20 탈주범은 1시간에 1만큼 이동 가능 시간 복잡도 현재 위치에 대해 BFS 탐색을 수행하므로 O(N∗M) 의 시간복잡도를 가진다 소스코드 문제 해결 시간 : 50m 메모리 : 12656 KB 시간 : 9 ms #include #include #include #include #in..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:26

[SWEA] 1952번 수영장

1952번 수영장 문제 링크 해결방법 모든 경우를 탐색하는 완전탐색 문제이다 (+ 이 문제는 완전탐색 or DP 로 해결이 가능한 문제라고 한다) ⭐️ 솔루션 ⭐️ 아래의 경우로 나누었다 만약 이번 달에 이용 계획이 없다면? 다음 달로 넘어간다 3달 이용권을 결제한다 1월이라면 1년 이용권을 결제한다 이용 계획이 있다면? 1일 이용권을 이번 달의 이용 횟수 만큼 결제한다 1달 이용권을 결제한다 12달의 경우를 모두 탐색했다면 결제 비용의 최소값을 갱신한다 문제 조건 1일 이용권 : 그 달의 이용횟수만큼 결제 1달 이용권 : 1달 동안 사용 3달 이용권 : 10 ~ 12 11 ~ 12 와 같이 연도가 초과하는 경우에도 사용 가능 1년 이용권 : 1월의 경우에만 사용 가능 소스코드 문제 해결 시간 : 30m..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:26

[SWEA] 1949번 등산로 조성

1949번 등산로 조성 문제 링크 해결방법 DFS + 백트래킹을 이용하여 모든 경우를 탐색하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 시작 봉우리가 최대 5개이므로 이 지점부터 모든 경우를 탐색한다 만약 자기보다 높이가 높거나 같은 봉우리를 만났을 경우, 아직 등산로를 한번도 변경한 적이 없다면 해당 지형을 깎는다 등산로의 최대 길이는 21 까지 나올 수 있다 문제의 조건 N ≤ 8, K ≤ 5 High → Low 등산로 연결 가능 Highest 봉우리는 최대 5개 한 지형을 K 깊이 만큼 깎을 수 있음 등산로의 시작은 가장 높은 봉우리 지형을 1보다 작게 만들 수 있음 시간 복잡도 가장 높은 봉우리 (5) 에 대해 탐색을 시작한다 ???? 소스코드 문제 해결 시간 : 45m 메모리 : 12628 KB 시간..

Algorithm/SWEA 문제풀이 2019. 3. 15. 15:25