TIL (31) 썸네일형 리스트형 99클럽 코테 스터디 7일차 TIL: 트리 문제https://www.acmicpc.net/problem/1240풀이접근방법이 문제에서 명확하게 "트리" 라고 알려주었다."트리"는 무뱡항 그래프이다.DFS, BFS 등 트리를 구현해서 풀 수 있겠다고 생각했다.DFS, BFS로 풀 때, 간선의 비용을 graph에 저장해두어야 겠다고 생각했다.그래서 그래프의 자료형을 [[(Int, Int)]] 형식으로 튜플의 2차원 배열로 선언해주어야겠다고 생각했다.물론 Struct나 Class, typealias 만들어줬어도 상관없다.첫번째로 풀이했을 때는 DFS로 풀어보았다.문제에서 간선의 개수는 노드의 개수 - 1 이고 같은 노드 번호는 주어지지 않으므로, 모든 노드가 연결되어있음을 알 수 있었다.startNode에서 DFS를 수행했다. startNode에서 D.. 99클럽 코테 스터디 6일차 TIL: 그래프 문제https://www.acmicpc.net/problem/2458풀이일단 어떤 알고리즘을 사용해서 풀어야할 지 고민을 해봤다.문제에 나와있는 그래프를 보면 4번만 자신의 키 순서를 명확히 할 수 있었다.그 이유는 자기보다 작은 학생의 수 + 큰 학생의 수를 했을 때, 자기를 제외한 총 학생의 수이기 때문이다.입력으로 키를 비교한 결과를 보여주고 있다.이는 방향 그래프를 의미하며 문제에 나와있는 그래프와 동일하게 구현할 수 있다.그래서 4번 학생을 시작노드로 DFS 혹은 BFS를 수행했을 때는 2번 6번에 도달할 수 있다.이는 4번보다 큰 학생이 2번, 6번 총 2명이라는 뜻이다.4번 보다 작은 노드는 어떻게 처리할 수 있을까.4번 노드에 방문이 가능하다면, 4번보다 작다는 것으로 알 수 있지 않을까?.. 99클럽 코테 스터디 5일차 TIL: BFS 문제https://www.acmicpc.net/problem/24444풀이문제 이름에서 나와있는대로 BFS를 구현하는 문제이다.BFS는 많이 풀어봤던 문제이고 로직 또한 익숙했다.문제에서 무방향 그래프로 나타나있어서, 인접행렬 혹은 인접리스트로 구현할 때 처리를 해주어야 했다.추가로 오름차순 순으로 방문해야 하기 때문에, 정렬이 필요했다.BFS는 Queue 자료구조를 사용하는데, Queue에 넣을 때 방문한 순서를 1증가시켜 주었다.또한 visited 배열을 방문한 순서를 들고 있도록 하기 위해 Int 배열로 만들어주었다.여기서 visited[i] = 0 이면 미방문 노드이고, 2라면 2번째 순서로 방문한 노드와 같이 생각하면 된다.문제에서 방문하지 못하는 노드의 순서는 0으로 처리하라고 되어있어서 그 .. 99클럽 코테 스터디 4일차 TIL: DFS 문제https://www.acmicpc.net/problem/24479 풀이오늘은 챌린저 문제가 아닌 미들러 문제를 풀었다.그 이유는 챌린저 문제를 1시간안에 풀어보려 했지만 풀이하지 못했다.힌트를 확인해보니 벨만포드 알고리즘이였고,벨만포드 알고리즘 하면 기억나는데 음의간선에서도 최단거리를 구할 수 있다는점..? 그래서 사이클이 존재하면 안된다는 점 밖에 기억이 나지 않았다..그래서 일단은 미들러 문제를 풀고, 주말에 벨만포드 알고리즘에 대해 더 학습하고 풀어야겠다고 생각했다.미들러문제는 DFS의 기본적인 문제였고, 챌린저 문제와 난이도 차이가 있다고 느꼈다.DFS에 대해 알고, 조금만 응용한다면 쉽게 풀 수있다.방문 여부를 확인하는 visited 배열을 Int로 사용하였고, 0일 때는 아직 방문하지 않.. 99클럽 코테 스터디 3일차 TIL: 최단 경로 문제https://www.acmicpc.net/problem/2660풀이이 문제도 보자마자 BFS를 떠올렸다.일단 간선의 비용이 1이라는 점에서 최단거리를 구할 수 있기 때문이다.어제 풀었던 문제와 거의 유사한 문제여서 빠르게 풀 수 있었다.회원의 수가 50명 즉 N이 50으로 아주 작았다.또한 플로이드-워셜로도 풀 수 있을 것이라고 생각했는데,오늘은 약속도 있고 요즘에 작곡 레슨을 받아.. 시간이 없어서 일단 BFS로 풀고 내일 다시 플로이드-워셜로 풀어봐야겠다.이 문제는 진짜 빨리 풀었고 (5분?) 한 방에 풀이했다.BFS가 젤 자신있어서 그런 것 같다.. 다른 알고리즘에도 자신감이 생기게 열심히 해봐야지..소스코드후기BFS를 조금 응용하면 쉽게 풀 수 있는 문제였다. 99클럽 코테 스터디 2일차 TIL: 최단 경로 문제풀이이 문제를 처음 봤을 때, 간선의 비용이 동일하다는 점. 최단 경로를 구해야 한다는 점에서 BFS 알고리즘을 떠올렸다.BFS의 시간복잡도가 어떻게 될까도 생각해봤다.$O(V + E)$ 라는 점, 최악의 경우 $O(100 + 5000)$ 이 될 것이라고 생각했다.또한 모든 친구($N$)에 대해 검사를 해봐야 하므로, $O(V * (V + E))$ 이지 않을까..?$100 \times 5100$라면 충분히 통과할 것이라고 생각했다.처음엔 다음과 같이 생각했다.1번노드에서 각 노드로 도달하는 depth를 전부 구해 더해줘야겠다라고 생각했다.즉, 1번 -> 2번으로 가능 최소비용 + 1번 -> 3번으로 가능 최소비용.. 이렇게 전부 구해야지 하고 생각하면서bfs를 1번에서 특정 노드 까지의 비용을 모두 .. 99클럽 코테 스터디 1일차 TIL: 플로이드-워셜 오랜만에 우연히 백준을 들어갔는데 향해99 광고를 보고 스터디 참여 신청을 했다.취업을 한 뒤 코테 공부를 거의 하지 않아서 기억이 가물가물..코테 공부하는게 재밌었기도 하고, 공부해야지 해야지.. 하는데 맨날 하지 않아서 스터디라도 해보면 어떨까 생각이 들었다.대학교 친구 단톡방에 공유해서 한명의 친구와 같이 참여하고 있다.언어랑 난이도도 선택할 수 있었는데, 나는 Swift/챌린저로 선택을 했다.챌린저 문제는 다음과 같았다.문제https://www.acmicpc.net/problem/11403 풀이기존에 풀어봤던 문제였다.문제 딱 보자마자 느낀점은 그래프 문제라는 것. 그 이후 모든 경로를 구해야한다는 점에서 플로이드-워셜 알고리즘을 떠올렸다.플로이드-워셜 알고리즘에 대한 이해만 있다면 쉽게 풀 수 .. 이전 1 2 3 4 다음
