Algorithm/SWEA 문제풀이 검색 결과

해당 글 24건

[SWEA] 4408번 자기 방으로 돌아가기

4408번 자기 방으로 돌아가기 문제 링크 해결방법 BFS 탐색을 통해 이동 경로를 구하는 문제이다 ⭐️ 솔루션 ⭐️ 먼저, 3 x 200 배열을 선언해 방과 복도를 배정한다 출발노드에서 BFS 탐색을 시작한다 복도인 경우만 탐색을 진행하며, 도착방에 도착한 경우는 예외로 처리한다 현재방과 도착방의 차이를 구해 왼쪽 or 오른쪽 진행을 결정한다 도착방을 지나치지 않도록 처리한다 이렇게 탐색을 진행하며, 이동 경로를 dist 배열에 기록한다 모든 학생들이 이동을 마쳤다면, 이 때 중첩된 경로 중 가장 큰 값이 걸린 시간이다 시간 복잡도 각 n개의 경우별로 BFS 탐색을 수행한다 이 때, 복도 + 출발방 + 도착방 을 대상으로만 탐색을 진행하기 때문에 202 만큼의 시간이 걸린다 따라서 O(n * 202) ..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:34

[SWEA] 4261번 빠른 휴대전화 키패드

4261번 빠른 휴대전화 키패드 문제 링크 해결방법 처음에는 모든 경우를 다해보는 문제인줄 알았으나, 그냥 단순히 일치여부를 확인하는 문제였다 ⭐️ 솔루션 ⭐️ 입력받은 단어를 반복문으로 돌며, 문제의 조건과 일치하는지 확인해야한다 S의 길이와 단어의 길이가 다르다면 이 경우는 제외한다 이제 단어의 알파벳 하나씩 확인을 하여 일치여부를 파악한다 시간 복잡도 모든 단어를 반복문으로 돌며 탐색한다 (1000) 각 단어의 모든 요소와 키패드의 일치 여부를 탐색한다 (4 * 1000) 따라서 O(4 * 1000 * 1000) 의 시간복잡도를 가진다 소스코드 문제 해결 시간 : 1h 메모리 : 14744 KB 시간 : 72 ms #include #include #include #include #include #i..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:33

[SWEA] 5656번 벽돌 깨기

5656번 벽돌 깨기 문제 링크 해결방법 모든 경우에 대해 탐색하여 구현 하는 완전탐색 + 시뮬레이션 문제이다 ⭐️ 솔루션 ⭐️ 구슬은 총 4개를 발사할 수 있고, 가로의 최대 길이는 12 이므로 탐색에는 O(12^4) 의 시간이 걸린다 완전탐색은 DFS 로 구현하였고, 구슬이 파괴되는 과정은 BFS 를 통해 구현하였다 중력에 의해 벽돌을 내리는 로직을 설계하였는데, 테케 50개 중 49개만 맞아서 다른 코드를 참고해 로직을 변경하였다 소스코드 문제 해결 시간 : 2h 메모리 : 12652 KB 시간 : 1681 ms #include #include #include #include #define INF 987654321 using namespace std; struct node { int x,y,rang..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:32

[SWEA] 5644번 무선 충전

5644번 무선 충전 문제 링크 해결방법 시간대별로 사람을 이동시켜 최대값을 얻는 시뮬레이션 문제이다 처음에는 완전탐색으로 문제를 풀었다가 시간초과 가 나왔다 그래서 솔루션을 찾아보다, 이 문제는 단순 시뮬레이션으로 해당 시간의 최대값을 구해야 한다는 힌트를 얻고 다시 40분 동안 코드를 수정해 풀 수 있었다 ⭐️ 솔루션 ⭐️ 처음에는 완전탐색을 통해 이용할 수 있는 충전소를 모두 해보는 방법을 적용했다 하지만 시간초과 가 발생했고 다른 솔루션을 적용시켰다 각 시간마다 사용자의 좌표는 정해져있기에 아래와 같은 솔루션을 적용시킬 수 있다 사용자 A, 사용자 B 가 사용할 수 있는 충전소를 맨해튼 거리로 구한다 이를 각각 A,B 벡터에 넣고 가능한 경우의 수를 구한다 이 때, 사용자 A만 이용하는 경우 사용..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:31

