MuviSsum

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제: 주어진 트리에서 트리의 지름을 구하여라 문제 이해하기!! 해당 문제는 1167번 문제와 같은 문제입니다.문제의 설명과 풀이 방법은 이전 글을 참고하시거나 해당 링크를 따라가시면 됩니다!링크: https://txegg.tistory.com/166 [BOJ] 1167. 트리의 지름 www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제: 주어진 트리에서 트리의 지름을 구하여라 문제 이해하기!! 트리의 지름이란 원본 문제를 보면 설명이 나와있는데요, 임의의 정점에서 임의의 정점까지의 거리가 최대인 것을 뜻합니다. 그럼 어떻게 구해야할까요? 정점의 갯수는 10만으로 플로이드-와샬 알고리즘은 못 씁니다. 그럼 다익스트라를 써도 될까요? 으음.. DP로 저장한다고 하더라도 여러 정점을 살펴봐야하기에 힘들죠. 좀 더 기본적인 방향..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제: 집들이 연결되어 있는 단지를 파악하고 총 단지의 수와 각 단지의 집이 몇개인지 파악하라. 문제 이해하기!! 해당 문제는 딱 명확한 완전탐색이었습니다. BFS, DFS든 상관은 없구요, visit 배열로 방문체크만 해준다면 바로 풀리는 문제입니다. 제가 푼 방식을 설명하자면, 1. 입력받은 배열을 for문으로 돌려, 아직 방문하지 않은 곳이고 집이 있는 곳이라면 DFS를 수행합니다. 2. DFS구현: DFS..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제: 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력하라. 문제 이해하기!! 구역을 나누는 것을 구해야 되는 문제입니다. 문제에서 나오는 적록색약은 미끼로 그냥 두 번 "R"을 "G"로 바꾸어 한 번 더 구하면 되는 문제였습니다. 그렇다면 어떻게 구역을 나눌까요. 저는 DFS로 완전탐색을 실시하였습니다. 해당 구역들을 찾기 위해서는 각 구역..

www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제: 뱀과 사다리 게임에서 주사위를 최소로 굴려 1부터 100까지 가장 빠르게 도착할 수 있게 하라. 문제 이해하기!! 뱀과 사다리 게임은 예전에 많이 해봤던 추억의 놀이죠. 그래서 문제를 쉽게 이해할 수 있었던 것 같습니다. 1부터 100까지이므로 모든 경우의 수를 다 확인하면 됩니다 ㅎㅎ (완전탐색!!) 다만, 주의할 점은 뱀으로 이동하면 100번까지 더 빨라..

www.acmicpc.net/problem/19621 19621번: 회의실 배정 2 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net 문제: 회의실에 최대한 많은 사람들이 회의할 수 있도록 만들어라. 문제 이해하기!! 일반 회의실 배정 문제와 다른 문제였습니다. 각 회의마다 인원이 다르고 앞과 뒤의 회의랑 회의시간이 무조건 겹치기 때문에 브루트포스 방법을 쓰는 문제였습니다. 문제에서 시작시간이 순서대로 입력이 들어온다는 말이 없어서 sort()를 해주고 시작했습니다. dfs를 재귀적으로 썼고 종료 조건은 N보다 n이 커지면서 res보다 ..

처음에는 하.. 이걸 어떻게 풀어야 하나 생각했는데 보니까 N이 10개더라구요. 그래서 바로 브루트포스로 돌렸습니다!! ㅎㅎ 그러다가.. dfs로 돌리고 페일.. ㅠㅠ 그리고 bfs로 바꿔서 성공했습니다. (나중에 알았지만, dfs도 풀 수 있는데 하... 제가 다 만들어 놓은 코드에서 합계 계산을 잘 못 했더라구요 ㅠㅠ 까빙..) 풀이 방법은 각각의 N-a와 a개의 도시 조합을 나누어서 브루트포스를 돌리면 됩니다. dfs / bfs 방법 둘 다 가능한데, bfs가 쉽습니다... ㅎㅎ bfs 추천 드릴게요! 코드: from itertools import combinations def bfs_com(x, cnt): global res1 Q = connect.get(x)[:] while Q: tmpp = Q..

DFS란? 깊이 우선 탐색 자신에게 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다. 이동한 노드에서 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다. 이렇게 계속 내려가다가 자식 노드가 없는 노드를 찾는다. 다시 부모 노드로 이동하여 새로운 자식 노드를 찾는다. 또 자식노드가 없으면 다시 부모노드로 이동하여 위의 순서를 반복한다. 완전탐색 중 한 방법 - 위의 순서를 보면 모든 노드를 체크하는 것을 볼 수 있다. DFS에서 발전된 알고리즘 : 백트레킹 백트레킹은 DFS 방식을 하면서 조건을 추가한다. 한 노드가 조건에 맞지 않으면 밑의 자식노드 또한 조건에 맞지 않으므로 다시 부모노드로 돌아간다. DFS보다 훨씬 시간을 줄일 수 있다. DFS를 이해하기 위해서는 그림을 보면 쉽..

백준 문제 주소 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준알고리즘을 시작한지 이제 한달이 되어가네요. 기본적인 문제들을 풀면서 이제 실력이 좀 늘은 것 같아요 ㅎㅎ 그래서 괜찮았던 문제 하나씩 블로그에 올려보려 합니다! 이번 문제는 Gold-5 문제인 N-Queen 문제인데요! N*N 체스판에 N개의 퀸을 넣고 퀸이 서로 공격을 못 하게 해야합니다. 역시 처음에는 2차원 배열로 해결해야죠!! True와 False를 사용하여 2차원 배열을 써본결과..