향해99 (3) 썸네일형 리스트형 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 다음
