본문 바로가기

알고리즘/백준

 (68)
백준 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를 쓰는 것은 당연한 ..
백준 2143 두 배열의 합 - 단순 브루트포스 c++ https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net 배열별로 가질 수 있는 모든 부분합의 경우와 경우의 수를 우선 전부 구해 T가 되는 가지수를 구하면 되는 문제였다. set를 활용해 key value 값으로 저장해 구현할수도 있지만 벡터를 활용..
투 포인터 알고리즘, 슬라이딩 알고리즘 https://m.blog.naver.com/kks227/220795165570 투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09) 조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다.첫 번째로 소개해드릴 기법은 투 포인터(tw... blog.naver.com 몇분 동안 여러 블로그들을 봤는데 위에 있는 글이 제일 깔끔하게 두 알고리즘에 대해 정리해 놓은 것 같다.
백준 1182 부분수열의 합- 재귀 브루트포스 (c++) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 수열의 길이가 최대 20이고, 합이 s가 되는 모든 경우를 찾아야 하므로 재귀함수를 이용한 브루트포스 방식으로 접근해보았다. 수열의 i번째 index를 탐색한다고 하면 그 이전 index는 탐색했다고 가정하고 그다음 인덱스 부터 나머지 모두를 전부 탐색하는 방식으로 재귀함수를 짜면 된다. 그리고 main함수에서는 0번째 index부터 탐색하면 된다. 그렇게..
백준 1987 알파벳 - dfs와 백트래킹 (c++) https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net dfs + 백트래킹 문제였다. 알파벳 별로 방문을 한번이라도 했는지 안했는지를 alphavisited로 마킹하면서 확인. 하지만 백트래킹하는..
백준 1110 더하기사이클 - while문, 수학 문제 (c++) 문제 링크 https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자. 26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = www.acmicpc.net 십의자리수와 일의자리수를 가지고 장난치면서, 원래 입력받았던 수와 같아지는지 알아보는 문제이다. 1 2 3 4 5 6 7..
백준 1766 문제집 - 우선순위 큐를 활용한 위상정렬 문제 (c++) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다. 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 이 문제는 위상정렬을 이용하되, 조건이 하나 붙게 된다. 바로 쉬운 문제 순서대로 풀어야 한다는것. 이를 활용하기 위해서는, 항상 큐에 들어있는 문제 중 쉬운 문제 순으로 풀도록 우선순위 큐를 활용해서 풀어야 한다. 우선순위 큐는 prio..

티스토리툴바