본문 바로가기

알고리즘 문제147

[알고리즘문제] 프로그래머스 - 경주로 건설 먼저 최소비용 문제이기 때문에 bfs를 사용했습니다. 처음 23점을 맞고, 코드를 분석하는데 상하좌우 탐색할 때 더 많은 비용을 사용함에도 먼저 탐색했기 때문에 그 경로를 사용하는 오류가 있었습니다. 그래서 이 부분을 해결하는 방법은 다른분의 코드를 참고하였는데, arr[][]에 해당 지점에서의 최소비용을 저장하는 것입니다. 그래서 [4,5]에 방문했을 때 현재 계산된 값이 arr[4][5]에 저장된(이전에 누군가가 방문했을 때의 값)보다 더 작은 경우 arr[4][5]의 값을 갱신해 줍니다. 그리고 그때의 x,y, 방향, sum값을 저장합니다. 기존에는 [0,0]에서 오른쪽과 아래로 이동했을 경우 따로 구했는데 각 지점의 최소비용을 계속 갱신해 주는 방법이라면 그냥 [0,0]에서 시작해도 됩니다. 그리.. 2020. 9. 25.
[알고리즘문제] 프로그래머스 - 키패드 누르기 문제의 핵심은 번호의 위치를 좌표로 어떻게 표혈한 것인가 ? 이다. 그 이후의 다른 부분은 그냥 문제를 읽고 if문으로 처리해주면 된다. y위치는 num/3을 해주고, x위치는 0번째 인덱스 부터 시작하기 때문에 num%3 -1을 해준다. 그리고 제일 오른쪽 번호(3,6,9)에서 처리를 해주어야 하는데 3,6,9에서는 num%3값이 0이 되기 때문에 임의로 2를 넣어주어여 하며, y위치 역시 y위치로 +1값이 되기 때문에 -1을 해주어야 한다. 그 외부분은 문제의 설명대로 구하면 된다. #include #include #include #include using namespace std; int distance(int x1, int y1, int x2, int y2) // 두 점의 거리 { return a.. 2020. 9. 22.
[알고리즘 문제] 백준2606 - 바이러스 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net dfs,bfs로 풀 수 있는데 저는 bfs로 풀었습니다. 각 노드들의 간선을 양방향으로 map먼저 체크해주었습니다. 1번 컴퓨터 부터 시작하기 때문에 que에 1번을 넣어주고 하나씩 꺼내면서 맵에 연결되어 있으면 그 다음 시작점을 que에 넣는 방식으로 진행하였습니다. 한번 방문한 노드는 다시 방문하면 안되기 때문에 visited[]로 체크해주었습니다. #include #include using namespace.. 2020. 9. 21.
[알고리즘 문제] 백준17471 - 게리멘더링 www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제는 아래의 흐름으로 풀 수 있습니다. 1. 선거구를 나눌 수 있는 모든 케이스로 나누어 줍니다. next_permutation을 사용해도 되고 재귀를 사용해도 됩니다. 풀이에서는 재귀를 사용하였고 bool 1차원 배열을 사용하였습니다. 2. 케이스마다 각각의 선거구의 지역들이 모두 연결되었는지 검사합니다(연결 안되있으면 다음 케이스) 여기서 고민을 많이 했고, union-find방법을 사용할까 하다가, 다른분의 코드를 참고하여 .. 2020. 9. 11.

티스토리툴바