[SWEA] 4014번 활주로 건설

4014번 활주로 건설 문제 링크 해결방법 주어진 조건을 구현하는 시뮬레이션 문제이다 삼성 기출문제인 경사로 문제와 동일하다 다시 푸는 문제지만 너~무 어렵다 정말…ㅠㅠㅠ 나중에 다시 풀어봐야지….퓨ㅠ ⭐️ 솔루션 ⭐️ 경사로를 설치할 수 있는지 검사하는 여부가 까다롭다 높이 차가 1인가 이미 경사로가 설치되어 있는가 경사로가 맵 밖을 벗어나는가 경사로 설치 지형의 높이가 동일한가 또한 두 지형을 비교해 높이가 더 작은 쪽에 경사로를 설치해야한다 문제 조건 경사로는 겹치면 안됨 경사로가 맵 밖을 벗어나면 안됨 x : 경사로의 길이 (높이 : 1) 소스코드 문제 해결 시간 : 1h 30m 메모리 : 12488 KB 시간 : 7 ms #include #include #include using namespac..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:31

[SWEA] 4013번 특이한 자석

4013번 특이한 자석 문제 링크 해결방법 주어진 조건을 구현하는 시뮬레이션 문제이다 삼성 기출문제인 톱니바퀴 문제와 동일하다 ⭐️ 솔루션 ⭐️ 저번에 풀었던 문제인데도 좌•우 회전이 헷갈렸다 leftValue 와 rightValue 값을 갱신해가며 회전 여부를 파악하면 됐다 또한 점수를 매기는 방식이 헷갈렸는데 구글링을 통해 간단한 방법을 찾았다 문제 조건 8개의 전극을 가지고 있는 자석이 총 4개 서로 다른 극이 접해야 회전을 함 소스코드 문제 해결 시간 : 1h 메모리 : 12488 KB 시간 : 6 ms #include #include using namespace std; int testcase; int k,ind,dir,ans,sum; int magnet[5][9]; void rotateMagn..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:31

[SWEA] 4012번 요리사

4012번 요리사 문제 링크 해결방법 DFS + 백트래킹을 통해 모든 경우를 탐색하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ 백준의 스타트와 링크 문제와 거의 동일하다 1차 구현에서는 2개의 음식에 재료를 배분하고, 배분이 균등하지 않다면 return 하는 식으로 구현했다 하지만, 이는 시간적인 측면에서 비효율적이었다 따라서 2차 구현 시, 균등하게 배분하도록 구현하였다! 소스코드 [1차 소스코드] 문제 해결 시간 : 30m 메모리 : 12632 KB 시간 : 2403 ms #include #include #include #define MAX 16 #define INF 987654321 using namespace std; int testcase; int n,ans; int map[MAX][MAX]; int..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:30

[SWEA] 4008번 숫자 만들기

4008번 숫자 만들기 문제 링크 해결방법 DFS + 백트래킹을 통해 모든 경우를 탐색하는 완전탐색 문제이다 ⭐️ 솔루션 ⭐️ + - * / 의 경우를 모두 대입시켜 모든 연산자의 경우를 처리한다 문제 조건 N ≤ 12 연산자 개수 = 숫자 개수 - 1 연산의 값은 -100,000,000 ~ 100,000,000 시간 복잡도 연산자의 종류는 4개이고, 개수는 최대 11개이다 따라서 연산자를 설정하는 것은 4^11 의 시간이 걸린다 또한 수식을 계산하는 과정은 최대 11 의 시간이 걸린다 따라서 O(4^11 * 11) 의 시간 복잡도를 가진다 소스코드 문제 해결 시간 : 30m 메모리 : 12632 KB 시간 : 89 ms #include #include #include #include #include #..
Algorithm/SWEA 문제풀이 2019. 3. 15. 15:30