Algorithm/Graph Search Algorithm30 BOJ G4 9177 단어섞기 JAVA 9177번: 단어 섞기 입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어 www.acmicpc.net 문제 읽기 문제를 처음에 읽었을 때에는 모든 경우의 수를 따지는 방법을 생각했다. 단순하게 생각하면 dfs가 직관적이라 dfs를 생각했지만, 복잡도를 생각했을 때 단어의 길이가 200이기 때문에 dfs를 수행하면 지수 시간이기 때문에 불가능했다. 그래서 bfs로 접근했다. 문제 풀기 bfs로 풀었는데, 사실 처음에는 visited가 필요 없다고 생각했다. 처음에 다음 그림을 그렸었다. 이렇게 오른쪽, 아래쪽 두 방향으로 내려가면 경우의 수를 구했을 때 방문 처리는.. 2024. 3. 18. BOJ G4 12886 돌그룹 JAVA 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 문제 읽기 처음 문제를 읽고 예제를 한 번 그려봤다. 위와 같은 과정을 통해서 이루어진다면 돌이 정확히 분배된다. 위에서 알 수 있는 점은, 세 그룹에 있는 돌의 합이 3으로 나누어 떨어지지 않는다면 무조건 0을 출력한다는 점과, 이 문제는 다른 알고리즘 보다는 완전 탐색을 해야 할 것 같다는 느낌(?)이다. 그래서 완전 탐색인 DFS를 통해서 풀어보았다. 문제 풀기 처음 작성했던 풀이 과정은 크게 복잡하진 않았다. 우선 세 그룹을 두 그룹씩 개수를 비교해서.. 2024. 3. 11. BOJ G2 2108 로고 JAVA 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 문제 읽기 일단 처음 딱 문제를 읽었을 때는.. 복잡하게 여러 연산이 있는 것처럼 나왔지만 결국엔 직사각형의 연결 컴포넌트 개수를 구하는 문제라는 생각이 들었다. 다음 그림을 보면 쉽게 이해할 수 있을 것이다. 그래서 이를 이용해서 문제를 해결했다. 문제 풀기 처음에 풀이 과정을 다음과 같이 구상했다. 다시 정리해 보면 다음과 같다. 사각형 좌표를 입력 받아 사각형 정보를 배열에 저장한다. 모든 사각형을 맵에 그려준다. 사각형을 그린다는 것은 맵에 각 방향에 대해 이동 가능.. 2024. 3. 7. BOJ G4 1956 운동 JAVA 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 읽기 처음에 문제를 읽고 풀었을 때는 dfs로 풀었었다. 그런데 3퍼센트 쯤에 시간 초과가 나와서 그냥 다른 방법을 생각해야겠구나 싶었다. 최단 거리니까 다음과 같은 세 가지 방법이 있었다. 다익스트라 벨만포드 플로이드워샬 각각은 사용하는 경우가 다양한데, 처음엔 다익스트라? 생각했다가 시작 지점이 정해져 있지 않기 때문에 다익스트라를 하려면 여러 번 돌려야만 했다. 그래서 모든 지점에서 다른 모든 지점까지의 최단 거리를 .. 2024. 2. 27. 이전 1 2 3 4 5 ··· 8 다음
