공부하자

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 정리 팀의 능력치 : 팀에 속한 모든 쌍의 능력치 Sij의 합 = Sij + Sji 두 팀의 능력치 차이의 최솟값을 구하기 생각 모든 경우의 수를 구해야 하긴 하는데… 1. 팀 구성 방식 - 중복이 허용되지 않으니까 순열로 구해야 하긴 함! 한 팀에 속하면 visited로 방문 표시를 하면서 방문한 팀이 n/2될 때 까지 방문하고! 이런 식 2. 팀의 능력치 비교 - 표에서 그대로 가져오는데 두 팀의 능력치 차를..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 정리 주어진 도시 정보에서 M개의 치킨집만 남기는데 치킨집과 집 사이의 총 거리가 가장 적게 되도록 M개를 골라서 도시의 치킨 거리의 최솟값을 구하면 됨! (각 집과 치킨집 사이의 거리의 총 합이 최소가 되는) 생각 브루트포스로 모든 M개를 골랐을 때마다 거리를 다 구해놓고 그 중 min을 구함! 근데 M개를 고르는 로직은 어떻게 하지? 모든 경우의 수를 구한다고 하면 ..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 알고리즘 스터디 하는 친구가 가져온 문제가 백트래킹 문제들인데 브루트 포스 개념조차 기억이 안 나서... ㅠㅠ 개념 리마인드 겸 브루트 포스 문제의 대명사인 블랙잭 문제를 다시 풀어보고자 한다 브루트 포스의 종류 순차 탐색 - 선형 구조를 순차적으로 탐색 DFS(깊이 우선 탐색) - 비선형구조를 점점 더 깊게 깊이를 우선적으로 탐색하는 방법 BFS(너비 우선 탐색)..

https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 보자마자 생각난 것 : color graph! 알고리즘 수업 열심히 들은 보람이 있다고 생각했다 ㅋㅋㅋ 교수님 보고 계십니까?!! 앞으로 엘베에서 마주치면 90도로 인사박겠습니다!!! 하하 암튼 나한테 휴학은 없으니까 내년 그니까 3학년 1학기 시험기간이 돌아올 때 까지 1일 1백준 다시 레츄고 애들아 열심히 하자... 생각 행운의 문자열인지 확인하는 방법 (Find 함수로 따로 만들자!) 1. 인접한..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net + C++의 next_permutation 함수를 사용하면 더 쉽게 풀 수 있다! 하지만 난 안 썼음 생각 1. 계산하고 비교하면서 큰 것만 남긴다! 근데 진짜 어떻게 해야할지 모르겠어 배열의 크기 제한이 8까지니까!! 작으니까 뭔가 하면 될 것 같아 코드 초안 int N, ans; int arr[9]; int result(){ // 일케 계산하는 함수를 따로 만들고! int result = 0; for(int..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 나 난독 있나봐... 생각 숫자가 들어가는 경우 / 안들어가는 경우로 나눠 dfs를 돌리자 1. sum += arr[1]; 2. sum = sum; 코드 초안 약간 이런 느낌 void dfs(int k, int sum){ for(int i=0 ; i main에서 S가 0일때만 공집합을 하나 빼주자~ 2. if 처리를 어떻게 해야할지 모르겠음!!! -> 그냥 fo..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 코드 #include using namespace std; int N, M; int arr[9]; bool visited[9]; void dfs(int k){ if (k == M){ for (int i = 0; i M; dfs(0); } visited 배열은 0부터 시작해도 상관 없는데 arr에 저장할 땐 +1을 해줘서 1부터 N까지 자연수 중에서 중복 없이..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 퀸이 서로 공격할 수 없게 놓는 방법 : 같은 행 / 같은 열 / 같은 대각선 상에 위치하지 않아야 한다. (최지웅 교수님한테 배운 ㅎ) 생각 1. 백트래킹 문제니까 되추적 알고리즘을 쓴다 1.1. 상태 조건 트리를 어떻게 구성할 것인가? -> 트리까지 그릴 필요는 없는 문제인듯 아닌가 하하 1.2. promising 조건을 뭘로 할 것인가? -> 행 / 열 / 대각선이 겹치는지 확인하기 1차원 배열을 써도 되는..