본문 바로가기

전체 글

 (346)
[백준] 5582. 공통 부분 문자열 풀이 (Python, TypeScript) 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 접근한 방법 최장 공통 부분수열을 구하는 문제로써 DP를 활용하여 해결할 수 있습니다. 1. DP 테이블 d를 생성하여 문자열의 길이에 따른 최장 공통 부분 수열 길이를 저장합니다. d[i][j]는 s1의 첫 i개 문자와 s2의 첫 j개 문자 사이에서의 최대 공통 부분 수열의 길이를 나타냅니다. 2. 문자열을 비교해 최장 공통 부분 수열 길이를 갱신합니다. 이중 반복문을 사용하여 s1과 s2의 각 문자를 순회하면서 만약 s1[i - 1]과 s2[j -..
[백준] 2665. 미로 만들기 풀이 (Python) 접근한 방법 미로에서 최단 경로를 찾는 BFS 알고리즘을 사용하여 해결할 수 있습니다. 최소 heap 자료구조를 이용하여 매 방문마다 가장 적게 벽을 바꾼 지점의 좌표를 꺼내서 해당 좌표에서만 탐색을 나아가면 최소 개수로 벽을 바꿀 수 있습니다. 1. 큐에서 원소를 하나씩 꺼내면서 해당 위치의 상하좌우를 체크합니다. 2. 벽이 있는 경우는 +1 카운트 하여 큐에넣고 그렇지 않은 경우는 그대로 큐에 넣어줍니다. 3. 마지막 지점에 닿으면 현재까지의 카운트를 출력하고 종료합니다. Python import sys input = sys.stdin.readline n = int(input()) arr = list(list(map(int, input().rstrip())) for _ in range(n)) from..
[백준] 5972. 택배 배송 풀이 (Python) 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 접근한 방법 그래프의 간선 가중치를 고려한 최단 경로를 구하는 문제입니다. 힙 자료구조를 이용한 다익스트라 알고리즘으로 풀이할 수 있습니다. dist는 노드 간의 최단 거리를 저장할 리스트로 초기값은 무한대(inf)로 초기화하고 1번 노드부터의 최단 거리를 나타냅니다. graph는 각 노드에 연결된 엣지 정보를 저장하는 리스트입니다. 먼저 그래프 정보를 구성해야 합니다. m번 반복하여 입력으로 주어지는 간선 정보를 바탕으로 생성합니다. 양방향 그래프이므로 두 노드 간의 ..
[백준] 2096. 내려가기 풀이 (Python, TypeScript) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근한 방법 답을 도출하기 위한 풀이 로직은 쉽지만 메모리, 시간 초과 문제로 인해 정답 비율이 낮은걸로 보입니다. 이 문제를 만약 2개의 배열을 만들어 중간 결과를 저장하는 방식으로 코드를 짰다면 입력 데이터가 클 때 메모리 제한(4mb)에 걸리게 될겁니다. 따라서 입력 데이터의 최댓값과 최솟값을 계산하면서 중간 결과를 저장하는 대신, 이전 단계의 계산 결과만 활용하여 계산해 나가는 방식을 사용하면 풀이할 수 있습니다. 첫 입력 데이터 한 줄을 초깃값으로 정해놓고 다음 입력..
[백준] 2636. 치즈 풀이 (Python, TypeScript) 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 접근한 방법 7576. 토마토 문제와 살짝 비슷합니다. 내부, 외부 공간을 굳이 구분할 필요는 없고 매 시간마다 처음 (0, 0) 좌표에서만 bfs를 수행하면서 치즈를 만나는 경우만 체크하여 제거 리스트에 올려주고 그 외 공간은 모두 탐색을 계속 진행하면 됩니다. 치즈를 만나는 경우는 탐색 대상에 들어가지 않기 때문에 애초에 치즈로 둘러쌓인 공간을 탐색할 일이 없습니다. 1. 전체 치즈 수를 체크합니다. 2. 좌표 0, 0 에서 bfs를 실행합니다. 상하좌우를 확인하여 공기만 경우..
[백준] 2589. 보물섬 풀이 (Python, TypeScript) 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 접근한 방법 비교적 풀이법이 단순한 완전탐색 문제. 지도가 몇 개의 육지로 나뉘어져 있는 지는 아무 상관 없습니다. L에 해당하는 모든 칸을 확인하여 BFS를 수행합니다. 1. L이면 BFS를 들어갑니다. 2. 시작점을 1로 잡고 이후 상하좌우로 방문하는 L칸 마다 +1씩 더하여 값을 넣어줍니다. (방문 처리) 3. 마지막으로 방문한 칸에서 시작점인 1을 뺀 값이 해당 좌표에서 계산된 시작점에서 가장 먼 지점까지의 거리가 됩니다. 4. 모든 L칸에 대해서 1~3 과..
[백준] 2573. 빙산 풀이 (Python, TypeScript) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 접근한 방식 1. 입력으로 n, m을 받고, 2차원 배열 arr에 빙산 정보를 저장합니다. 2. 주어진 4방향(dist)을 이용하여 빙산이 한 덩어리로 얼마나 오래 지속되는지 계산하는 solution 함수를 정의합니다. 3. dfs를 정의하고 모든 빙산이 연결되어 있는지 확인합니다. 4. solution 함수에서는 빙산이 1개로 이루어져 있거나 빙산이 나뉘어 있는 경우까지 계속 반복하여 빙산을 녹이고, 빙산이 1개로 이루어져 있을 때까지 걸리는 시간을 반환..
[백준] 2470. 두 용액 풀이 (Python, TypeScript) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 접근한 방법 입력받은 용액들을 오름차순 정렬한 후 투 포인터로 해결할 수 있습니다. 포인터를 각각 배열의 왼쪽, 오른쪽 부분에서 시작하도록 설정하고 두 포인터가 엇갈리지 않을 때까지 포인터가 가리키는 각 배열의 값의 합의 최솟값을 갱신합니다. 값을 갱신할 때는 0에 수렴하는 값을 넣어줘야 하므로 절댓값으로 바꿔 넣어줍니다. 현재 순회중인 각 포인터가 가리키는 배열의 합이 0보다 큰 경우 오른쪽(큰 값)값을 줄여줘야 하므로 오른쪽..

티스토리툴바