개발자 퉁이리

https://programmers.co.kr/learn/courses/30/lessons/92343?language=python3 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr ⊙ 문제 ⊙ 제한사항 ⊙ 입출력 예 ⊙ 입출력 예 설명 ⊙ 문제 접근 과정 백트래킹으로 풀자! 계속해서 양의 수와 늑대의 수를 비교! 같아지는 순간 return. 아니라면 다음 노드를..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 브루트포스 알고리즘 백트래킹 ⊙ 문제 접근 과정 백트래킹 문제였는데 재미있었다. 반복문 i는 4번 돌린다. 범위는 0부터 3으로 각각 0,1,2,3은 순서대로 +, -, *, /이다. 사칙 연산에 대해 값을 모두 탐색하였을 때, 그 값이랑 현재 값이랑 비교하여 큰 값은 maxValu..

https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 이전 단계인 10탄에서 방문 여부만 제거해줬다! 왜냐하면 같은 수를 여러 번 골라도 되기 때문에. 하지만 같은 수를 여러번 골라도 같은 수열은 출력하지 않는다. set 덕분에 ㅎㅎ ⊙ 문제 풀이 #include #include #include #include using namespace std; #defi..

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 비내림차순이 무엇인지 알고 싶다면? 비내림차순에 대해서 적은 글 (N과 M 8탄)을 참고하자! 비내림차순을 구현하기 위해 9탄의 코드에서 num 변수를 추가적으로 만들어줬다.현재 값보다 높은 값만 출력할 수 있도록 하는 변수다. set을 통해 중복을 제거해줬고, visited를 통해 방문한 곳은 가지 않는..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 수열의 중복을 막기 위해 set을 사용했다. vector에 수열의 값을 저장을 M개만큼 저장하고 그 값들을 set에 저장한다. 이번 문제의 point! 이번 9탄에서는 방문처리인 visited을 사용하지 않으면 시간 초과가 발생한다. N과 M 9탄에서 드디어 방문 표시를 해야 하는 이유를 몸소 확인할 수 있..

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 방문 여부를 체크하지 않고, 기존의 값들을 배열에 저장해 정렬했다. 그그다음 백트래킹을 통해 값을 출력해줬다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 9 int N,M; int first[MAX]; int arr[MAX]; void d..

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 이전 문제에서 18번째 줄을 오름차순으로만 바꿔줬다. 풀이 방법은 전 시리즈와 같다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 9 int N,M; int first[MAX]; int arr[MAX]; bool visited[MAX]; v..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 18번째 줄만 계속 수정해주면 N과 M 시리즈가 풀린다! 다음 문제가 그렇다. 해당 줄을 코드에 주석으로 ★ 표시해놨다. 값을 입력받고 정렬한다. 그 값을 새로운 배열에 저장하고, dfs를 반복한다. 그러다가 M값에 도착하면 새로운 배열에 넣은 값을 출력해준다. 자세한 건 코드를 통해 확인하자!! ⊙..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 방문 체크가 전혀 필요 없었다. dfs 문제다. 그냥 M까지 들어가면 num부터 M까지 출력해주면 된다. ※TMI : 다음 단계(5탄)에서 난이도가 급 상승한다. ⊙ 문제 풀이 #include using namespace std; #define MAX 9 int N,M; int arr[MAX]; void d..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 이번에는 방문표시가 의미없다고 생각해서 방문표시는 없앴다! M까지 도착하면 1부터 다 출력하고 아닐 시, 더 깊게 들어간다! 아래 코드를 통해 확인해보자. ⊙ 문제 풀이 #include using namespace std; #define MAX 9 int N,M; int arr[MAX]; bool visit..