본문 바로가기

알고리즘

 (305)
[백준] 1699번 : 제곱수의 합 1699번: 제곱수의 합 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 🤔 문제분석 전형적인 다이나믹 프로그래밍 문제이지만 저는 처음에 문제를 풀때 너비우선탐색으로 문제를 해결하였습니다. 다이나믹 프로그래밍 풀이법과 너비우선탐색 풀이법 둘다 문제 풀이를 해보겠습니다. 다이나믹 프로그래밍 i 번째 제곱 수를 구할때 이전에 구했던 제곱수를 참조하여 값을 구합니다. dp[i] = min(dp[i], dp[i-제곱수] + 1) 로 나타낼 수 있습니다. 아래를 예를 확인하면 이..
[백준] 11726번 : 2xN타일링 11726번: 2×n 타일링 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🤔 문제분석 이번 문제는 문제의 아이디어가 떠올리지 않아서 인터넷검색을 통해 흰트를 찾았습니다. 제가 찾아본 흰트중 가장 이해가 잘 되었던 내용을 이야기하고자 합니다. 어떠한 수열이 있다고 가정해봅니다. [1, 2, 3, 4, 5] 수열이 주어졌을때 여기서 순열의 가지수는 5! 입니다. 하지만 [1, 2]는 고정되어있다고 가정하고 나머지의 수열을 구한다면 3!이 되겠습니다. 이렇게 숫자가 이미 고정되어있는 사고 방식을 해당 문제에 적용해봅니다. n이 3일때..
[백준] 5557번 : 1학년 이번주는 다이나믹 프로그래밍 문제를 푸는 주 입니다. 지난주에는 그래프 이론 유형의 문제를 풀었는데요, 다이나믹 프로그래밍 문제를 풀어보니, 저는 그래프의 문제를 더 잘 푸는것 같습니다. 이번주에는 다이나믹 프로그래밍 유형을 열심히 익히도록 하겠습니다. 5557번: 1학년 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 🤔 문제분석 처음에 문제를 접근할때에는 탑다운 방식으로 문제를 접근하였습니다. 저는 아직까지 탑다운 방식의 문제풀이가 더 쉽게 풀리는것 같습니다. 현재위치의 인덱스에서 덧셈과 뺄셈을 해..
[백준] 1948번 : 임계경로 1948번: 임계경로 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 🤔 문제분석 진입차수를 알고있으면 문제를 쉽게 접근 할 수 있습니다. 진입차수로 가장 오래걸리는 시간을 구한뒤, 진입 차수를 역추적하여 가장 큰 값이 방문된 곳들을 카운팅하여 문제를 해결 할 수 있습니다. 진입차수를 역추적 하는 방법은 간선의 정보를 거꾸로 입력받은뒤에 목적지로부터 소스까지 재 방문해봄으로서 문제를 해결 할 수 있습니다. 되돌아가는 과정에서 이미 구한 최대거리를 계산한 값을 확인해가면서 역추적 하면..
[백준] 3197번 : 백조의 호수 3197번: 백조의 호수 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 🤔 문제분석 구현은 까다롭지 않은 문제이나, 시간복잡도를 최적화 해야한다. 이전에 움직였던 자료를 재 활용하여 이전에 탐색했던 내용을 기반으로 다시 탐색해 나아가야합니다. 문제를 쉽게 풀기 위해, 백조를 움직이는 것과, 빙산이 물이 되는 것을 나누었습니다. 백조를 한번움직이면, 빙산에 도달하기전까지의 이전의 위치를 기록하고 있다가 빙산이 녹고난뒤에 다음에 백조를 움직입니다. 빙산을 녹일때 빙산을 녹인뒤, 다음..
[백준] 5718번 : 거의 최단 경로 5719번: 거의 최단 경로 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 🤔 문제분석 어제와 오늘 이 문제 때문에 머리가 너무 아팠습니다 😂 이틀동안 고민해봤지만, 시간초과와 메모리초과를 해결할 수 없어, 해결방안을 찾아보았습니다. 우선, 데이트스트라로 문제를 풀어야 했다는걸 알았지만, 데이크스트라의 최단경로를 어떻게 백트래킹 할 수 있을까 생각해 보았지만, 좋은 아이디어가 떠올리지 않았습니다. 문제의 핵심은 데이크스트라, 너비우선탐색으로 해결 할 수 있습니다. 문제의 포인트..
[백준] 9328번 : 열쇠 9328번: 열쇠 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 🤔 문제분석 BFS 탐색 및 구현 문제로, 문제만 정확히 이해 한다면 쉽게 풀 수 있는 문제입니다. 문의 Key를 확인하고자 딕셔너리 자료구조를 활용하였습니다. 출발할 수 있는 곳을 구하기 ( 단, 끝자락이 벽인경우, 열쇠인경우, 알파벳인경우를 예외처리 해주어야합니다. ) 탐색하기 : 출발지로부터 갈 수 있는곳을 탐색하며 열쇠와 문서의 개수를 업데이트 합니다. 만약, 문서와 열소의 개수를 얻지 못한다면, 다음 탐색에도 똑같기 때문에 여기서 게임을 종료합니다..
[백준] 2887번 : 행성터널 2887번: 행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 🤔 문제분석 크루스칼 알고리즘을 알고 있어야 해당 문제를 해결 할 수 있다. N-1개의 터널을 모두 건설하여( 최소산장트리의 간선의 개수) 행성들이 모두 연결된 상태를 만들어야한다. 또한, 간선의 개수를 구할때 O(n^2)이 아닌 O(3N)으로 해결 할 수 있는데, 비용을 계산할때, x와 y와 z를 각각 독립적으로 계산하여 간선에 누적한다. 📝 의사코드 간선을 만든다. x, y, z를 각각 분리하여 만들고,..

티스토리툴바