영모저모

다시금 코테를 준비하면서 풀어본 프로그래머스의 3단계급 문제 되시겠다. 뭐 엄청 오랜만에 풀어본 것 같지만, 한번에 통과하다니...역시 머슬 메모리가 남아있는 것일까? 하지만 문제를 풀어보면서 생각해보니 낭비되는 메모리도 좀 있던 것 같아 이부분이 아쉽다고 생각했다. 나의 경우, BFS를 통해서 문제를 해결하였다. 다른 사람들을 보니, DFS를 통해 해결하는 사람도 많았고, 백트래킹으로 푸는 사람도 있었지만, 아무래도 BFS가 낫지 않을까? 라고 생각해 풀게 되었다. #include #include #include using namespace std; int *visited; int cnt; string begins; string targets; queue Queue; bool littleSame(str..

이번에 푼 문제는 0-1 knapsack 문제인 12865번 평범한 배낭 문제를 풀었다. 솔직히 이런말하긴 뭐하지만 개갓이 어려웠다. 진짜진짜진짜 개갓이 아니 문제 아니 알고리즘이 이렇게 어려워도 됨? 이거 공부부터 해석하는데만 기절하는줄 알았음... 이거도 다이나믹 프로그래밍의 종류인, 0-1 knapsack(배낭)문제이다. 보통의 배낭 문제라고 한다면 그리디 알고리즘으로 해결할 수 있는데, 0-1 knapsack문제는 다르다. 그리디 알고리즘으로 푼다면 최적값이 아니기 때문에 틀려버리는데, 동적 계획법이나 백트래킹기법으로 접근해야만 문제를 해결할 수 있다. 아니 나도 너무 어려워서 관련 알고리즘 짜는 법을 검색해보고 공부했는도 아직 어려웠다ㅠ #include using namespace std; in..

오늘은 이진탐색(Binary Search)문제를 해결하였다. 문제만 본다면 그냥 탐색으로 풀 수도 있겠지만, 그렇게 풀면 시간 초과가 나올 것이 분명했기에 이진 탐색으로 문제를 해결하였다. 사실 오늘 하루종일 피곤했는데, 그래도 빠르게 문제를 해결했다ㅎ ㅎ 예전 대학교 알고리즘 수업 때에는 엄청 고생했던 것 같은데 다시 풀어보니 그때의 기억이 조금 살아난게 아닐까 싶었다. 이진 탐색은 배열의 탐색법중 하나로, 오름차순 정렬되어있는 배열에 내가 찾고자 하는 값을 얻는 방법이다. 탐색하는 방법으로는, 찾는 수를 배열의 중간값와 비교하여 재귀적으로 다시 함수를 호출해 범위를 좁혀나가고 값이 있는지 확인하는 방법으로, 시간 복잡도가 O(logN)으로 굉장히 빠른 알고리즘이다. #include #include #..

예고대로 오늘은 동적 프로그래밍 문제인 24416번 피보나치 수를 풀었다. 문제가 나와있는 수도코드대로만 하면 바로 풀리는 문제라 약간 죄책감이 들었을지도.. 사실상 다이나믹 프로그래밍이 재귀에 비해 얼마나 빠른지 알려주는 문제라고 볼 수 있는데, 그렇기 때문에 문제 난이도 자체는 쉽게 하여 많은 사람이 다이나믹 프로그래밍을 이해하는데 도움될 수 있도록 한 문제라고 생각한다. 다이나믹 프로그래밍은 문제를 해결하는데 있어서, 해당 문제에 대해 이전이나 다른 범위의 값을 이용하여 더욱 효율적으로 값을 구하는 알고리즘 기법이다. 이전에 했던 문제들과는 다르게 정형화 되어있지 않고, 음.. 알고리즘이라고 하기보다는 이런식으로 풀면 된다! 라고 말해야 할법한 방법? 나는 그렇게 생각하고 있다 위 문제 또한, 재귀..

DFS때의 9실패를 만회하고 원트원클 해버린 모습 ㅎㅎ; VS에서 디버그를 오질나게 돌렸더니 성공해버렸다. BFS도 수도 코드만을 보고 풀었는데, 의외로 DFS보다 할만했다고 생각한다. 머리가 오늘따라 잘돌아간건가? 사실 수도코드가 전부인 문제라고 생각했고, 원리를 이해하니 어렵지는 않다고 생각하여 고민만 했던 것 같다. 아무튼 결과는 원트원클로 성공~ 역시나 이번에도 시간초과를 방지하기 위해 ios_base를 사용하였다 해당 문제는 DFS와 항상 같이나오는 BFS를 사용하여 문제를 해결했다 BFS는 너비우선탐색(Breadth First Search)라고 부르며, 그래프의 탐색법중 하나이다. DFS와는 다르게, 뭐랄까 다음 차수의 모든 노드를 방문한 뒤, 다시 차례대로 다음 차수의 노드를 방문하는? 구조..

우선 이번엔 시간초과 보다는 런타임 에러가 많이 떳다. 범위 오류와 Segmentation fault ㅎㅎ; 문제 자체를 잘못 이해하여 방문하는 순서를 적는 줄 알았는데, 알고보니 순서대로 i번째 정점이 몇 번째로 출력되는질 적는 것 이였다... 이걸 이해못해서 틀린게 세번 시간초과또한 두 번이나 나왔는데, 굳이 vector를 이용하여 find를 사용해 풀었기 때문에 시간복잡도가 O(N)이 나와버려 시간이 오바되버렸다... 그냥 visited를 int로 바꿔줬으면 되는걸 아무튼 짜잘한 문제를 전부 해결 하고 나니 성공! 이번에도 시간을 줄이기 위하여 ios_base를 사용하였다. 해당 문제는 DFS를 활용하는 문제이다. DFS가 아니면 어캐풀지? 란 느낌의 정석 DFS문제였다. DFS는 깊이 우선 탐색(..

친구의 C++ 시험공부를 도와주다 이런 문제를 보았다. #include using namespace std; int main() { short arr[5]; short*p = &arr[3]; short*q = &arr[0]; int r = p - q; cout