본문 바로가기

Algorithm8

백준 12100 삼성기출 2480(Easy) 알고리즘 자체의 난이도는 높지 않지만 예외케이스와, 기저가 많아 집중하고 체계적으로 코딩해야되는 문제였습니다. BFS,DFS 모두 사용가능하나 brute force로 흝어봐야하는 문제이기 때문에 어차피 시간복잡도가 같다면, 메모리를 더 아낄 수 있고 코드도 좀 더 깔끔한 재귀함수 DFS를 추천드립니다. (재귀함수를 사용하면 function stack을 계속 만드는 오버헤드는 있다고 합니다. 다만 함수 내용이 짧을 수록 함수 stack 생성 오버헤드가 상대적으로 더 큰 것이지, 그외는 괜찮은 듯합니다. DFS도 stack 자료구조를 사용하면 재귀를 사용하지 않을 수 있습니다.) #include #include #include #include using namespace std; typedef unsigne.. 2020. 4. 20.
백준 13460번 삼성기출 구술탈출2 문제의 알고리즘 자체는 어려운편은 아니지만, 예외 케이스가 많고 기저 사건이 다양하기 때문에 문제를 잘읽고 코드는 최대한, 실수가 나지 않게끔 길어지더라도, 명확하게 분류해서 잘짜는게 중요한듯 합니다. 알고리즘은 기본적인 BFS 최단 문제입니다. #include #include #include #include #include using namespace std; int N, M; string Map[10]; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int oy, ox; int bx, by; int rx, ry; struct pos { int bx, by; int rx, ry; int cnt; pos(int by, int bx,int ry,int rx, int .. 2020. 4. 20.
백준 2352번 nlog(n)으로 풀기, LIS 알고리즘의 이해 (longest increasing Subsequence ) 백준 2352번은 일반적인 DP코드로는 N^2 시간복잡도가 걸립니다. 왜 N^2인지는 밑의 코드 주석에 작성 알고리즘에서 lower_bound라는 함수를 사용했는데, 대단한 함수는아니고 직접 작성하여도 되는 함수이다. lower_bound(첫주소, 마지막주소, 찾는 값) return iter or pointer 주소값 매개변수 인자는, STL의 iterator를 넣어도 되고, 배열의 주소값을 넣어도 됩니다. 이 함수는 이미 오름 차순으로 sort된 배열에서 binary search를 하여 찾고자 하는 값이 있는 인덱스(iter or 주소)를 알려주는 함수입니다. 만약 값이 존재하지 않는다면, 찾는값 보다 큰 수 중에서 작은 값을 찾습니다. (2, 5, 8) 에서 4를 찾는다면 idx 1 (5) 반환 모든.. 2020. 4. 10.
백준 2631 줄세우기 LIS 개념 다이나믹 프로그래밍 줄세우기 문제는 3 7 5 2 6 1 4 라는 수열이 있으면 숫자를 최소로 움직여 정렬 상태로 바꾸는 문제이다. (1 2 3 4 5 6 7) dp문제로 분류되어 있지만 바로 DP를 사용하기에는 감이 잡히지 않았다. 이런 문제를 LIS 문제라고 하는데, 위 문제를 잘 생각해보면 모든 숫자는 한번 움직이기만하면 원하는 위치에 딱 놓을 수 있다. N개 문제가 있다면 N번 안에 무조건 해결 가능하다. 어쩌면 어떤 숫자들은 가만히 있어도 된다. 즉, 최대한 많은 숫자들이 움직이지 않아도 될 수록 좋다는 것 !!! 그리고 건들이지 않아도 되는 숫자들은 , 이미 각 숫자들이 오름차 순으로 있다는 것 그렇다면 우리는 이미 오름차순으로 정렬되어있는 가장 긴 순열 길이를 찾으면 된다. 위 문제에서는 3 7 5 2 6 1 .. 2020. 4. 7.

티스토리툴바