본문 바로가기

분류 전체보기

 (106)
백준 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로 마킹하면서 확인. 하지만 백트래킹하는..
프로그래머스 1단계 배지획득! 프로그래머스 문제들도 풀기 시작하려고 한다 이제부터. 오늘 1단계를 시험삼아 봐봤는데, 13분만에 2문제를 풀정도로 쉽다. 백준의 '수학' 파트들 을 보면 참고가 될 것 같다. 굿굿~
백준 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씩 해주면 되는 문제였다. 백트래킹의 대표적인..
백준 2580 - 스도쿠 ( 재밌는 dfs 문제) c++ https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 최소경로 문제가 아니므로 bfs가 아닌 dfs 문제이다. 오랜만에 dfs 백트래킹 문제를 만났는데, n queen에서 공부했던 백트래킹의 ..

티스토리툴바