분류 전체보기 (81) 썸네일형 리스트형 [백준] 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.. [백준] 1201번 NMK [풀이] 이 문제는 N개의 수를 M개의 덩이로 나누어서 그를 역순으로 하는 문제 입니다. 우선, M + K - 1 [백준] 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 우선, 초기상태 입니다. 마을은 .. [백준] 9576번 책 나눠주기 [풀이] 정답 비율을 보고 쫄아있었는데.. 설마 이게 맞겠어 하며 제출했는데 바로 맞아버려서 생각보다 너무 간단하게 풀려 조금 허무했던 문제입니다. 책의 범위 a~b에서 b를 기준으로 우선 오름차순 정렬 하면, 어짜피 최고로 빌릴수 있는 숫자는 b까지 입니다. 그래서 a가 무슨 숫자가 오든 상관 없이 순서대로 주면 꼬일 일이 없습니다. 하지만 a를 기준으로 정렬한다면 최고로 빌릴 수 있는 숫자가 뒤죽박죽이 되면서 꼬여버리게 됩니다. 아래의 예를 봅시다 1 5 2 2 1 5 3 3 1 5 vs 1 5 2 2 1 5 3 3 1 5 (a 기준) (b 기준) a를 기준으로 정렬했다면 1, 2, 3번 책밖에 주지를 못합니다. 하지만 반대로 b를 기준으로 했다면 2, 3, 1, 4, 5 순서로 모든 책을 빌려줄수 .. 이전 1 ··· 6 7 8 9 10 11 다음
