목록class 4 (6)

1일1알

백준 17070번 파이프 옮기기 1 C++

파이프를 오른쪽으로 옮길 때에는 현재 위치에서 오른쪽 한 칸이 비어있어야 하고 아래로 옮길 때에는 아래에 한 칸이 비어있어야 한다. 대각선으로 옮길 때에 주의해야할 점이 있는데, 대각선으로 간 칸과, 그 위칸과 왼쪽 칸 모두 비어있어야 한다는 것이다. 문제에도 비어있어야 할 칸이 색으로 칠해져있다. 나는 구조체를 만들어서 파이프의 위치와 현재 상태(오른쪽, 대각선, 아래 중 하나) 정보를 저장하고 그 구조체를 큐에 넣어서 bfs방식으로 해결하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; str..
알고리즘 2021. 10. 22. 12:16
백준 12851번 숨바꼭질2 C++

bfs로 풀 수 있는 문제인데 특이한 점은 가장 빠른 시간만 구하는 게 아니라 그 방법이 몇 가지인지까지 구해야 한다. 최초 도달했을 때 시간을 구하고 그 시간과 같은 시간에 도착 할때마다 Count를 증가시켜주면 된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector visited(100001, false)..
알고리즘 2021. 10. 20. 12:46
백준 16953번 A->B (C++)

bfs로 문제를 해결하였다. 초기 cnt=1 처음 큐에 pair로 (A, cnt)을 넣고 (A * 2, cnt + 1) 와 (A * 10 + 1, cnt + 1)을 bfs로 탐색하면서 A의 값이 B의 값과 같아지면 cnt를 출력하는 방식으로 해결하였다. 같은 숫자를 또 방문하는 것을 방지하기 위해 탐색 시간 복잡도가 O(1)인 unordered_set에 방문한 값을 넣어줘서 중복을 방지하고, A * 2나 A * 10 + 1이 B보다 커지면 큐에 넣지 않는 식으로 구현하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lo..
알고리즘 2021. 10. 19. 10:45
백준 11660번 구간 합 구하기 5 C++

dp 테이블을 이용하여 누적 합을 저장해서 풀 수 있는 문제이다. 예제의 숫자들을 각 행마다 누적 합을 저장하여 저장한다. (2,2)부터 (3,4) 까지의 합은 이 부분의 합을 구하면 되기 때문에 dp[2][4]-dp[2][2-1] + dp[3][4]-dp[3][2-1] = (14 - 2) + (18 - 3) = 27 이렇게 구할 수 있다. 이것을 코드로 나타내면 #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin...
알고리즘 2021. 10. 18. 13:19
백준 11725번 트리의 부모 찾기 C++

그래프, 트리 관련 문제이다. 우선 (n+1)*(n+1) 행렬을 만들어서 트리를 인접 행렬을 통해 나타내는 방식을 생각해볼 수 있다. 노드가 양방향으로 연결되어있기 때문에 (1,6)을 받으면 (1,6)과 (6,1) 모두 저장한다. 하지만 이런 방식으로 풀면 비어있는 공간도 모두 탐색하면서 시간이 오래 걸려 시간 초과가 날 것 같아서 다른 방법을 생각해보았다. 2차원 벡터를 사용하여 노드와 연결된 노드만 저장하는 방식이다. vector[1] : 4, 6 vector[2] : 4 .... 이런식으로 만들었다. 우선 루트가 1이라고 했으니 큐에 1을 넣고 시작한 뒤 노드 r을 1로 저장하고 pop을 한번 해준다. 그리고 vector[r] 을 탐색하면서 원소가 아직 방문이 되지 않았을 경우에 해당 원소를 큐에 ..
알고리즘 2021. 10. 17. 12:39
백준 9465번 스티커 C++

다이나믹 프로그래밍 bottom-up 방식으로 풀 수 있는 문제이다. 우선 두 가지 경우가 있다. 1. 왼쪽 위에서 시작하는 경우 2. 왼쪽 아래에서 시작하는 경우 1번의 경우를 예를 들어 살펴보면 한 칸 떨어진 대각선을 선택하는 경우와 두 칸 떨어진 대각선을 선택하는 경우로 나눌 수 있다. 다른 어떤 곳을 선택하더라도 결국 이 두 가지로 나뉜다. (100을 선택: 50->50->100, 20을 선택: 50->50->20 or 50->70->20, 10을 선택: 50->50->100->10) 위 경우들을 살펴보면 결국 위의 두 가지의 경우들의 조합으로 만든 선택임을 알 수 있다. 마지막 스티커까지 도달했을 때 1번의 경우와 2번의 경우 중 큰 값이 답이 된다. max(dp[0][n], dp[1][n]) ..
알고리즘 2021. 10. 16. 13:09
이전 Prev 1 Next 다음