분류 전체보기

[python3] 백준 1937 풀이 (욕심쟁이 판다, DFS, DP)

어떤 문제이던 DP가 들어가면 난이가 확 올라가는것 같다. 이 문제는 처음에는 DFS로만 풀었다. 각 좌표별로 DFS를 실행했고 DFS에 시간복잡도에 N*N만큼 곱해져서 상당히 시간복잡도가 컸다. 그래서 시간초과가 났고 새로운 풀이를 찾아야 했다. 우선 고수들의 예시를 보자 위와 같이 대나무가 있다고 가정한다. 우리는 (0,0)부터 탐색을 시작한다. 그렇다면 자신보다 큰 값으로 최대한 이동할때의 DFS를 생각해본다. 그렇다면 DP배열은 아래와 같이 설정된다. 그러면 결국 DFS한번 만으로 각 좌표에서의 최대 일 수를 구할 수 있다. 그렇다면 DP가 계산되지 않은 (1,0)을 살펴본다. 그러면 이미 DP(0,0)은 최댓값을 가지고 있으므로 2의 값을 가져와서 1을 추가한다면 DFS없이 최대 일 수를 구할 ..

[py3] 백준 2573 풀이 (빙산, DFS, 그래프)

이 문제는 일반적인 그래프에서 집합 개수 찾는 것과 시간마다 달라지는 그래프를 적용하여 푸는 문제이다. 여기서 중요하다고 느낀점은 빙하가 물과 닿는 개수대로 빙하가 녹게 되는데 녹일때 조심해야한다. 예를 들어 0 0 0 0 3 5 0 0 0 이라고 한다면 내년에는 0 0 0 0 0 3 0 0 0 이 되어야한다. 그러나 코드를 잘못짜면 0 0 0 0 0 2 0 0 0 이 될수 있다. 그래서 나는 filter 배열을 만들고 빙하별로 인접한 방향의 수를 구하고 제거하는 방식으로 코드를 구현했다. n,m = map(int , input().split()) M = [] big = 0 for _ in range(n): tmp = list(map(int, input().split())) M.append(tmp) fr..

[c++] 백준 14476 (최대공약수 하나빼기, 누적합, 최대공약수, 유클리드 호제법)

최대공약수를 구하는 함수는 수는 유클리드 호제법을 이용하여 정의할 수 있다. gcd(36, 8) => gcd(8, 36%8) ....gcd(36,8) => gcd(8,4) => gcd(4,0) => 최대공약수는 4가 된다. int gcd(int a, int b){ while(b != 0){ int r = a % b; a = b; b = r; } return b; } 이를 활용하여 누적합을 적용해 본다. number 8 12 24 36 48 L to R 8 4 4 4 4 R to L 4 12 12 12 48 각 L to R과 R to L을 구한 이유는 k수를 제외하고 최대공약수를 구할때 O(n) 시간복잡도로 구하기 위해서이다. 즉, k=8 , 최대공약수 = RL[1] k=12, 최대공약수 = gcd(LR[..

백준 1202 보석도둑 c++ 풀이 (priority queue, vector, 우선순위 큐)

이 문제는 priority queue를 활용한 문제이다. 우선 보석의 (무게, 값) 과 가방의 (무게) 가 주어진다. 여러개가 주어지는데 이때 가장 큰 가치를 가질 수 있도록 가방에 보석을 하나씩 담는다.(단 가방에 하나의 보석만 담을 수 있다.) 가장 작은 가방에 들어갈 수 있는 보석 중 가치가 큰 것을 담는다. 다음으로 큰 가방에 담을 수 잇는 보석 중 가치가 가장 큰 것을 담는다. 이후 가방이 없을 때까지 반복한다. 그렇다면 결국 가방은 순서대로 사용하면 되고, 보석도 가방에 들어갈 무게만큼 순서대로 대조하여 가방에 담으면 된다. 그래서 보석과 가방을 무게 순으로 정렬한다. 이후에 pq에 보석을 넣어서 가장 가치가 높은것을 꺼내어 가방에 담는다. 1. 보석과 가방을 무게순으로 정렬 2. 가장 작은 ..

백준 3055 C++ 풀이 (탈출, BFS)

이번에는 c++로 BFS문제를 풀어보자. 사실 엄청 어렵지는 않은 문제였다. 알고리즘을 어떻게 사용해서 풀지 쉽게 이해할 수 있었다. 그러나 문제는 c++!!!!! 맨날 파이썬으로 풀다가 c++을 접했더니 아주 신경써야할 게 한 두개가 아니다. 괜히 알고리즘 고수들의 언어가 아니었다. 준나 어렵다. 문제는 간단하다. 귀여운 고슴도치가 비버굴로 피난을 가는데 걸리는 시간을 구한다. 단, 물이 넘치게 되는 조건이 있는데 시간이 갈수록 물이 주변 지역으로 퍼진다. 이를 피하며 굴로 이동하면 된다. 가장 빠른 길을 찾는 것이기 때문에 BFS를 선택하면 된다. 또한 고슴도치는 물이 넘치는 지역으로 이동하면 안되기 때문에 물을 먼저 이동시키고 고슴도치를 이동시키면 된다. 1. 땅굴의 위치, 물의 위치, 고슴도치의 ..

[c++] ios::sync_with_stdio(0), cin.tie(0) 는 왜 쓰는 걸까?

ios::sync_with_stdio(0)는 c의 stdio와 cpp의 iostream을 동기화 시켜준다. 문제는 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생한다. 따라서 이러한 동기화를 비활성화 시켜주기 위해 ios::sync_with_stdio(0)으로 선언해준다. cin.tie(0)는 cin과 cout의 묶음을 풀어준다. 따라서 순서가 사라진다. 알고리즘을 풀때는 화면에 바로 보이는 것이 중요하지 않기 때문에 cin과 cout의 묶음을 풀어주어 더 빠르게 만들 수 있다. 아래는 고수님의 상세링크 https://jaimemin.tistory.com/1521

[c++] \n 와 endl 중에는 \n가 더 빠르다.

이번에 삼성SDS알고리즘 특강을 듣게 되며 C++을 활용한 코딩을 공부하고 있다. 강사님이 endl보다는 "\n"가 더 빠르다고 했다. endl의 경우에는 내부에서 flush()를 포함하기 때문에 출력버퍼를 지워주는 과정을 포함한다. 그렇다 보니 출력시에 "\n"보다 속도가 느려진다. 타 블로그를 확인해보니 "cout

백준 10026 파이썬 풀이 (적록색약, DFS)

이번 문제는 간단하다. 그냥 같은 영역이 얼마나 되는지 찾아내는 것이다. 1. 일반인을 위한 Map, 적록색약인 사람을 위한 Map('G'와 'R'를 동일하게 보는 사람) 2. DFS를 유연하게 만들어서 시간을 줄인다. n = int(input()) NMap = [] WMap = [] for i in range(n): tmp = list(input()) NMap.append(list(tmp)) for j in range(n): if tmp[j] == "G": tmp[j] = "R" WMap.append(tmp) def DFS(x,y, Map): s = [(x,y,Map[x][y])] Map[x][y] = 0 dx = [0,0,1,-1] #동서남북 dy = [1,-1,0,0] while s: x,y,z =..