백준 (22) 썸네일형 리스트형 백준 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.. 백준 3055 탈출 - 확산하는 물체가 2개 있을때 bfs를 돌려야 한다면? 문제 링크 www.acmicpc.net/problem/3055 풀이 아이디어 최단경로 문제이므로 당연히 BFS를 이용해서 풀어야 한다. 문제는 확산하는 물체가 고슴도치 1개와 물 n개라는 것이다. 구체적으로 푸는 방식은 여러개가 있을 수 있다. 나는 bfs 함수를 하나만 정의했지만 물이 이동하는 bfs, 고슴도치가 이동하는 bfs 함수를 각각 짜서 비교해보며 진행을 해도 된다. 하지만 각 객체(고슴도치,물) 이 확산하는 정보는 따로 관리가 들어가야 하므로 queue는 2개를 반드시 이용해 주어야 한다. 나는 queue 2개를 이용을 하되, 함수를 하나만 정의 했다. 문제의 조건에 따라 물을 먼저 이동시키고, 그 이후에 고슴도치를 이동시키기. 추가적으로 사용한 2가지 팁은 1. for문을 이용해 큐의 사이.. 백준 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.. 백준 14226 이모티콘 - 2차원 배열로 상태저장 bfs - c++ 링크 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net 아이디어 오랜만에 bfs관련 풀어본 문제. 이문제는 주의해야 할점이, 클립보드에 복사한 이모티콘 갯수는 몇번이고 재사용이 가능하.. 백준 13335 트럭 - 큐 2개를 활용하자 c++ 문제 링크: https://www.acmicpc.net/problem/13335 13335번: 트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최 www.acmicpc.net 큐를 이용해서 시뮬레이션을 구현하는 문제로 특별한 알고리즘은 없는 문제다. 다만 이런 시뮬레이션 문제를 처음 풀어보았기 때문.. 백준 1261 알고스팟: bfs와 caching 쓰는 문제 c++ https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 사실 이 문제는 분류가 다익스트라 알고리즘으로 분류되어있었는데, 그 알고리즘에 대해서 몰라도 풀수 있다. 전형적인 bfs문제는 아니고 다이나믹 프로그래밍의 캐시 개념만 조금 쓰면 풀 수 있다. 어떻게 보면 최단 경로 문제이기 때문에 (빙빙 돌아가면서 벽을 부숴가면서 미로를 탐색하진 않을것 아닌가?) bfs를 쓰는 것은 당연한 .. 백준 1697 숨바꼭질 - bfs - c++ https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 한 7번;; 만에 풀었다. 큐에다가 bfs를 진행하면서 넣고 빼고를 반복하면서 카운팅만 잘 해주면 풀 수 있는 문제지만 따져야 되는 조건들.. 이전 1 2 3 다음
