본문 바로가기

알고리즘/백준

 (263)
[백준] 2589번 : 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 해당 문제는 메모리제이션 기법과 완전탐색, 너비우선탐색으로 문제를 해결 하였습니다. A(x1,y1), B(x2,y2) : A,B 각각 육지일때 dp[x1][y1][x2][y2] = 최소거리 1. 2중 for문으로 육지일때 각각의 육지에 대한 거리를 계산하여 dp 테이블에 넣습니다. 2. 육지의 그룹이 2개 이므로, 해당 육지내에서만 이동할 수 있으므로 조합을 생성하여 조합중 거리의 최대값을 리턴하면 ..
[백준] 1068번 : 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 자기자신으로부터 방문할 수 있는 노드를 graph의 배열에 넣어둔뒤, 루트노드로부터 자식 노드들을 방문해가면서 각각의 노드들의 자식노드가 0일경우 cnt값을 증가시켜 문제를 해결 하였습니다. 루트노드가 지워진 노드일경우는 트리 자체가 사라지기 때문에 0으로 예외사항을 추가 했습니다. N = int(input()) nodeInput = list(map(int ,input().split())) ..
[백준] 16638번 : 괄호 추가하기 2 https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 해당문제는 식에다가 괄호를 추가하지 않거나 추가했을때의 모든 경우의수의 값을 구하여 최대값을 구하는 문제로 완전탐색, 구현 문제 입니다. 연산자의 우선순위는 곱하기가 제일 우선순위가 높고 그다음에 빼기, 더하기 임으로 곱하기는 괄호를 해도 식에 결과에는 상관이 없기때문에 곱하기 연산자는 무시합니다. 또한 빼기 더하기 연사자에 괄호를 추가할때 이전에 있던 연산자에 괄호가 추가되어..
[백준] 1285번 : 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 해당 문제는 브루트포스 + 비트마스킹으로 문제를 해결 하였습니다. 행을 먼저 뒤집은뒤 -> 열을 뒤집어보며 최적의 개수를 구합니다. 행을 뒤집은 경우와 뒤집지 않은 모든 경우의 수를 구합니다. 2^N의 경우의수가 나오는데, 이 모든 경우의 수를 각각의 테이블을 구한다면 메모리 복잡도와, 시간복잡도로 해결 할 수 없습니다. 그래서 각 행을 뒤집었는지 뒤집지 않았는지 비트마스킹을 활용합니다. 모든..
[백준] 1929번 : 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 해당 문제는 에라토스테네스의 체와 소수를 제곱근까지 확인하여 구하는 방식으로 시간복잡도를 최적화 할 수 있다. 우선 소수를 구할때에 제곱근까지 구하는 방식을 사용한다. 예를들어 20의 소수를 구할때 2부터 20까지 모든 수를 나누어 보면서 나누어 떨어지는지 나누어 떨어지지 않는지 확인하며 소수인지 아닌지 판별한다. 그러나 이 문제는 모든 수를 확인해야 함으로 O(n)의 시간 복잡도가 든다. 그러나 모든 수를 확인하지 않고 제곱수..
[백준] 1016번 : 제곱 ㄴㄴ수 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 해당 문제는 모든 경우의 수를 set 자료구조로 만들어서 전체에서 빼는 로직을 세웠으나, 메모리 복잡도에서 에러 판정을 받았다. 문제를 오랫동안 생각해보았지만 생각나지 않아서 정답을 찾아 보았다. 에라토스테네스의 체의 성질을 이용하여 문제를 해결하였다. visited 리스트를 0혹은1 상태로 저장하여 메모리 최적화를 하였습니다. min = 1, max = 1000 일때, 예를들어 ..
[백준] 11438번 : LCA 2 https://bigkwangs.tistory.com/65 [백준] 11437번 : LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 bigkwangs.tistory.com 해당문제의 시간복잡도를 개선한 문제 입니다. 조상을 찾아가는데에 시간복잡도가 O(n)이 소요되지만 메모리제이션을 통하여 O(logn) 으로 단축하였습니다. https://www.acmicpc.net/status?user_id=rhkdguskim&problem_id=11438&from_mine=1 채점 현황 www.acmicpc.net..
[백준] 11437번 : LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 해당 문제는 특정 정점2개의 공통 조상을 찾는 문제입니다. 우선 각 정점을 깊이우선탐색으로 각각의 깊이를 구합니다. 구하려는 정점 2개의 공통조상을 찾기위하여 두 정점의 깊이를 맞춰주는데, 자기자신의 조상이 깊이우선탐색을 하면서 기록되었기 때문에 자기자신의 조상을 참조하면서 올라갑니다. 두 정점의 깊이가 일치할경우 같이 조상으로 올라가면서 같은 조상인지 판별 하면 됩니다. 해당문제는 O(n*..

티스토리툴바