📚 알고리즘

[백준 11727] 2×n 타일링 2_dp(c++)

[문제] https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net [접근법] 다이나밍프로그래밍이란걸 보자마자 느낌..! 점화식을 찾아내기 위해 애썼음 [문제풀이] 고민하다가 찾은 점화식은 //홀수인경우 if (i % 2 != 0) { memo[i] = ((memo[i-1] * 2) - 1) % 10007; } else { memo[i] = ((memo[i -1] * 2) + 1) % 10007; } 근데 알고보니 원리가 따로있었다 경우의 수는 가로가1인 경우와, 가로가2인경우(2x2..

[백준 4485] 녹색 옷 입은 애가 젤다지?_다익스트라(c++)

[문제] https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈�� www.acmicpc.net [접근법] 다익스트라인지 몰랐지만 다익스트라로 풀었다! [문제풀이] 다익스트라는 하나의 정점에서 다른 모든 정점들의 최단경로를 구하는 알고리즘이라고 한다. 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단거리를 갱신해야 한다고 한다. bool 배열로 방문체크를 해주지 않아도 dist배열만으로 탐색을 한다. dist배열을 큰 값으로 초기화해두고 이동을하면서 a..

[백준 2146] 다리만들기_bfs(c++)

[문제] https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net [문제를 보자마자 든 생각] 보자마자 일단 bfs로 단지나누기를 해야겠다고 생각했다. 단지를 나눈 다음, 한 단지에서 이동하다가 다른단지를 만날때까지의 거리를 구한다음 그 거리의 최솟값을 구하면 될것이라고 생각했다. [문제풀이] 이중for문 돌면서 육지라면 좌표를 bfs(int x, int y)에 전달. bfs() 에서 너비탐색하면서 바다이면 true, 육지이면 false를 반환하게 함 ==>..

[백준 2096] 내려가기_dp(c++)

[문제] https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net [접근법] BFS랑 DP를 섞어서 접근할 생각으로 풀었다.. 풀다보니 메모리제한이 4MB인걸 보고 절망.. DP만으로 풀어야 한다는것을 깨달음..(친구의 도움을 받았다ㅠㅠ) [문제풀이] 구하고자 하는 값이 최대값과 최소값이므로, 2차원배열로 만들었다. (배열을 n x 3으로 나면 메모리 초과가 난다그래서 1x3 크기의배열을 만들어서 계속 갱신하는 식으로 풀었다.) dp1의 min, max값을 가지고 d..

[백준 6593] 상범빌딩_bfs(c++)

1.문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 www.acmicpc.net 2. 접근방법 3차원적으로 생각해야됐던 문제 동,서,남,북,상,하 상범이가 6가지 방향으로 움직이도록 한다. 나머지는 일반적인 bfs랑 똑같이 하면됐던 문제!!(단, xyz인덱싱 꼭 주의) 3. 문제풀이 상범이의 위치와, 움직인 시간 카운팅을 큐에 담는다. 테스트케이스를 한번에 받는 문제이므로 bool배열이나 기타 다른것들 초기화 꼭 시켜주기!!!!!!! 방문체크해가면서 second를 반환시켜..