본문 바로가기

알고리즘

 (74)
백준 2565 전깃줄 - 아이디어가 중요한 DP 문제 문제 링크 www.acmicpc.net/problem/2565 풀이 아이디어 아이디어가 되게재밌다. 우선 전기줄이 '겹치게 되는는' 조건이 어떻게 되는지를 한번 생각해 봐야된다. 왼쪽 전봇대에서 위 아래로 시작하는 줄이 오른쪽 전봇대에서 아래 위로 끝나면 겹치게 된다. 근데 이렇게 생각하기 시작하면 개인적으로 좀 어려워 진다고 생각한다. 하나 기준을 정해야 한다. 왼쪽 전봇대로 정하는 것이 편하다. sort가 편하기 때문이다. 그러면 왼쪽 기준으로 정렬 되어있는 상태에서 for문을 돌릴 때, 오른쪽 에서 대소관계의 순서가 유지되면 안겹치는 것이다. 문제의 그림을 예시로 들자면 A를 기준으로 오름차순 정렬을 한 후 탐색을 진행하는 것이다. 1,2에서 시작하는 전기줄은 각각 8,2에서 끝난다. 1,2를 볼 ..
백준 2644 촌수계산 - bfs에서 메모리초과가 안뜨게 하려면? 문제 링크 www.acmicpc.net/problem/2644 풀이 아이디어 최단거리 문제니까 당연히 dfs가 아닌 bfs를 이용해서 푸는 것이다. 노드번호와 cost의 쌍을 큐에 넣고 bfs돌리면 쉽게 풀 수 있다. 문제는 메모리! 아래 주석 친 부분에 처음에 if-return문을 넣었다가 메모리 초과가 떴었다. BFS 조건 판단은 반드시 방문여부 체크한 후에 하기!! 코드 #include using namespace std; vector tree[101]; bool visited[101]; int bfs(int a, int b){ queue q; q.push({a,0}); visited[a]=true; while(!q.empty()){ int front = q.front().first; int cos..
ACM craft - 테스트케이스 while(t--) 스타일 문제, 위상정렬 문제 링크 www.acmicpc.net/problem/1005 풀이 아이디어 fill_n을 통한 메모리 관리 및 초기화 전형적인 위상정렬 문제 위상정렬은 항상 '조상 개수 0인 노드 queue에 넣고 문제에 맞는 해당 작업 진행하기' 임을 기억하기. 코드 #include #include #include #define N 1005 using namespace std; int ans; int n, k, w; int dp[N] = {}; int arr[N] = {}; int inDegree[N] = {}; vector v[N]; queue q; void f_initialize(int n) { fill_n(dp, n + 1, 0); fill_n(arr, n + 1, 0); fill_..
백준 3190 뱀 - 앞뒤로 넣고 빼야 될 때는 deque를 활용하자! 문제 링크 www.acmicpc.net/problem/3190 풀이 아이디어 아이디어 랄건 딱히 없는데 구현을 잘 해야 풀 수 있는 문제다. 뱀의 머리와 꼬리를 이동시키고, 복제시키고 하는 로직때문에 머리꼬리를 동시에 관리해야 한다. 이럴 경우에 적합한 자료구조는 deque라고 널리 알려저 있기 때문에 deque을 사용해서 변수를 관리한다. 주의해야 할 점을 몇 가지 적자면 1. 뱀의 몸통이랑 부딪히는 것까지 생각을 해야 하므로 bool snake[][] 배열을 만들어, 뱀이 있는 공간은 true로 설정을 한다. 2. 명령이 L개 주어지는데, 명령이 있을 때만 명령을 읽고 처리하기 위해 if(opdq.size()) 조건이 꼭 필요하다. 만약 명령이 담긴 deque인 opdq의 size가 0일때는 그냥 실..
백준 3055 탈출 - 확산하는 물체가 2개 있을때 bfs를 돌려야 한다면? 문제 링크 www.acmicpc.net/problem/3055 풀이 아이디어 최단경로 문제이므로 당연히 BFS를 이용해서 풀어야 한다. 문제는 확산하는 물체가 고슴도치 1개와 물 n개라는 것이다. 구체적으로 푸는 방식은 여러개가 있을 수 있다. 나는 bfs 함수를 하나만 정의했지만 물이 이동하는 bfs, 고슴도치가 이동하는 bfs 함수를 각각 짜서 비교해보며 진행을 해도 된다. 하지만 각 객체(고슴도치,물) 이 확산하는 정보는 따로 관리가 들어가야 하므로 queue는 2개를 반드시 이용해 주어야 한다. 나는 queue 2개를 이용을 하되, 함수를 하나만 정의 했다. 문제의 조건에 따라 물을 먼저 이동시키고, 그 이후에 고슴도치를 이동시키기. 추가적으로 사용한 2가지 팁은 1. for문을 이용해 큐의 사이..
백준 19236 청소년 상어 : 내가 했던 4가지 놓친 점들과 함께 문제 링크 www.acmicpc.net/problem/19236 풀이 아이디어 사실 풀이 아이디어는 간단했다. 4*4의 제한된 공간과 가능한 경우 중 최댓값을 찾는 문제. 완전 탐색이다. 문제에서 말하고 있는 대로, 상어를 이동시키기 전 물고기들을 전부 이동시킨 후, 이동할 수 있는 상어를 백트래킹을 통해 탐색하면 되는 문제였다. 나는 이 문제를 풀면서 몇 가지 실수들을 했었는데, 우선 최종 solved 받은 코드를 보고 이야기를 해보겠다. 코드 #include using namespace std; int fisharr[4][4]; int dirarr[4][4]; int answer=0; int dx[8] = {0,-1,-1,-1,0,1,1,1}; int dy[8] = {-1,-1,0,1,1,1,0,-1..
백준 1972 놀라운 문자열 - substr로 해결못하는 문자열 처리 문제 문제 링크 https://www.acmicpc.net/problem/1972 1972번: 놀라운 문자열 문제 대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 �� www.acmicpc.net 종강 기념으로 다시 알고리즘 시작한다! 길고 긴 학기였다... 해결 아이디어 문자열 처리 문제이다. 각 case에 대해 1부터 len-1 까지, 처음부터 끝까지 검사하고 , set를 이용해 하나도 겹치지 않고 나오는지 개수를 파악해서 검사했다. 총 n^3의 시간복잡도가 사용되겠지만 case수가 100개가 최대이므로 시간내에 돌아간다. 코드 #include using namespace..
다익스트라와 플로이드 와샬, A* 알고리즘의 차이점. 언제 써야 할까? 그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem) 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem) 하나의 목적지로가는 모든 최단 경로를 구하는 문제(single destination shortest path problem) 마지막으로 모든 최단 경로를 구하는 문제(All pairs shortest path problem). 1번째 시작과 목적지가 두개 정확히 지정이 되어있는 경우 --> A* 알고리즘. (http://www.gisdev..

티스토리툴바