분류 전체보기
[이코테] Chapter10-2 / 팀 결성
[이코테] Chapter10-2 / 팀 결성
2023.02.21팀 결성 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어 N + 1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. '팀 합치기' 연산은 두 팀을 합치는 연산이다. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1
[이코테] Chapter10-1 / 다양한 그래프 알고리즘
[이코테] Chapter10-1 / 다양한 그래프 알고리즘
2023.02.20이미 배운 내용을 훑어보자 지금까지 코딩 테스트에서 출제 비중이 높은 알고리즘 유형들을 다루어보았다. 이번 장에서는 지금까지 다루지 않았던 그래프 알고리즘을 추가로 다룰 것이다. 이전 5장 'DFS/BFS'와 9장 '최단 경로'에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 이외에도 그래프 알고리즘은 굉장히 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘이다. 여기서 다루는 개념들을 바르게 이해할 수 있다면 코딩 테스트에서 만나게 될 다양한 응용문제들도 해결할 수 있을 것이다. 10장에서 다룰 알고리즘은 앞서 배운 내용에 기반하는데, 예를 들어 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘..
[백준] 2565번 전깃줄(feat. 다이나믹 프로그래밍, LIS)
[백준] 2565번 전깃줄(feat. 다이나믹 프로그래밍, LIS)
2023.02.04https://www.acmicpc.net/problem/2565 문제 접근 첫 번째 단계(문제 요약 및 조건 파악 하기) 입력으로 첫번쨰 줄에 n이 주어지고, 두번째 줄부터 n + 1 번째 줄 까지 각각 A to B가 주어진다. (전깃줄의 연결 정보) 이 그림에 대한 입력은 아래와 같다. 8 1 8 3 9 2 2 4 1 6 4 10 10 9 7 7 6 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다. 두 번째 단계(문제 핵심 파악 하기) 모든 전깃줄을 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력해야 한다. 전깃줄이 서로 교차하지 않기 위해서는, 1번에서 출발한 전깃줄의 도착지점은 그 이후의 번호에서 출발한 전깃줄의 도착지점들보다 낮은 ..
[백준] 17216번 가장 큰 감소 부분 수열(feat. 다이나믹 프로그래밍, LDS)
[백준] 17216번 가장 큰 감소 부분 수열(feat. 다이나믹 프로그래밍, LDS)
2023.02.02https://www.acmicpc.net/problem/17216 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 가장 큰 감소 부분 수열의 요소 합을 구하는 문제이다. 예를 들어 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 가장 합이 큰 감소 부분 수열은 A = {100, 60, 8, 7, 6, 5} 이다. 입력으로는 수열의 크기 N (1
[백준] 11054번 가장 긴 바이토닉 부분 수열(feat. 다이나믹 프로그래밍, LIS, LDS)
[백준] 11054번 가장 긴 바이토닉 부분 수열(feat. 다이나믹 프로그래밍, LIS, LDS)
2023.02.02https://www.acmicpc.net/problem/11054 첫 번째 단계(문제 요약 및 조건 파악하기) 문제에서 말하는 바이토닉 수열에 대해서 간단하게 정리하면, 어떤 특정 수 X를 기준으로 왼쪽은 X보다 작은 LIS, 오른쪽은 X보다 작은 LDS 인 수열이다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 입력 조건으로는, 수열의 크기 N은 1 arr[j] and dp_left[i] < dp_left[j]: dp_left[i] = dp_left[j] dp_left[i] = dp_..
[백준] 11053번 가장 긴 증가하는 부분 수열(feat. 다이나믹 프로그래밍, LIS)
[백준] 11053번 가장 긴 증가하는 부분 수열(feat. 다이나믹 프로그래밍, LIS)
2023.02.01https://www.acmicpc.net/problem/11053 문제 접근 첫 번째 단계(문제 요약 및 조건 파악) 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제이다. 입력 조건은 수열의 크기 N은 1 arr[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] = dp[i] + 1 print(max(dp)) DP문제는 DP테이블을 어떻게 정의하느냐가 관건.