그냥 하는 노트와 메모장

* BOJ 5213 - TOTEM (과외맨) [ 분류 - BFS,DFS / 기타 최단경로 알고리즘 ] 주어진 문자들을 어떻게 노드로 정의할 것이며, 어떻게 자료구조를 설정할 것인지 물어보는 문제. 단순 최단경로 알고리즘을 사용한다면 별다를 문제는 없다. 문제에서는 타일은 두 개의 숫자로 이루어진다. 두 개의 숫자는 각자 '칸'을 의미하며 최대가 6이다. 인접한 타일과 같은 숫자로 접점이 있다면 두 타일은 이어져 있다고 볼 수 있다. * 접근 방식 1. 각 타일은 2개의 칸이고, 각 칸의 최대가 6이므로 두자리 수 하나로 퉁칠 수 있다. 2. 입력으로 주어지는 순서는 맨위 좌측 타일부터 맨 아래 우측 타일까지를 주어주므로 indexing 절차가 필요함을 알 수 있다. 즉, 단순 2차원 배열로 두고 접근할 ..

* BOJ 1765 - The Gangs (닭싸움 팀 정하기, https://www.acmicpc.net/problem/1765) [ 분류 - BFS, DFS/ DSU/ Hashing ] 이분 그래프가 여러개 생길 수 있는 구조를 생각하자. 조건에 따르면 특정 Component A에 대해 A의 적은 단 하나 밖에 존재하지 않는다. 따라서 자신의 적을 저장할 자료구조(Hashing)와 친구를 저장할 자료구조(인접 행렬 및 리스트/ DSU)를 정해야 한다. * 풀이 친구를 저장할 때는 인접 행렬 및 리스트로 저장하는 것은 꽤 간단하다. 하지만 적을 저장할 때는 어떻게 해야 할까? 이분 그래프이기 때문에 적을 단 하나만 저장한다. 이를 루트로 두고, 들어오는 데이터에 따라 자신의 적을 읽어들여, 적과 적을 이..

다소 까다로운 문제다. 문제 내용을 읽으면 우선 트리를 떠올리게 되는데, 문제에 맞는 트리의 속성을 적자면 아래와 같다. 1. 이진 트리다. 2. 자식이 하나만 있는 노드는 없으며, 자식이 있다면 무조건 2개의 자식을 갖는다. 하지만, 트리는 아니다. 이는 훼이크고, 그냥 단순 그래프이나, 노드에 순서성에 대해 트리형태처럼 보일 뿐이다. 정확히는 DAG(Directed acyclic graph)를 나타낸다. 따라서 나는 세 단계를 거쳐 AC를 받게 됐다. 1. MLE 2. TLE 3. AC (만약 단순 솔루션만 보고 싶다면 기본 아이디어 이후, 3.으로 바로 넘어가길 바란다.) * 기본 아이디어 그래프를 배열로 구현하고, 문자열에 대한 것은 string, map을 사용하여 배열에 대한 위치값(또는 포인터..