본문 바로가기

알고리즘/백준

 (68)
백준 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..
백준 2872 - 우리집엔 도서관이 있어 c 문제 링크 https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 문제 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다. 책은 1부터 N까지 번호가 책 이름의 사전 www.acmicpc.net 풀이 아이디어 처음엔 어떻게 풀지 좀 막막하다가, 여러 그림을 그려보고 방법을 깨닫게 되었다. 다음과 같이 책이..
백준 1655 가운데를 말해요 : 우선순위 큐 두개로 가운데를 빠르게 c++ 문제 링크 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 풀이 아이디어 이 문제는 오직 '가운데' 에 무엇이 있냐만 관심이 있는 문제이다. 만약 이 문제를 입력이 들어올때마다 정렬해서 가운데 인덱스의 원소를 출력하려고 하면 nlogn의 시간이 걸린다. 1부터 100000까지의 입력이 들어온다고 가정할때 합치면 약 1700초의 시간이 걸리는 무식한 방법이므로 이 방법은 쓸..

티스토리툴바