들어가는 말 알고리즘 문제 풀이, 백준 2623번 '음악 프로그램' 문제입니다. 문제 전체 가수의 숫자 N, 보조 PD의 숫자 M이 주어진다. 이후 M개의 가수 출연 순서가 배열로 주어지며, 이 때 각 배열의 첫번째 원소는 해당 순서에 있는 가수의 숫자다. 이 순서들을 모두 조합해 전체 가수들의 출연 순서를 정해야 한다. 이 때 출연 순서를 정할 수 있으면 정답을 출력하며, 답이 여럿일 경우 그 중 아무거나 출력한다. 만약 출연 순서를 정할 수 없다면 0을 출력한다. 풀이'음악 프로그램' 문제는 가수의 번호를 그래프 관계로 묶을 수 있고, 출연 순서라는 A가수가 B가수보다 앞에 와야 한다는 조건들이 주어진다. 따라서 '순서가 있는 작업', '그래프 특성을 지닐 수 있음', '선행(순서) 관계가 명확함..

들어가는 말 알고리즘 문제 풀이, 백준 2473번 '세 용액' 문제입니다. 비슷한 유형의 문제로 2467 '용액' 문제가 있으므로 먼저 풀고 이 문제에 도전하시는 것을 추천드립니다. 문제 N개의 정수를 원소로 가진 정렬되지 않은 1차원 배열 A가 주어졌을 때, A에서 임의의 원소 3개를 선택해 더하여 0에 가장 가까운 값을 얻어 이 때의 원소를 정렬하여 출력하는 문제다. 풀이1차원 배열로 값이 주어졌고, 임의의 원소들을 선택해 계산을 수행하여 특정 값을 얻는 문제다. 이 경우 '두 포인터' 알고리즘을 사용하면 좋다. '두 포인터' 알고리즘은 배열을 정렬한 후 조건에 따라 시작과 끝 부분부터 인덱스를 바꿔가며 계산을 수행한다. 자세한 내용은 '용액'문제에 대한 풀이를 참고하자(https://jingluv..

# 두 포인터 문제# 용액의 수n = int(input())# 용액의 특성값solutions = list(map(int, input().split()))# 가장 0에 가까운 값을 저장할 변수mn_solution = float('inf')# 0에 가까운 값의 인덱스가 저장될 변수들cur_left, cur_right = 0, n-1# 시작 인덱스 left, 끝 인덱스 right부터 원소 탐색을 위한 값left, right = 0, n-1# left가 right를 넘지 않으면 반복while left abs(new_solution): # 최적해가 바뀌었을 경우 해당 인덱스 값들을 별도로 저장. mn_solution = abs(new_solution) ..

들어가는 말 알고리즘 문제 풀이, 백준 2252번 '줄 세우기' 문제입니다. 문제 N 명의 학생을 키 순서대로 정렬하는 문제다. 학생 A와 B가 주어졌을 때, A는 반드시 B의 앞에 위치하여야 하며 번호는 1부터 N까지 존재한다. 총 M회 비교하며, 정답이 여러 개인 경우 아무거나 출력해도 된다. 풀이우선, 문제에서 'N명의 학생을 키 순서대로 줄을 세우려 한다' 하였다. 이는 일렬로 정렬한다는 말과 동일하다. 또한 A는 항상 B의 앞에 존재해야 하므로 반대의 경우는 존재할 수 없다. 즉, 방향성이 존재한다. 숫자들이 선형으로 연결되어 정렬되어야 하며, 방향성이 존재한다...? 아, 이 문제는 '위상 정렬'로 풀 수 있겠구나! 각 학생마다 작업 순서(차수, degree)를 지정한 다음, 작업 순서에 따..

들어가는 말 알고리즘 문제 풀이, 백준 2143번 '두 배열의 합' 문제입니다. 문제 배열 A, B가 주어졌을 때, 각 배열에서 연속적인 원소를 부분집합으로 하는 부배열들을 구하여 그 합이 T가 되는 경우의 수를 찾는 문제다. 각 배열의 길이는 N, M이며, 두 배열 모두에서 부배열을 선택하여 합을 구하여야 한다. 풀이 두 배열 A, B가 주어졌을 때 각 부배열로 가능한 경우의 수를 그려보면 위와 같은 흐름으로 전개된다. A 부배열의 합과 B의 부배열의 합을 각각 비교해가며 T를 만족시키는 경우를 세어야 한다. 하지만 위와 같이 일일이 모든 경우의 수를 세는 것은 비효율적이다. 따라서 다른 방법을 생각해야 한다. 위와 같이 부배열의 길이가 degree일 때 부배열의 합을 구해보자. 각 부배열의 합을 ..

들어가는 말 안녕하세요, jingluv입니다.오늘은 SSAFY 11기 공통프로젝트를 하며 느낀 후기를 나누려 합니다.다소 두서없고 영양가 없을 수 있지만, SSAFY를 준비하는 분들이 SSAFY 교육생이 2학기에 어떤 프로젝트를 수행하는지 알 수 있는 기회가 되길 바라겠습니다.     프로젝트 개요 제가 진행한 프로젝트 이름은 "STEACH"입니다. "Study & Teach"의 줄임말로, 가정형편이 어려운 취약계층에 속한 학생들이 실시간으로 무료 과외를 받을 수 있는 웹 애플리케이션을 개발하였습니다.    프로젝트 기획 배경 코로나 시대를 거치며, 사교육에 대한 열망이 커졌습니다. 사교육비의 증가는 가정 형편이 어려울수록 더 큰 부담으로 다가옵니다. 또한, 코로나가 본격적으로 유행하기 직전인 19년도와..