반응형 분류 전체보기123 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. 백준 12920. 평범한 배낭 2 🅰 백준 12920. 평범한 배낭 2 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net ✏️ 문제 풀이 평범한 배낭문제와 비슷하지만 다른점은 "한 물건을 두개 이상 챙기는 것도 가능하다." 이 부분이다. 처음 이 부분을 해결하기 위해 물건이 2개이상 있는 경우에는 for문을 이용하여 2개,3개,4개...k개 만큼을 넣었을 때의 가치를 비교하여 최적의 가치를 찾아서 제출했다 하지만 6%때 시간초과가 떠서 최악의 경우를 생각해보니 가방의 무게가 10,000이고 100개의 물품.. 2021. 9. 27. 이전 1 ··· 3 4 5 6 7 8 9 ··· 14 다음
