코딩성장스토리

그래프 용어정리 정점(node,vertex) 간선(edge) - 정점간의 관계 경로 .정점 a에서 b로가는 경로 사이클- 시작과 도착이 같은 곳(정점 a에서 다시 a로 돌아오는 경로 단순 경로/단순 사이클 1.경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클 2.특별한 말이 없으면 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말함 방향 있는 그래프 a → b 이면 b→a 는 없다. 방향 없는 그래프(양방향 그래프) a - b 두 정점사이의 방향이 없다. a → b , b→a 두개를 다 나타난다. 루프 간선의 양 끝 점이 같은 경우 a → a 가중치 간선에 가중치가 있는 경우 ex) a에서 b로 이동하는 거리, 이동하는데 필요한 시간 등등 ... 차수 정점과 연결되어 있는 간선..

https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 이 문제의 포인트는 버블 소트의 특징을 파악 하는 것이다. 첫번 째로 버블소트는 마지막부터 천천히 채워가는 형식이다. 그리고 뒤에 있던 값이 정렬된 배열의 위치로 가기 위해서는 항상 한칸씩 앞으로 이동하는 것이다. 즉 여기서말하는 몇 단계를 구하기 위해서는 한칸씩 앞으로 가서 본래 위치로 돌아가기 까지의 최대값을 구하면 되는 문제이다. 예를 들어 10 1 5 2 3 이 주어..

1.나머지 연산 (a+b)%c=((a%c)+(b%c))%c (a*b)%c=((a%c)*(b%c))%c (a-b)%c=((a%c)-(b%c)+c)%c → 뺼셈의 경우 음수가 될 수 있기에 +c를 해줘야한다. 나누기 연산은 불가능 증명) a=q1c+r1 a+b=(q1+q2)c+(r1+r2) → (a+b)%c =(r1+r2)%c b=q2c+r2 a%c=r1 b%c=r2 →a%c+b%c =r1+r2 이고 여기서 c를 나누면 (r1+r2)%c 이다 2.최대공약수(GCD) 유클리드 호제법 a를 b로 나눈 나머지를 r일떄 GCD(a,b)=GCD(b,r) 이다 재귀함수를 이용한 유클리드 호제법 int gcd(int a,int b){ if(b==0){ return 0; }else{ return gcd(b,a%b); } ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 이번 문제의 조건 이다 다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개서 만드는 것이고, 이 문제 또한 사용한다. 첫번째 조건 중에 한 계..