분류 전체보기 (400) 썸네일형 리스트형 99클럽 코테 스터디 8일차 TIL: 그래프 문제https://www.acmicpc.net/problem/2644풀이전형적인 그래프 문제이다.문제에서는 촌수를 계산하고 머 어렵지 않게 써놨지만,이 문제는 모든 간선의 비용이 1인 노드사이의 거리를 출력하라는 것과 동일하다.DFS, BFS 두 알고리즘으로 쉽게 풀 수 있는 문제였다.소스코드후기어렵지 않게 풀 수 있는 문제였다.챌린저 문제를 풀었어야 하는데.. 여러번 시간이 없다는 핑계로 안풀고 있다.내일이랑 모레도 바쁠텐데 꼭 풀어보려고 노력해야지. [BOJ] 백준 1240 노드사이의 거리 (Swift) 문제https://www.acmicpc.net/problem/1240풀이이 문제에서 명확하게 "트리" 라고 알려주었다."트리"는 무뱡항 그래프이다.DFS, BFS로 트리를 구현해서 풀 수 있겠다고 생각했다.DFS, BFS로 풀 때, 간선의 비용을 graph에 저장해두어야 겠다고 생각했다.그래서 그래프의 자료형을 [[(Int, Int)]] 형식으로 튜플의 2차원 배열로 선언해주어야겠다고 생각했다.물론 Struct나 Class, typealias 만들어줬어도 상관없다.첫번째로 풀이했을 때는 DFS로 풀어보았다.문제에서 간선의 개수는 노드의 개수 - 1 이고 같은 노드 번호는 주어지지 않으므로, 모든 노드가 연결되어있음을 알 수 있었다.startNode에서 DFS를 수행했다. startNode에서 DFS를 수.. 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.. [BOJ] 백준 2346 풍선 터뜨리기(Swift) 문제https://www.acmicpc.net/problem/2346풀이오른쪽으로 이동하는 것 (양수)인 경우에는array.append(array.removeFirst()) 를 통해 맨 앞으로 이동시킬 수 있다.주의할 점으로는 적힌 숫자보다 -1 만큼 이동을 시켜주어야 한다.예를 들어 다음과 같은 배열이 있을 때를 생각해보자.array = [2, -1, 1]가장 앞에 있는 2가 터지고 2만큼 뒤에있는 1이 터져야 할 상황이다.2가 터졌기 때문에 index가 자연스럽게 1이 줄어들게 된다.[-1, 1]array.append(array.removeFirst()) 수행 시 다음과 같다.[1, -1]한 번만 수행해도, 1이 가장 앞에 위치하는 것을 확인할 수 있다.왼쪽으로 이동하는 방식은 (음수) 다음과 같이 .. [BOJ] 백준 14502 연구소(Swift) 문제https://www.acmicpc.net/problem/14502풀이접근 방법그래프에서 0 -> 1로 변경시켜주어야 하는 작업이 필요할 것0 -> 1로 3개를 변경해주어야 하는 작업이 필요하기 때문에, 0의 위치들 중에서 3개를 뽑는 조합 알고리즘의 필요성을 느낌0의 위치를 배열로 담아주어야겠다고 생각함for문 3개로 0 -> 1로 바꿔주는 방법을 하려고 했지만 이 문제에서는 필요없겠지만 추후 확장성을 위해 조합알고리즘을 짜야겠다고 생각함0 -> 1로 3개를 변경했다면, 바이러스(2)에서 BFS를 수행해야겠다고 생각함2의 위치를 배열로 담아주어야겠다고 생각함BFS를 수행 이후 0의 개수를 세고 max 값을 찾는다. 그리고 0 -> 1로 바꿔준 부분을 되돌려주어야 함 (백트래킹)반복..이 문제는 n과.. 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일 때는 아직 방문하지 않.. 이전 1 ··· 3 4 5 6 7 8 9 ··· 50 다음
