본문 바로가기

TIL

 (53)
백준 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초..
백준 2637 장난감 조립(python) 문제 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 위상 정렬과 dp개념을 사용하여 푼 문제입니다. 부품 간의 관계를 파악하여 우선순위를 따라가며 개수들을 계산하는 문제였습니다. 과정은 다음과 같습니다. 먼저 입력을 받아 장난감 부품중 기본 부품을 따로 구분해서 큐에 넣어주고 기본 부품부터 순회를 시작합니다. 연결된 상위 부품의 갯수를 계산하기 때문에 필요로 하는 하부 부품들의 개수를 하부 부품들을 만들 때 드는 개..
백준 2617 구슬 찾기(python) 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 그래프 탐색으로 접근할 수 있는 문제입니다. DFS, BFS 어떤 것을 사용해도 무방하지만 저는 플로이드-워샬이 먼저 떠올랐기 때문에 이 방식으로 풀어보았습니다. 출력해야 되는 값이 무게가 절대로 중간값이 될 수 없는 구슬의 개수를 세는 문제였습니다. 풀이 과정은 다음과 같습니다. 먼저 입력으로 들어오는 구슬 번호대로 무게 순서를 지켜 관계를 2차원 리스트에 1로 표시해 줍..

티스토리툴바