Gi-Log

문제 링크: https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이에 이용된 알고리즘: BFS, 순열(DFS), Brute Force 삼성 전자 코딩 테스트 기출 문제 풀이를 진행했거나 최근 bfs, dfs 등을 공부하는 사람에게는 익숙한 미로 탐색 유형이다. 아... 미로 탐색 유형이 익숙하다는 것이고, 16985 문제의 경우는 익숙하지 않은 미로 탐색처럼 느껴질 수 있다고 생각된다. 일단 단순히 미로를 탐색하는 것이 아니..

문제 링크: https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 풀이에 이용된 알고리즘: DFS, BFS 주어진 테스트 케이스보다 풀이자가 다소 확장된 테스트 케이스를 만들어서 도출해보는 것을 추천한다. 9 7 4 1 3 2 3 3 4 3 7 4 6 5 8 7 9 본인은 위 테스트 케이스를 제작 및 이용했다. 4번이 몇 등인지 최고 등수(숫자가 작을 수록 최고라고 표현하겠다.)와 최저..

문제: SW Expert Academy 1248번 공통조상 (효율적인 풀이인지 검증이 필요한 풀이입니다) 주어진 트리 정보를 바탕으로, 두 정점의 공통 조상을 파악하고, 그 조상의 자식 노드 수 + 1(=서브 트리 크기)를 구하는 문제이다. 개인적으로 트리 문제가 나오면 긴장하는 편인데, 주어진 정보를 바탕으로 트리를 구현해야하나...라는 고민을 처음에 했고, 배열을 이용해서 트리를 구현하려고 했다. 하지만 공통조상을 찾기 위해서는 트리를 거슬러 올라가야할 필요가 있었기에 단순히 각 노드의 부모가 누구인지 parent라는 배열에 저장하고, 각 노드의 자식 노드는 누구(들)인지 child라는 2차원 배열에 저장하기로 하였다. 이 때 2차원 배열인 이유는, 주어진 트리가 이진 트리이기 때문인데, 그냥 vec..