반응형 전체 글62 백준 14503번 - 로봇 청소기 (C++) 문제 해결 방법 게임 몬스터 자동 이동 프로그래밍 하듯, 그냥 시키는대로 코딩하면 된다. 객체가 하나여서 재귀를 사용하였다. 아쉬웠던 점 두번째 if문과 while문의 내용이 비슷해서 하나로 어찌 잘 묶어볼 수 있었을 것 같은데, 쓸대없이 길어진 것 같아서 아쉽다. 코드 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 73 74 75 76 77 78 79 80 81 82 83 84 85 .. 2021. 4. 9. 에라토스테네스의 체 알고리즘 진행 과정 순차 탐색 -> 색칠되지 않은 칸 발견 -> 해당 칸을 소수로 분류하고, 해당 숫자의 곱을 모두 색칠. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include using namespace std; bool Num[1000001] = {}; int main() { int Start, End; cin >> Start >> End; for (int i = Start ; i 2021. 4. 8. 백준 1929번 - 소수 구하기 C++ 문제 알고리즘 분류 : 에라토스테네스의 체 해결 방법 : 에라토스테네스의 채를 구현하면 끝나는 문제. 아쉬웠던 점 글을 쓰며 생각이 들었는데, Num 배열 또한 절반만 사용할 수 있었는데 그러지 않아서 아쉽다. 코드 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 #include using namespace std; bool Num[1000001] = {}; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int Start, End; cin >> Start >> End; for (int i = 3; i 2021. 4. 8. 백준 7562번 - 나이트의 이동 (C++) 문제 알고리즘 분류 : 너비 우선 탐색(BFS) 접근 방법 BFS를 몰라서 검색해봤다. 만들기는 매우 쉬웠던 것 같다. (youtu.be/_hxFgg7TLZQ?t=193이거 3분 13초 ~ 5분까지 봤음.) BFS는 깊이를 기준으로 깊이가 1인 노드 탐색 -> 2인 노드 탐색 -> 3인 노드 탐색... 으로 진행되는데, 여기서 깊이(자식) = 체스말의 이동 횟수라고 생각하면 금방 해결할 수 있는 문제였다. 탐색 순서는 사실 한번 이동해서 갈 수 있는곳 -> 두번 이동해서 갈 수 있는곳 -> 세번 이동해서 갈 수 있는... 이런식으로 상당히 비효율적으로 진행되는 것 같다. 코드 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 .. 2021. 4. 7. 그리디(Greedy) 알고리즘 Greedy(욕심) 알고리즘이란? 매 선택에서 지금 최선인 답을 선택하는 알고리즘. 다만, 종합적으로 판단하는 것이 아니기 때문에 결과적으로 정답이 아닐 수 있다. 진행 과정 두 숫자를 거쳐서 총 합의 최소를 구하는 과정에서, 정답은 시작->20->30 으로 총합 50이지만, 그리디 알고리즘을 통하여 접근하면 해당 알고리즘은 언제나 "현재 선택지의 상황만"고려하여 답을 찾는 알고리즘이기 때문에 1. 20보다 15가 더 적으니 15로 진행. 2. 100과 200중 100이 더 적으니 100으로 진행. 이런 방식을 통하여 총합 115가 정답으로 도출된다. 2021. 4. 6. 백준 2504번 - 괄호의 값 (C++) 문제 구현 방법 각 괄호마다 괄호 내부의 숫자들을 곱해주기 위하여 재귀를 통하여 구현했다. 크게 세 단계로 구성되어있으며, 먼저 붙어있는 괄호들을 A2B/A3B형식으로 숫자로 바꾸어준다. AB는 2 3 이 23인지 2와 3인지 숫자끼리 구분하기 위하여 덧붙였다. 그리고 이 과정에서 괄호의 갯수를 세며 존재가 불가능한지 판단한다. 이후 재귀를 돌며 괄호를 만나면 해당 괄호가 끝날때까지 그 사이에 있는 A?B에 괄호별 값을 곱해준다. 이때 string에서의 곱 이기 때문에 정수로 변환 후 곱한 후 해당 결과를 삭제->중간 삽입 하는 과정을 거쳐서 곱연산을 하게 되었다. 이를 재귀로 반복하여 문자열의 끝까지 있는 모든 괄호에 대하여 연산을 마치고, 이후 다시 순회하며 모든 숫자들을 더해준다 아쉬웠던점 중간 삽.. 2021. 4. 4. 이전 1 ··· 7 8 9 10 11 다음 반응형
