반응형 분류 전체보기124 백준 2056. 작업 🅰 백준 2056. 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net ✏️ 문제 풀이 순서가 주어지므로 위상정렬의 개념을 이용하여서 풀었다. 일단 위상정렬이랑 비슷하지만 선행관계가 없는 작업들은 동시에 수행되기 때문에 이 부분을 생각해내는데 시간이 조금 걸렸다. pq에 저장되는 정점들은 comparable을 이용하여 수행시간이 작은 순으로 정렬을 시켜서 하나씩 뽑아낸다. pq에는 들어오는 간선이 없는 정점부터 저장을 해서 탐색을 시작한다. cur = pq.poll() 한 정점이 걸리는 시간을 an.. 2021. 9. 29. SW Expert Academy [Professional] 키 순서 / 백준 2458 키 순서 🅰 SW Expert Academy [Professional] 키 순서 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net ✏️ 문제 풀이 백준의 키 순서 문제와 동일한 문제이다. 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성해야 한다. 그래프 형식으로 주어지기 때문에 플로이드-와샬을.. 2021. 9. 29. 백준 1766. 문제집 🅰 백준 1766. 문제집 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ✏️ 문제 풀이 백준 2252 줄 세우기 문제랑 99% 동일한 문제이다. 다른점이란 가능하면 쉬운 문제를 먼저 풀어야 한다는 조건이 하나 더 생겼을 뿐이다. 이를 해결하기 위해서는 queue대신 PriorityQueue를 사용하여 들어오는 정점들을 오름차순으로 저장해서 순서대로 탐색하면 된다는 점이다. 아래에는 2252 줄 세우기 문제랑 해설이 동일하다. 위상정렬이란 그래프의 개념과 큐를 이용하여 푸는 것.. 2021. 9. 28. 백준 2252. 줄 세우기 🅰 백준 2252. 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ✏️ 문제 풀이 위상정렬의 개념을 이용해서 풀면 쉽게 풀리는 문제이다. 위상정렬이란 그래프의 개념과 큐를 이용하여 푸는 것으로, 어떤 일을 하는 순서를 찾는 알고리즘이다. 중요한 것은 큐에 넣을 때 연결된 간선이 하나밖에 없는 정점만 넣어줘야 한다는 것이다. 먼저 인접리스트, 큐, 연결된 간선 수를 체크해줄 check배열을 선언하였다. 먼저 그래프를 생성하기 위해 인접리스트를 생성해주고, .. 2021. 9. 28. [Graph] 위상정렬 - 위상정렬 어떤 일을 하는 순서를 찾는 알고리즘으로, 큐에 들어있는것들은 간선의 개수가 0개인 것이고, 큐에서 빼서 체크할 때에도 들어오는 간선의 개수가 0인 것을 넣는다. - 기본적으로 필요한 변수 PriorityQueue or Queue : 정점들을 저장하기 위한 자료구조 connect[] : i에 연결된 간선들의 수를 저장하기 위한 배열 ArrayList : 각 정점이 가리키는 노드를 저장하기 위한 인접리스트 - 문제푸는 팁(오로지 내 생각) 보통 어떤일의 순서를 출력하시오, 두 정점에 대한 선행관계, 우선순위가 주어진다. - 관련된 문제 해설 백준 1766. 문제집 🅰 백준 1766. 문제집 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 .. 2021. 9. 28. CT(기본 수열과 특성방정식) - 등차수열 수열의 차이가 일정한 것 점화식 : f(n) = f(n-1) + d Sn = n(a1+an) / 2 - 등비수열 점화식 : f(n) = f(n-1) * r(일정비율) Sn = an = a1*r^(n-1) - 특성방정식 왜 사용하나? 점화식을 일반식으로 유도할 때 점화식에 특성방정식을 이용하면 일반항을 구할 수 있다. 유형 3번일 때 (P!=1 && Q!=0) - 만약 P=1이면 An+1 = An + q(등차수열이 됨) - 만약 Q=0이면 An+1 = P*an(등비수열이 됨) An+1-d = PAn + Q-d 식을 풀다보면 공통적인 부분들이 있다. 그 부분들을 같은 식으로 치환하면 등차or등비 수열의 형태가 된다. 2021. 9. 28. CT(수의 표현, 유클리드 호제, 페르마의 소정리) - 수의 표현 1의 배수 2의 배수 : 짝수 3의 배수 4의 배수 5의 배수 : 2.5를 이용한 소인수 분해 6의 배수 : 어떤 수든 연속적으로 3번 곱하면 6의 배수가 됨 / (a-1)a(a+1) 7의 배수 : 요일(기준요일 + 경과일), 달력, 13일의 금요일 8의 배수 : 홀수의 제곱 % 8 = 1이 나오는 수(정수의 특징) - 유클리드 호제 (큰 수나 어려운 숫자에 대한 GCD를 쉽게 구하는 방법) 1. 큰수를 작은수로 나누어 떨어지지 않기 때문에 큰수를 작은수로 나누어 나머지를 구한다. 2. 작은수를 나머지로 나누어 나머지를 구한다. 3. 2번을 계속 반복적으로 수행 ==> 나머지가 0이 나올때 까지 ==> 나머지가 0이 될때는 제수가 GCD(최대공약수)이다. ex) (120,150) -> 15.. 2021. 9. 27. 백준 5557. 1학년 🅰 백준 5557. 1학년 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net ✏️ 문제 풀이 2차원 배열을 이용해서 각 수식을 순서대로 +, - 해서 dp[][] index에 저장한다. 행은 각 수식의 수만큼 만들고 계산되는 수식은 0~20 사이에 있기 때문에 열은 0~20으로 생성한다. dp[N+1][21] 계산해서 나오는 값들은 index로 표현할 수 있기 때문에 각 숫자마다 +연산을 한 값이 20보다 작거나 같으면 dp[i][j+number[i]] += dp[i-1][j], -연산을 한 값이 0보다.. 2021. 9. 27. 백준 1495. 기타리스트 🅰 백준 1495. 기타리스트 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net ✏️ 문제 풀이 기타리스트 문제에서는 행을 각 곡의 개수, 열을 0~M(최대 볼륨)으로 설정한 다음 dp를 수행한다 점화식은 D[i][j] = D[i+1][j+V[i+1]] = 1, D[i+1][j-V[i+1]] = 1이 될 수 있다. i+1에 데이터를 저장할 때 0~M사이에 있으면 dp에 저장을 하면서 마지막 곡까지 반복수행한다. 마지막 곡의 볼륨조절이 끝난 후 그 행에 있는 볼륨 중 최대값을.. 2021. 9. 27. 이전 1 ··· 3 4 5 6 7 8 9 ··· 14 다음
