1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net 2. 해결 IDEA Union-Find 알고리즘 (초기상태) Parent Index 1 2 3 4 5 6 7 8 9 Node Index 1 2 3 4 5 6 7 8 9 바이러스 근원 노드가 '1'이므로 1과 같은 Group으로 Union 되는 노드의 Parent Index가 '1'이 되..
Algorithm
김성렬 교수님의 알고리즘 수업 리뷰 + 알고리즘 문제풀이
0. 소인수분해 정의임의의 자연수 N을 마지막 나머지가 '1'이 나올 때 까지 '소수'로 나누어 곱으로 표현한 것. EX)120이란 수를 소인수분해 한다면? N이란 숫자를 몫 i로 나누어 떨어지는지 검사하고 나누어 떨어지면 떨어지는 동안 계속 나누기/ 나누어 떨어지지 않으면 i + 1 N의 나머지가 1이될 때까지 (그림에서는 5에서 멈춤) 1. 문제https://www.acmicpc.net/problem/1165311653번: 소인수분해첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.www.acmicpc.net2. 핵심 IDEAQ. i(몫)의 범위?저번 포스팅에서 소수를 검사하는 아이디어에서 '에라토스테네스의 Idea'에서 살펴 보았듯이임의의 자연수 N이 제곱근 이하에서 소수로 나누어..
1. 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 2. 핵심 아이디어 DFS는 재귀 (Stack) BFS는 Queue가 비어있을 때 까지. 3. 실수 (1) Node별 연결상태를 저장한 vector Array List를 오름차순으로 출력해주기 위해서 sort 필요 (2) Array Index가 0부터인지 1부터 시작인지 체크..
1. 소수란? 1과 자기 자신이외 어떠한 약수도 가지지 않는 자연수 2부터 N/2 까지 나누어 떨어지는 수가 없으면 N은 소수이다. p : 몫 q: 나머지 N = ap + q (0
🔒 문제 [기초-2차원배열] 성실한 개미 C언어기초100제v1.2 : @컴퓨터과학사랑, 전국 정보(컴퓨터)교사 커뮤니티/연구회 - 학교 정보(컴퓨터)선생님들과 함께 수업/방과후학습/동아리활동 등을 통해 재미있게 배워보세요. - 모든 내용 및 이미지들은 저작자와의 협의 없이 무단으로 사용할 수 없습니다. codeup.kr 이정도 난이도 문제는 별도의 함수 정의가 필요하지 않아서 설계 문서와 Flow chart를 생략한다. 🔑 Key Idea 이동의 우선순위가 →↓ 이다. 따라서 2차원 배열을 늘여놓았을 때 ⚠️ 주의! 배열을 이용한 문제에서 항상 주의해야 할 것은 인덱스 범위이다. 반복문 조건식에 index 범위를 제한해 주는것이 필수! (∵ 범위내 목적지를 찾지못하면 끝을 넘어가게 됨) 인덱스 번호가 0..
이전 포스팅! https://m-falcon.tistory.com/84 피보나치 수열 0. 문제 코드업 1855 피보나치 수열 https://codeup.kr/problem.php?id=1855 [기초-재귀함수] 재귀로 n번째 피보나치 수 리턴하기 *주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지.. m-falcon.tistory.com [Memoization 정의] 재귀호출상 반복되는 결과를 메모리에 저장해서 같은 결과를 중복하여 이용하는 횟수를 줄임으로써 성능 향상을 기대하는 코딩 기법. 지난번 포스팅에서는 재귀함수를 통한 피보나치를 구현했다. n번째 피보나치 수열 값을 구하는 프로그램을 Memoization, Dynamic Programming 기법으로 구현해보자. 1..
