본문 바로가기

python

 (13)
백준 2098 외판원 순회(python) 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회 2 문제와 다르게 시간과 메모리 조건이 달랐기 때문에 비트 마스크 개념과 dp개념을 사용하여 접근한 문제입니다. 순회하면서 방문하는 노드의 상태를 비트의 형태로 표현해 주었습니다. 과정은 다음과 같습니다. 순회하면서 메모이제이션할 값들을 현재의 노드와 상태를 기준으로 저장해 주었습니다. 순회하면서 기존에 저장한 값이라면 dp 리스트에 저장된 ..
백준 22239 가희와 읽기 쓰기 놀이2(python) 문제 https://www.acmicpc.net/problem/22239 22239번: 가희와 읽기 쓰기 놀이 2 결과 리스트가 [2, 1, 2, 2, 3, 4, 2, 3]으로 주어졌다고 생각해 보겠습니다. [그림 1] 유효한 결과 리스트 결과 리스트에서 두 번 이상 등장한 수는 2, 3입니다. 2가 등장한 횟수는 4번, 3이 등장한 횟수 www.acmicpc.net 구현하기 까다로웠던 문제였습니다. DFS 방식으로 접근하여 풀었습니다. 주어진 제약 조건에 맞게 카드와 사람들 간에 관계를 연결하여 푸는 문제였습니다. 과정은 다음과 같습니다. 주어진 제약들과 카드 값들을 입력받고, 제약에 맞게 카드값들에 플레이어 번호를 넣어 줍니다. 탐색하는 함수에서는 만들어내야하는 결괏값이 있는지 확인하고, 있다면 값을..
백준 11049 행렬의 곱셈 순서 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net DP로 접근해서 해결한 문제입니다. 점화식이 쉽게 생각나지 않아서 도움을 많이 받았습니다. 이 문제는 주어진 행렬의 곱셈 순서에 따라 연산 횟수가 달라지는데 그중 최소 연산 횟수를 찾는 문제입니다. 과정은 다음과 같습니다. 값을 저장할 dp 리스트를 이차원으로 만듭니다 dp [i][j] = i행렬부터 j행렬까지의 최소 연산 행렬 간의 곱을 여러 경우로 만들어 낼 수 있어서 시작 ..
백준 20119 클레어와 물약(python) 문제 https://www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다. 다음 M개의 줄에는 각각의 줄마다 레시피의 정보 k www.acmicpc.net 문제에서 느꼈던 중요한 포인트는 물약을 만들 수 있는 레시피가 여러 개 존재할 수 있다는 점이었습니다. 만들 수 있는 레시피들의 포션의 존재 여부를 파악하면서 해당되는 레시피가 하나라도 완료되면 포션을 만들 수 있기 때문에 결과에 넣어주었습니다. 과정은 다음과 같습니다. 물약 데이터 클래스를 만들어서 연결될 점들과 레시피들, 필요한 포션의 개수들, 만들 ..
백준 2638 치즈(python) 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net BFS 방식으로 접근하였습니다. 문제의 접근 자체를 공기를 기준으로 할지 치즈를 기준으로 할지 정해서 풀 수 있었습니다. 저는 치즈를 기준으로 밖의 공기와 내부 공기를 나눠서 풀었습니다. 과정은 다음과 같습니다. 먼저 처음 주어진 상황에서 모든 공기를 돌며 외부 공기를 파악해줍니다. 다음으로 치즈를 찾아 외부 공기의 개수를 세줍니다. 조건에 맞게 접촉한 면이 2개 이상이면 지워져..
백준 14226 이모티콘(python) 문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 주어진 경우에 맞게 연산들을 진행해 나가며 목표 개수에 도달하는 문제입니다. BFS 방식으로 접근하였습니다. 과정은 다음과 같습니다. 각 경우로 조건을 나누어서 연산을 진행해 줍니다. 연산된 결과를 통해 이전에 접근했는지를 확인해줍니다. 가보지 않은 경우라면 큐에 넣어주고 과정을 진행합니다. 최종적으로 목표 개수에 도달하면 시간값을 출력해 줍니다. 확인 리스트를 2차원으로 한 이유는 화면에 있..
백준 13549 숨바꼭질 3(python) 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 주어진 2가지 경우로 이동하면서 목표지점으로 가는 문제였습니다. 이렇게 간선의 가중치가 두 종류로만 이루어진 문제를 0,1 BFS라고 부르며 데크를 사용하여 구현할 수 있습니다. 구현 과정은 다음과 같습니다. 처음 시작지점을 데크에 넣어줍니다. 데크의 가장 앞쪽 값을 pop 해 주어서 갈 수 있는 조건에 따라 시간을 구해 줍니다. x-1, x+1 일때는 1초..
백준 3055 탈출(python) 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS방식으로 문제에 접근했습니다. 물과 고슴도치 둘 다 움직이는데, 고슴도치는 물이 있는 곳으로 갈 수 없으니, 물을 먼저 움직여서 이차원 리스트에 표시해 두고, 그다음 고슴도치를 움직여 주었습니다. 물과 고슴도치 두 개의 큐를 사용하였습니다. 시작할 때 물의 위치와 고슴도치의 위치를 받아서 큐에 각각 넣어줍니다. 물은 여러 곳에 존재할 수 있습니다. 물이 갈 수 있는 곳을 찾아서 각 방향으로 움직여서..

티스토리툴바