알고리즘 (74) 썸네일형 리스트형 백준 10971 - 외판원 순회 2 - dfs 를 이용한 순열 구현 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 10819 차이를 최대로 문제에서 순열을 dfs로 구현하는 것에서 아이디어를 따와 풀었다. 거기보다 이 문제에서 조금 더 주의해야 할 점은, 마을마다 방문한 노드는 다시 방문하면 안되는 것은 기본이고, edge가 0인 경우에는 갈수 없다는 조건까지 검사해보아야 한다. 일단 이.. 백준 10819 차이를 최대로 - 브루트포스(순열 구하기) c++ https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 순열을 구하는 방법은 여러가지가 있다. STL에서 벡터의 순열을 구하는 방법도있고, 아니면 길이가 N이 될때까지 모든 방법에 대해서 백트래킹을 진행하면서 dfs를 때리는 방식도 있다. 나는 후자를 선택해서 풀어보았다. 하지만 stl 사용 방식도 공부 해 볼것. 브루트포스의 범위는 꽤 넓구나. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2.. 백준 1107 리모컨 - 브루트포스 - c++ https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 우선 이 문제를 풀기 전 내 아이디어(브루트 포스 첫 문제다.) 고장난 리모컨 버튼들을 입력받아서, 0-9에서 뺀다. 그럼 잘 작동하는 리모컨 버튼만 입력을 받을 수 있을 것.(arr나 벡터에 저장하기.) 가장 큰 자리수부터 검사해서, 배열에 있는지 없는지 확인. 없으면 차이의 절댓값이 제일 작은 녀석을 골라서 다 밑의 자리.. 백준 1759 - 암호만들기 (백트래킹) c++ https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제를 바라보면서 머릿속으로 해야하는 생각: 정렬된 문자열로 출력해야 한다 --> 입력 받으면 일단 정렬 한번 때려야 됨. 길이와 자음모음 갯수 조건이 있음 --> 출력하는 부분에서 확인해야 된다. 길이는 s.size()로. 자음모음 개수는? --> 저장해가면서!! 파라미터에다가. 여기까진 ok. 한번 어떤 알파벳을 골랐으면, 사전순서 이전에 있는 알파벳은 다음에 죽어도 못고른다. 그건 어떻게 구현하지.. 백준 1992 - 쿼드트리 (분할정복) C++ https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. www.acmicpc.net 언제 괄호를 출력해야 하는지 확실히 구분해야 한다. 분할정복이 이뤄지는 시점 시작과 끝에만 괄호를 집어 넣을 것. 그 부분 에만 괄호가 들어가야 하고, 그 이외의 시점에는 숫자만 출력하는 것을 확실히 해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 백준 11729 하노이 탑 이동순서 - 분할정복 -C++ https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 사실 문제를 보고 꽤 고민을 해봤는데, 어떻게 푸는 문제인지 전혀 감이 잡히지 않았다. 아직 PS에 대한 감이 많이 부족.. 백준 1780 종이의 개수 - 분할정복 - C++ https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 전형적인 분할정복 알고리즘이다. n*n짜리 배열에서 같은 숫자가 나오면 패스고, 다른 숫자가 검출이 되면 n/3*n/3짜리 배열 9개.. 백준 2110 공유기 설치 - 이분탐색 C++ https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net main 함수의 이분탐색 방식은 똑같고, 어떤 interval을 두고 공유기를 설치할수 있냐 없냐를 판단 하는 여부가 조금 까다로운 부분이지 않았나 싶었다. 13번째 줄에 current_x를 current_x+interval로 두지 않고 x[i]로 두어야 하는 부분을 조심하자. 어떤 인터벌을 두고 공유기를 n개 이상 설.. 이전 1 ··· 5 6 7 8 9 10 다음
