원당컴퓨터학원

SCC(Strongly Connected Components) 란 SCC 알고리즘은 방향 그래프에서 그래프의 모든 정점들 간에 양방향으로 경로가 존재하면 강하게 연결 되었다고 하는데 이렇게 연결된 부분그래프를 찾는 알고리즘이다. 위의 그래프에서 a,b,e / f,g / c,d,h 와 같이 3개의 그룹을 찾는 알고리즘 SCC가 되기 위한 조건 1. 같은 SCC 내의 임의의 두정점 A,B 사이의 경로가 항상 존재한다. 2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다.(SCC끼리는 사이클이 존재하지 않는다.) SCC 알고리즘 - 코세라주 알고리즘 1978년 코사라주가ㅏ 설명하고 1981년 미샤 샤리르가 출판. 두번의 깊이 ..

1. 다음의 도형에서 몇개의 선분이 있는지 세어 보세요.(숫자만 입력하세요.) 문제풀이 더보기 각 점의 위치에 1,2,3,4,5 의 번호를 붙여 줍니다. 1번에서 그릴수 있는 선분은 (1,2)(1,3)(1,4)(1,5) 4개입니다. 2번에서 그릴수 있는 선분은 (2,3)(2,4)(2,5) 3개 입니다. 3번에서 그릴수 있는 선분은(3,4)(3,5) 2개입니다. 4번에서 그릴 수 있는 선분은(4,5) 1개입니다. 따라서 1+2+3+4 = 10개입니다. 2. 아래 그림에서 각이 모두 몇개 있습니까? 문제풀이 더보기 각 점의 위치에 1,2,3,4,5 의 번호를 이용하면 1번에서 그릴수 있는 각은 (1,2)(1,3)(1,4)(1,5) 4개입니다. 2번에서 그릴수 있는 각은 (2,3)(2,4)(2,5) 3개 입니..

원당이는 한빛도서에서 책을 하나 구매했는데 홈페이지에 ISBN 코드를 인증 받으면 포인트를 준다고 합니다. 그런데 어린 동생이 ISBN의 가장 마지막 자리를 사인펜으로 낙서를 해 놓는 것 때문에 ISBN 코드로 인증을 받지 못하게 되었는데 인터넷으로 ISBN 에 대해 검색을 하니 ISBN 에 대해 다음과 같이 설명이 되어 있습니다. ISBN(International Standard Book Number)는 국제적으로 책에 붙이는 고유한 식별자이다. ISBN체계는 원래 1966년 영국에서 "표준 도서 번호"(SBN)라는 이름으로 만들어졌고, 1970년 국제 표준화 기구에 의해 ISO 2108이라는 표준으로 채택되었다. 본래 ISBN은 10자리였지만 2007년 1월 1일 이후부터는 유럽상품번호(EAN)에 맞..

미분의 기초 미분이란 "순간의 변화율"을 구하는 것 입니다. 여기서 변화율이 무엇인지 살펴 봅니다. 원당이가 집에서 8시에 출발해서 2km 떨어진 회사까지 걸어가서 도착하니 10시가 되었다. 그렇다면 속도는 거리/시간 이므로 1km/h 가 된다. 이때 위치의 변화 = 변화후의 위치 - 변화 전의 위치가 되고 시간의 변화 = 변화후의 시간 - 변화전의 시간 이 되며 속도는 위치의변화/시간의변화 로 정의 할 수 있습니다. 하지만 이것은 평균속도이며 원당이가 회사까지 걸어가는 동안 횡단보도에서 대기할때도 있고 오르막길에서 천천히 걷는 경우도 있고 내리막길에서 빨리 걸어 가는 경우도 있을것입니다. 즉 위의 속도는 평균 변화율이며 평균변화율은 위치의변화/시간의 변화 = Δy/Δx = f(b)-f(a)/b-a 와 ..

거리,속도,시간 및 그들 사이의 관계를 연구하는 문제를 모두 거리에 관한 문제라고 합니다. 거리와 속도 관련해서는 여러분은 아빠가 시속 120km 로 운전을 하고 갈때 2시간 후에 가는 거리는 240km 라는 것을 알고 있는 것처럼 거리 = 속도(120/1시간) * 시간(2시간) 을 잘 알고 있습니다. 여기서는 이렇게 알고 있는 속도와 거리 문제를 풀어 보는 방법에 대해 알아 보겠습니다. 1. A,B 두사람은 각각 서로 30km 떨어져 있는 두 지점에서 동시에 출발하여 서로 마주보고 걸어 오는데 A는 6km/h로 걷고 B는 4km/h 로 걷습니다. 두 사람은 몇시간이 지나면 서로 만납니까?(숫자만 입력하세요.) 문제풀이) 더보기 처음 30km 떨어져 있는데 두사람은 1시간에 10km 씩 좁혀져 옵니다. ..

