brunch

You can make anything
by writing

C.S.Lewis

by 코드아키택트 May 06. 2024

그래프 알고리즘

D+37

알고리즘 공부는 계속되고 있다.  6006 수업을 계속 보고 있으며, 이제 그래프 알고리즘인 9강으로 넘어왔다. 그럼 공부하면서 느낀 내용을 적어본다


AEC와 그래프 알고리즘

나는 여전히 건축에 관련된 문제를 해결하기 위해선 그래프 알고리즘을 알아야 한다고 믿고 있다. Diffusion 모델이나 CNN 모델이나(사실 비슷한 부류로 알고 있지만) 해당 모델에는 건축에서 중요하게 생각하는 관계성을 표현하지 못한다. 통계학적으로 접근하는 모델이니 마치 그렇게 보일 순 있어도 학습 레이어상에 그런 내용이 없다. 데이터셋이 생각보다 적은 건축계에선 원하는 관계성을 설정하고 무언갈 만드는 것이 가장 현실적인 대안으로 보인다. 이게 그래프가 필요한 이유라면 내가 오늘 그래프 알고리즘을 통해 배운 게 무엇인지 이야기해봐야 하는 때가 되었다


그래프는 점과 점과 연결된 점의 조합으로 표현된다

어떤 그래프를 G라고 한다면 G= V +E로 표현된다. 여기서 V는 Vertex를 뜻하고 E는 Edge를 뜻한다. 편의를 위해 각 Vertex의 Key값이 0부터 Vertex의 개수에서 하나 뺸것 (|V|-1) 사이의 하나하나에 대응된다고 가정하자. 그리고 Direct Access Array의 각 index가 vertex의 key와 같다고 하고, 해당 index에 포함된 Array는 해당 index와 인접한 Vertices(Vertex의 복수를 이렇게 쓰더라)를 뜻한다. 이렇게 말로만 하면 어려우니 그림으로 표현해 보면 다음과 같다.


위 구조에서 화살표가 그어져 있지 않은 것은 양방향으로 연결되어 있다는 뜻이다. 흔히 Undirected Graph라고 표현한다. 위 그래프를 자료구조로 표현하면 아래와 같다

[
[2,3], # 0번 vertex와 인접한 vertices
[], #1번은 동떨어져있다
[0,3], #2번.
[0,2]
]

위와 같은 구조로 표현된다. 원 강의에서 Set Data Structure 또는 Top-level Set이라는 표현도 쓰던데 정확한 의미는 좀 더 알아봐야겠다. 위 자료구조를 Adjacency List라고 한다. 한국말로는 인접관계리스트 정도로 표현할 수 있어 보인다.


6006 수업은 엄청나게 파고들어 가는 수업인데, 처음 부분을 놓치면 중간에 상당히 고생하게 된다. 그래프 단원에서 다루는 주요 문제는 최단거리 문제다. 이를 위해서 그래프의 기초부터 잘 알아둘 필요가 있다. 강의 9번의 뒷부분은 나도 아직 이해하는 중이라 추후에 좀 더 보완해야 한다.


만약 이걸 잘할 수 있다면...

건축업계에서 공공연한 비밀 중 하나는 평면 등 설계 대안을 추천해 주는 시스템을 만들고 싶어 하는 것이다. 내 짧은 법규적 이해로는 설계 대안을 만들어주는 AI는 건축사법 위반이지만, 건축사에게 설계 대안을 추천해 주는 AI는 위법이 아니다. 따라서, 대형 건축사무소들은 자신들의 내부 생산성 향상 및 홍보적 차원에서 건축 설계 대안 AI를 만들고 싶어 한다. 하지만 디자인을 전공한 사람들에게 공학의 영역인 AI는 쉽지 않은 부분이다. 특히, Graph를 다루는 AI는 GNN이라고 하며, 난이도가 꽤나 있는 분야다. 실제로 이를 통해 제대로 된 연구 결과를 내놓은 것은 Autodesk Research 팀과 일본 오바야시 건설사가 내놓은 Building GAN 하나 일 정도다. 나도 아직 먼 길이지만 차근차근 쌓아서 좋은 결과를 만들 수 있길 바랄 뿐이다.

이전 07화 중간점검 겸 감사의 글
brunch book
$magazine.title

현재 글은 이 브런치북에
소속되어 있습니다.

작품 선택

키워드 선택 0 / 3 0

댓글여부

afliean
브런치는 최신 브라우저에 최적화 되어있습니다. IE chrome safari