본문 바로가기

알고리즘

 (74)
백준 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..
백준 2252 줄 세우기- 위상정렬 개념공부, 큐를 이용한 위상정렬 (c++) 우선순위 큐 문제를 풀어보려고 했다가, 위상정렬 개념을 처음 들어봐서 공부도 하고, 문제도 풀어본 좋은 경험이 된 문제인 것 같다. 문제를 풀기 전에 위상정렬에 대한 개념을 위키피디아에서 공부했다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이..
백준 18429 근손실 - dfs와 백트래킹 (c++) https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다. 다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 www.acmicpc.net 백트래킹을 하면서, 근손실이 나지않는 조건 하에서 dfs를 끝까지 진행한 경우에 결과에 +1씩 해주면 되는 문제였다. 백트래킹의 대표적인..

티스토리툴바