원당이는 생명공학의 DNA 에 대해 연구 하고 있습니다. DNA의 염기서열은 adenine(A),thymine(T),guanine(G),cytosine(C) 와 같이 네가지로 구성되어 있습니다. 고릴라의 염기서열을 분석해 보니 GATACCAGATACCCA 와 같이 이루어져 있고 원숭이의 염기서열을 분석해 보니 AAGATTGCCATTATT 와 같이 이루어져 있는 것을 발견했습니다. 원당이는 이 두개의 염기서열에서 공통부분 서열 중에 최대로 긴 부분 서열을 구하고 싶습니다. 여기서 부분서열이란 원래 문자열에서 임의적으로 몇개의 문자를 제거하여 순서에 맞춰 빈칸 없이 합쳤을 때 만들 수 있는 문자열을 말합니다. 즉 ATGC 와 ATCT 의 가장긴 부분수열은 ATC 3개 입니다. ATGC 에서 G를 제거 하고 ..

목표 벡터가 무엇인지 살펴보고 인공지능 프로그램에서 어떻게 사용되는지 살펴 봅니다. 벡터란 벡터는 크기와 방향을 갖춘 양을 말합니다. 벡터는 공간에서 한점을 나타냅니다.(1차원 상의 점은 벡터 보다는 스칼라라고 부릅니다.) 2차원 상의 점을 (x,y)로 표현되는데 원점에서 부터 공간상의 한 점 까지의 상대적 위치를 벡터라고 이해하면 됩니다. 인공지능에서는 n차원상의 공간에서의 한 점으로 표현을 합니다.(인공지능에서는 대부분 큰 차원의 벡터를 다루게 됩니다.) 벡터에 숫자(스칼라)를 곱해주면 길이만 변합니다. 이러한 여러개의 데이터를 한 줄에 담아 낼 수 있게 만든 것을 벡터라고 합니다. 벡터는 다음과 같이 표현 합니다. 벡터의 덧셈과 뺄셈 벡터끼리 덧셈과 뺄셈은 서로 대응하는 성분끼리 덧셈 뺄셈을 합니다..

원당이가 사는 원당동 금정산에는 약수터가 있습니다. 약수터의 물은 1초에 1리터씩을 담을 수 있습니다. 원당이가 약수터에 올라가 보니 사람들이 약수통을 들고 가장 최소한의 시간을 대기해서 물을 받으려면 어떤 순서대로 받는것이 가장 좋을지 논의 하고 있었습니다. 지금 약수터에 물을 받고 싶어하는 사람은 네명이며 첫번째 사람은 3리터, 두번째 사람은 5리터, 세번째 사람은 2리터, 네번째 사람은 1리터 들이 물통을 가지고 있습니다. 이때 첫번째,두번째,세번째,네번째 순으로 물을 받는다면 대기한 시간은 첫번째 사람은 자신의 물을 받는 시간 3초 + 두번째 사람은 3초 대기후 자신의 물을 받는 시간 5초 이므로 8초 + 세번째 사람은 8초 대기후 자신의 물을 받는 시간 2초 이므로 10초 + 네번째 사람은 10..

목표 유클리드 거리를 표현하는 방법을 살펴 보고 인공지능에서 어떤 식으로 사용되는지 알아 보자. 절댓값의 기호는 |x| 로 사용되며 유클리드 거리는 ||x|| 를 사용한다. 절댓값 절댓값은 수직선 위에서 원점으로 부터 어떤 수를 나타내는 점까지의 거리 절댓값은 |x| 로 표시하며 음이 아닌 실수의 값을 갖는다. 유클리드 거리 유클리드 거리는 두 점 사이의 거리를 계산할 때 사용하는 방법 (0,0)과 (x,y)의 두 점의 거리는 피타고라스 정리에 의해서 다음과 같은 거리를 계산 할 수 있다. 거리=√(x*x + y*y)​ (x1,y1) 와 (x2,y2) 의 두 점의 거리는 다음과 같이 계산 가능하다. 거리=√( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))​ (x1,y1,z1) 와 (x2,..

LCA(Lowest Common Ancestor) 란? LCA 란 최소 공통 조상을 찾는 알고리즘 - 두 정점 u,v 에서 가장 가까운 공통조상을 찾는 과정을 말한다. LCA(Lowest Common Ancestor) 구현 방법 위의 그래프에서 LCA((4,8)=1 이 됩니다. 가장 단순한 방법은 한번에 하나씩 자신의 조상을 찾아 올라가는 방법입니다. 4의 조상은 2,8의 조상은 7,2의 조상은 1,7의 조상은 3,1의 조상은 루트이므로 대기,3의 조상은 1 에서 순차적으로 하나씩 찾아가다가 누군가가 먼저 지나간 자리에 도착하면 그곳이 공통조상이 됩니다. 하지만 이 알고리즘은 최대 O(N) 의 시간이 걸립니다. https://www.acmicpc.net/problem/11438 11438번: LCA 2 ..