Algorithm 검색 결과

해당 글 225건

[SWEA] 1824번 혁진이의 프로그램 검증

1824번 혁진이의 프로그램 검증 문제 링크 해결방법 BFS 를 통해 해당 경로를 갈 수 있는지 확인하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 처음에는 그냥 명령어에 따라 이동만 했는데 프로그램이 종료가 되지않는 큰 문제점이 생겼다 이를 해결하기 위해서 visited 배열이 필요했다 단순히 x,y 좌표로만 방문처리를 하면 안됨! x좌표, y좌표, 메모리, 방향 을 이용한 4차원 배열로 방문처리를 해줘야한다 또한 ? 명령어의 처리가 필요하다 문제에서는 무작위로 방향을 선택하라고하지만, 사실 4개의 확률은 동일하기 때문에 4방향 모두 돌려버리면 된다 소스코드 문제 해결 시간 : 2h 메모리 : 12796 KB 시간 : 45 ms #include #include #include #include using nam..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:38

[SWEA] 1486번 장훈이의 높은 선반

1486번 장훈이의 높은 선반 문제 링크 해결방법 아주 간단한 DFS 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 직원을 탑으로 사용하는 경우 직원을 탑으로 사용하지 않는 경우 위와 같은 2가지 경우로 나눠 탐색을 진행한다 만약 전 직원을 탐색했을 때, 탑의 높이가 선반보다 같거나 높다면, 이 중 최소값을 갱신한다 시간복잡도는 전체 직원의 수 20명을 선택하는 경우, 선택하지 않는 경우로 나뉘기 때문에 O(2^20) 을 가지게 된다 소스코드 문제 해결 시간 : 2h 10m 메모리 : 12636KB 시간 : 9ms #include #include #include #include #include #define MAX 21 #define INF 987654321 using namespace std; int testca..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:37

[SWEA] 1249번 보급로

1249번 보급로 문제 링크 해결방법 다익스트라를 이용해 탐색하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 이 문제를 다익스타라 문제라고 생각한 근거는 아래와 같다 최소 비용으로 노드간의 이동을 해야한다 노드간의 이동 비용이 다르다 따라서 오랜만에 다익스트라를 활용하여 문제를 해결하였다 문제 조건 N ≤ 100 (0,0) → (n-1,n-1) 최소비용의 경로를 구해야함 소스코드 문제 해결 시간 : 30m 메모리 : 12716 KB 시간 : 55 ms #include #include #include #include #include #define INF 987654321 using namespace std; struct node { int x,y,t; node(){ } node(int _x,int _y,int _..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:37

[SWEA] 4301번 콩 많이 심기

4301번 콩 많이 심기 문제 링크 해결방법 조건에 맞게 구현하는 문제이다 ⭐️ 솔루션 ⭐️ 문제의 유형은 완전탐색처럼 보인다. 하지만 N≤10,000 이라는 조건으로 완전탐색은 불가능하다. 따라서 새로운 접근이 필요했다. 손으로 콩을 직접 심어보니, 5x3의 경우 아래와 같은 모형이 나왔다 012345 0xxxx 1xxx 2xx 3xxx 그래서 전체 맵을 탐색했다 만약, 4방향에서 거리가 2인 노드에 콩이 모두 심어져있지 않다면, 콩을 심을 수 있는 곳이었다 따라서, O(N*M*4) 의 시간복잡도를 통해 문제를 해결할 수 있었다. 소스코드 문제 해결 시간 : 30m 메모리 : 16536 KB 시간 : 67 ms #include #include #define MAX 1001 using namespace ..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:36

[SWEA] 4112번 이상한 피라미드 탐험

4112번 이상한 피라미드 탐험 문제 링크 해결방법 BFS 탐색을 통해 최단거리를 구하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 그래프의 구조가 복잡하지만, 1차원 배열을 통해 O(10,000) 시간동안 완전탐색을 수행할 수 있다 BFS 를 수행하기 위해 노드의 간선을 연결해야한다 직접 관계를 그려보면, 아래와 같은 간선의 결과를 얻을 수 있다 1 - 2, 3 ------------------------------ 2 - [1], 3, 4, 5 3 - [1], [2], 5, 6 ------------------------------ 4 - [2], 5, 7, 8 5 - [2], [3], [4], 6, 8, 9 6 - [3], [5], 9, 10 ------------------------------ 7 - ..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:36

[SWEA] 1767번 프로세서 연결하기

1767번 프로세서 연결하기 문제 링크 해결방법 DFS + 백트래킹을 통해 모든 경우를 처리하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 문제를 처음 보고 완전탐색을 생각했지만 설계가 너무 복잡했다 먼저 가장자리 코어를 제외한 나머지 코어들을 벡터에 넣어준다 4방향을 탐색하여, 전선을 설치할 수 있다면 전선을 설치했다 백트래킹을 활용하여, 전선 설치 - 재귀 - 전선 해체 의 과정을 구현했다 문제 조건 가장자리에 전원이 공급됨 최대한 많은 전원을 연결하고, 최소 전원 길이의 합을 구해야함 모든 코어가 반드시 전원에 연결될 필요는 없음 N≤12 , Core ≤ 12 시간복잡도 최대 코어의 개수는 12개이다. 또한 각 코어는 4방향 또는 연결되지 않을 수 있다. 따라서 O(5^12) = 244,140,625 이지..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:35

[SWEA] 3752번 가능한 시험 점수

3752번 가능한 시험 점수 문제 링크 해결방법 반복문을 통해 가능한 경우의 수를 구하는 문제이다 N ≤ 100 이기 때문에, 완전탐색을 수행한다면, O(2^100) 의 시간이 걸리므로 불가능하다 조건을 분석한 뒤, 2중 반복문을 통해 해결할 수 있는 솔루션을 발견했다 ⭐️ 솔루션 ⭐️ 최대 배점은 100점 이고 최대 문제 수는 100개 이기 때문에 최고 점수는 10,000점 이다 0점의 경우부터 탐색을 시작한다 초기에, 0점의 플래그를 true 로 설정한 뒤, 벡터에 넣는다 각 배점을 반복문으로 돌며 아래와 같은 탐색을 수행한다 벡터의 값을 꺼내, 현재 배점을 더한다 만약 더한 값이 플래그 처리가 되지 않았다면, 플래그 처리 후 벡터에 넣는다 반복문을 모두 돌았다면, 벡터의 크기를 반환한다 소스코드 문..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:35

[SWEA] 2891번 분수 스도쿠

2891번 분수 스도쿠 문제 링크 해결방법 스도쿠의 빈 칸에 1~9 까지의 수를 대입해가며 모든 경우를 탐색하는 완전 탐색 문제이다 ⭐️ 솔루션 ⭐️ 스도쿠 한칸을 pair 로 선언하여 입력받는다 빈칸인 경우 0으로, 아닌 경우 입력값으로 분수를 채운다 이 때, 분수인 경우와 정수인 경우를 나눠야한다 만약 분수라면 분모와 분자를, 정수라면 분모만 입력받고 분자는 10으로 채워준다 이제 탐색을 수행한다 빈 칸에 대해 1~9 까지의 수를 모두 대입해본다 이 때, 가로•세로•스도쿠•분수 조건 을 체크한 뒤, 모두 만족한 경우 숫자를 대입해준다 이러한 방식으로 백트래킹을 통해 모든 경우를 탐색한다 문제 조건 6x6 보드가 주어지며, 3x2 스도쿠가 총 6개 존재한다 분수의 크기는 1보다 작아야하기 때문에, 분자..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:34