알고리즘/백준 (68) 썸네일형 리스트형 백준 1963 - 소수경로 - bfs,몫 나머지 활용 - C++ https://www.acmicpc.net/problem/1963 백준 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를 진행하면서 넣고 빼고를 반복하면서 카운팅만 잘 해주면 풀 수 있는 문제지만 따져야 되는 조건들.. 백준 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에 대한 감이 많이 부족.. 이전 1 ··· 4 5 6 7 8 9 다음
