Algorithm/Baekjoon
0304_백준 1260번 : DFS와 BFS (개념 알고 익숙해지기)
*출처 : 백준 1260번 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net # DFS와 BFS 코드 1차 풀이 : 다른 사람들의 풀이와 비교했을 때 시간이 더 오래 걸린다는 것을 파악. 시간 단축 필요. - 맨 처음 DFS를 풀었을 때는 노드와 엣지를 표현할 때 2차원 배열을 사용했는데, 이게 정답은 나왔는데 시간 초과가 떴던 ..
0302_백준 15656~15666번 : N과M문제 (재귀함수로 순열, 조합 구하기)part2
출처 : 백준 15656번 문제~ https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 어제에 이어 오늘 재귀함수로 구하는 순열, 조합 N과M 문제를 마무리 ..! 어제보다 난이도가 살짝 높았지만.. 주변 블로거님들 참고하며 극복ㅎㅎ 이전 문제들은 비슷한 맥락이지만, N과M 문제 9번부터 N개의 자연수 중 중복되는 숫자가 있어 이를 처리해줘야 하는 부분에서 조금 헤맸다. 해결방법은 overlap 이라는 새로운 변수를 만들어 만든 부분집합의..
0301_3월 첫 날/백준 15649 ~ 15655번 : N과M문제 (재귀함수로 순열, 조합 구하기)
# 출처 : 백준 N과M 문제 https://www.acmicpc.net/workbook/view/2052 문제집: N과 M (baekjoon) www.acmicpc.net 그 동안 순열과 조합을 itertools 외장 라이브러리를 사용하여 순열과 조합을 만들어 왔으나, 재귀함수를 이용해 풀어보는 연습이 꼭 필요하다는 피드백을 받아서 이를 연습하고자 백준 N과 M문제를 풀기 시작했다. 오늘은 6문제 정리하였고, 내일 6문제 추가로 풀 예정이다. 아직 함수를 쓰는 것도, 재귀 개념을 활용하는 것도 서툴지만 여러 차례 반복하여 문제를 풀다 보니 차츰 개념이 정리되는 느낌이다. [풀이 과정 정리] 중복 가능 : 순열 P 함수 중복 불가능 : 조합 C 함수 * 고려해야 할 요소 : 구한 수열들의 중복이 가능 유..
0225_백준 14889번 : 스타트와 링크_Combination 조합 활용
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 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속..