본문 바로가기
728x90

전체 글205

[BOJ/백준] 11723 집합 ● [문제번호 11723] 집합 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net ● 알아야 할 것 : NULL ● 풀이 과정 : 문제에서 주어진 내용에 따라 간단하게 구현가능하다. ● 주의 할 것 : 숫자 입력 후 문자열 입력받을 때 공백있는 문자열이 있는 경우, ws 또는 cin.ignore()를 이용해야한다. 하지만 아래 코드에서는 공백없는 문자열을 입력받았으므로 상관없다. ● 참고 할 것 : 숫자 입력 후 공백있는 문자열 입력시 주의사항 https://pirateturtle.. 2021. 9. 9.
[BOJ/백준] 1248 맞춰봐 ● [문제번호 1248] 맞춰봐 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문 www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : DFS의 기본 구현 형태에서 벗어나지 않지만, 주의하고 확인할 조건들을 잘 구현한다. : -10부터 10까지 순서대로 각 열의 모든 행의 부호 조건에 만족하는 숫자를 찾으면 다음 열로 넘어간다. ● 주의 할 것 : 부호 확인 방법을 구현할 때 어떤 순서로 구해지는 지 이해해야한다. ● 참고 할 것 .. 2021. 9. 9.
[BOJ/백준] 2529 부등호 ● [문제번호 2529] 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 : vector 자료구조와 메소드 ● 풀이 과정 : DFS의 기본 구현 형태에서 크게 벗어나지 않는다. : 맨 앞자리의 숫자는 그대로 저장하고 다음 숫자부터 부등호 조건에 맞는 숫자들을 저장한다. 그리고 부등호는 K개이므로 숫자는 K+1 개 인 경우, 최대 숫자인지, 최소숫자인지 확인 후 저장 여부를 결정한다. ● 주의 할 것.. 2021. 9. 9.
[BOJ/백준] 15661 링크와 스타트 ● [문제번호 15661] 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : 스타트와 링크 문제에서 팀인원 조건을 수정하면 된다. : bool로 이루어진 team이라는 1차원 배열을 만들어 각 사람(index)이 스타트 팀(true)인지 링크 팀(false)인지를 구분한다. : 팀의 능력치를 구할 때는 team 배열에서 해당 팀원(r.. 2021. 9. 9.
[BOJ/백준] 14889 스타트와 링크 ● [문제번호 14889] 스타트와 링크 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 ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : DFS의 기본 구현 형식에서 크게 벗어나지 않지만, {N/2 명 까지 선택} + {조합} 을 고려하여 구현하면 된다. : bool로 이루어진 team이라는 1차원 배열을 만들어 각 사람(index)이 스타트 팀(true)인지 링크 팀(false)인지를 구분한다. : 팀의 능력치를 구할 때는 team 배열에서 해당 팀원(ro.. 2021. 9. 9.
[BOJ/백준] 14501 퇴사 ● [문제번호 14501] 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : DFS의 구현형태에서 크게 벗어나지 않지만, 상담을 연속되지 않게 진행하는 경우들을 고려해야한다. : {현재} + {다음 상담까지 빈 공간} + {다음 상담 소요기간} ≤ 퇴사일 이라는 조건을 잘 고려해서 구현했다. : Base Case는 어떻게 구현할 지 고민하였으나 '항상 퇴사전날까지 일하는 것이 최대 상담료인 건 아니다' 이므로 매 재귀마다 확인하게 만들고, Base Case는 만들지 않았다. ● 주의 할 것 : 각 배열들의 index를 주의.. 2021. 9. 9.
728x90

티스토리툴바