알고리즘 (32) 썸네일형 리스트형 [백준] 13460번 구슬 탈출 2 [풀이] 고려해야될 케이스가 많아서 생각보다 애를 먹었던 문제입니다.. ㅠ 우선 제가 풀이한 방식은 다음과 같습니다. 1. 각 지점별로 사방으로 이동을 합니다. 2. 빨강, 파랑 둘다 '#'를 만나거나 서로 겹치게 되면 멈추고 그 자리를 기억합니다. 만약 그 중 'O'가 있다면 가능한지 불가능한지 구분해줍니다. 가능하다면 바로 그 횟수를 출력하면 되고, 불가능하다면 그 위치에서는 더이상 이동 하지 않습니다. 여기에서 주의해야 할 부분은 visited를 빨강과 파랑 둘다 기록해줘야 한다는 것입니다. 처음에는 어짜피 빨간색만 구멍에 들어가면 되니까 빨간공만 기록해주면 되지 않을까 하였지만, 빨간색은 같은 위치인데 파란색의 위치가 달라 결과가 달라지는 경우가 생기더군요.. ! 어떻게 보면 BFS로 간단히 풀 .. [백준] 2583번 영역 구하기 [풀이] 쉬운 문제인데 처음에 좀 헷갈렸습니다.. 저 색칠된 부분이 좌표라고 생각했는데 그게 아니어서 당황했던거죠..ㅠ 그렇지만 주어진 좌표를 토대로 제 입맛에 맞게 (위 그림처럼) 새로운 2D array를 만들고 해결하면 간단하게 풀리는 문제였습니다! 새로운 배열로 비어있는 부분을 BFS 탐색하였습니다. 아래는 풀이한 코드입니다. 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 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #include u.. [백준] 14502번 연구소 [풀이] 처음에는 벽을 어떻게 세울까 엄청 고민을 했는데, 조건을 보니 N, M이 최대 8밖에 안되더군요! 전부 0이라고 하더라도 총 가짓수가 64*63*62 = 249984개밖에 안되서 완전탐색을 진행했습니다. 풀이 순서는 1. 일단 재귀를 활용해서 벽 3개를 세팅 2. bfs로 2 채우기 3. 0인 개수 구하기 아래는 풀이한 코드입니다. 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72.. [백준] 1260번 DFS와 BFS [풀이] 가장 기본적인 DFS와 BFS를 구현하는 문제입니다! 아래는 구현한 코드입니다. 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 50 51 52 53 54 #include #include #include #include #include using namespace std; vector gf(1001); bool visited[1001] = { false }; void bfs(int v) { queue q; visited[v] = true; q.push(v); while (!q.empty()) { in.. [백준] 2816번 디지털 티비 [풀이] 답이 하나만 정해져있는 것이 아닌 문제였는데요, 저는 예제처럼 33이 아닌 1과 4만 사용해서 Greedy하게 해결했습니다. 단순하게 KBS1 찾아서 제일 위로 올리고 KBS2 찾아서 그 위로 올려버렸습니다. 이렇게 하면 만약 채널 수가 최대값(100) 이더라도 눌러야할 버튼 수가 400번이 안됩니다.(문제 조건은 500개 미만) 아래는 해당 코드입니다 :) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include using namespace std; int main(void) { int n; cin >> n; int kbs1_idx, kbs2_idx; for (int i = 0; i > chnl; if (chnl.. [백준] 3109번 빵집 [풀이] 이 문제는 DFS를 활용해서 Greedy 하게 풀 수 있는 문제입니다. DFS를 활용한다는 건 점을 하나하나 이어가면서 x면 되돌아오는 식으로 하는 것으로 쉽게 이해할 수 있는데, 여기서 가장 중요한게 Greedy 부분입니다. 만약 DFS만 활용했을 경우에는 20 20 ..................x. ..................x. ..................x. (중략...) .................... 이런 입력에 대해서 시간초과가 나오게 됩니다. x가 끝쪽에 있으니 거의 모든 경우의 경로를 다 돌아보게 되기 때문입니다. 그렇기 때문에 Greedy를 활용해 주어야 합니다. 이미 실패한 경로는 다시 가더라도 어짜피 결과는 FAIL 입니다. 그러므로 성공한 경로든 실패한.. [백준] 8980번 택배 [풀이] 처음에 많이 헤맸지만.. 결국 각 마을 마다 실을 수 있는 공간을 체크해나가며 해결할 수 있는 문제였습니다. 문제를 해결하기 위해선 우선 도착지를 기준으로 오름차순 정렬 해주어야 합니다. 출발지는 상관 없습니다. 왜 그런지는 이 후에 제가 설명드리는 과정을 보면 이해할 수 있을 겁니다:) 1. 출발지부터 도착지 - 1 까지에서 트럭 잔여용량이 가장 적은 곳 찾기 2. 실을 박스의 수 정하기 (1에서 찾은 잔여용량보다 박스의 수가 많다면 1에서의 결과값만큼 박수 싣기) 3. 출발지부터 도착지 - 1 까지 실을 박수의 수만큼 잔여용량을 줄여주기 이렇게 3가지를 차례대로 반복해줍니다. 문제상의 예제를 바탕으로 풀이해보겠습니다. 마을 1 2 3 잔여용량 40 40 40 우선, 초기상태 입니다. 마을은 .. [백준] 1543번 문서 검색 [문제] 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 문제 입니다. 예로, 문서가 abababa가 있을때 찾으려는 문장이 ababa 라면 중복되지 않게 1번 등장합니다. [풀이] 이 문제는 KMP 문자열 탐색 알고리즘을 쓰면 간단하게 해결되는 문제 입니다. 제 블로그의 문자열 탐색 알고리즘 KMP에 코드와 함께 설명을 작성해 두었습니다 :) 아래는 문제 풀이한 코드입니다. 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 50 51 52 53 54 55 56 5.. 이전 1 2 3 4 다음
