알고리즘 (5) 썸네일형 리스트형 알고리즘 유형 (DP, 다이나믹 프로그래밍) DP는 알고리즘 문제 중에 가장 감이 잡히지 않는 유형이다. 개념 자체는 이해가 되지만 문제를 봤을 때 DP로 풀어야겠다고 바로 떠올리기가 힘들다. DP문제 임을 알고 풀지만 문제만 보고 DP 문제라고 판단하기가 쉽지 않다. 일단 대표적인 DP 문제 유형을 나름 정리하면서 감을 잡으려 하고 있다. DP는 dymamic programming의 약자로, 직역하면 동적 프로그래밍이다. 동적 프로그래밍이라고 해서 동적할당 방법을 쓰지 않는다. 이름과는 무관하게 '동적'과 관련이 없어서 '기억하며 풀기'가 가장 의미있다는 의견이 많다. DP는 큰 문제를 부분문제로 나누고 부분문제를 풀어가면서 결론적으로 큰 문제를 푼다는 개념이다. 이렇게만 들으면 분할정복과 다를 바가 없고, 앞서 이야기한 '기억하며 풀기' 랑도 .. 알고리즘 유형 (백트래킹) 나는 C++ 를 사용해서 백준 알고리즘 문제를 푼다. 단계별로 풀기로 문제를 푸는데 생소하고 처음보는 유형의 알고리즘이 나오면 블로그에 정리하려고 한다. 지금껏 프로그래밍 언어를 통해 과제가 주어지면 복잡도, 메모리, 중복여부 이런 부분들을 고려하지않고 짰었다. 알고리즘문제를 풀게 되면 나처럼 프로그래밍을 하던 사람은 필시 막힐 수 밖에 없다. 단계별 풀기 단계에서 처음으로 막혔던 부분은 정렬 알고리즘에서 였고 새롭게 느낀점과 알고리즘을 종류별로 이 블로그에 포스팅 했었다. 단순히 과제를 구현하는 데에 그치지 않고 시간복잡도와 메모리를 고려해서 짜는 프로그램의 중요성을 알게 되었다. 정렬 알고리즘 이후 개인적으로 막혔던 곳은 재귀-백트래킹-DP 단계이다. 재귀는 과제를 수행하면서도 많이 접해보아서 그렇게.. 알고리즘 시간 줄이기 (입출력 시간 줄이기 : 버퍼 비동기화 & io untied) 저번 정렬 알고리즘 포스팅에서 살짝 언급했던 입출력 시간 줄이기를 해보려고 한다. 백준 2751 문제를 풀기 위해 헤더파일에 있는 sort() 함수를 사용하려 했는데, sort() 함수의 복잡도가 O(nlogn) 인데도 불구하고 시간초과가 났었다. merge sorting 알고리즘도 같은 O(nlogn) 복잡도를 가지지만 시간초과가 나지 않는 것을 보면 sort() 함수 문제가 아니라 다른 부분에서 시간을 많이 잡아 먹는 다는 뜻인 것 같았고, 그래서 입출력에서 시간을 줄이는 방법을 찾아보기로 하면서 해당 부분들을 공부했다. 흔히 쓰는 방법 3가지가 있다고 한다. 그냥 코드만 붙여주면 되는 단순한 작업이지만 원리를 이해해서 능동적으로 활용하고 싶었다. c++ 입출력 버퍼와 c 입출력 버퍼를 비동기화 시키.. 알고리즘 시간 줄이기 (정렬 알고리즘) cpp를 복습하고 백준 알고리즘 문제를 풀면서 감을 익히고 있다. 그중 나름 공부가 되었던 것을 위주로 기록을 남기려 한다. 백준 2751번 문제이고 N개의 수를 입력받아 오름차순으로 정렬해 출력하는 간단한 문제이다. 겉보기엔 간단한 문제이지만 N의 입력 범위가 1 최솟값인 1과 정렬된 부분의 뒤(처음엔 정렬된 부분이 없으므로 0번째) 와 값을 바꾼다. 1 2 4 5 3 -> 1은 정렬된 배열이므로 그 다음 최솟값을 찾는다. -> 정렬된 배열 뒤의 값과 최솟값이 일치한다. 1 2 4 5 3 -> 그 다음 최솟값인 3을 4와 바꾼다. 1 2 3 5 4 -> 그 다음 최솟값인 4를 5와 바꾼다. 1 2 3 4 5 복잡도 최악의 경우의 수는 n + (n-1) + ... + 2 + 1 이고, 즉 n(n+1)/2.. cpp 복습 후 느낀 점 23.04.17를 끝으로 c++언어 복습을 마쳤다. 예전에 학습했던 c++언어를 이제와서 다시 꺼내보니 옛날 기억이 살아나면서 감회가 새로웠다. c++를 학습한 이유는 c++ 언어에나름 여러 프로그래밍의 요소들이 섞여 있기에 복합적으로 학습하기 좋다고 생각했기 때문이다. Java의 객체지향적 요소와 c언어의 포인터 개념을 c++언어를 통해 한 번에 익히기 좋았다. 처음 복습할 땐 굉장히 당황했다. for문도 제대로 작성하지 못하는 나를 보면서 너무 절망스러웠고 스스로에게 실망했다. 하지만 예전의 내 노력들은 나도 모르게 나에게 스며들어 있었고, 복습을 하면서 다시 쉽게 익히는 나를 보며 예전의 노력이 헛되지는 않았다는 것을 느꼈다. 영화티켓예매 문제를 똑같이 수행해 보면서, 옛날의 난 정말 무식하게 코딩.. 이전 1 다음
