전체 글102 [C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 구현! 사실 원래의 BFS를 이용한 최단거리 알고리즘에서 조금만 추가하면 쉽게 풀 수 있는 문제이다. 여기서 중요한 것은 tuple안의 4개의 원소를 집어넣어 각각 x좌표, y좌표, 벽을 뚫고 지나갔는지에 대한 여부, 현재까지의 거리를 저장해야 하는 것이다. 또한 중요한 것이 visit 배열인데 기존의 2차원으로만 표현하면 안되고 3차원으로 표현하여 벽을 뚫고 지나갔는지에.. 2023. 9. 18. [C/C++] 백준 11444: 피보나치 수 6 (점화식 풀이) https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 맨 처음에 다른 문제처럼 DP로 풀려고 했지만 너무 범위가 커 메모리초과가 나왔다. 구현!! 이 문제와 같이 입력의 수가 과도하게 크고 DP를 사용해야할 상황일 때 (1.)항상 점화식을 2개로 나눠서 풀 수 있도록 생각을 해야한다. 특히 (2.)한번 지난간 곳을 저장해둬서 한번 지난 곳은 다시 못 지나가게 만들어 시간을 줄여야할 필요도 있다. 1) 그래서 점화식을 나누기 위해 머리를 굴렸지만 결국 두개로 나누지 못했다. 사실 거의 다 오긴 했지만 마지막에... 그렇게 다른 .. 2023. 9. 17. [C/C++] 백준 11725: 트리의 부모 찾기(vector 이용) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 맨 처음에 문제에서 트리의 루트를 1로 둔다는 조건을 확인 못해서 맨 처음에 해맸다.. 구현!! 사실 간단하게 풀이가 가능하다. 이차원 백터 vectorv1[100001]를 선언하여 각 노드와 연결되어 있는 노드를 뒤에 추가해주면 된다. 이때 무엇이 부모이고 자식 노드인지 모르기 때문에 v1[tmp1].push_back(tmp2); v1[tmp2].push_back(tmp1); 두번 다 해줘야한다. 그 다음에는 queue를 이용하여 push와 pop을 해주면 .. 2023. 9. 17. [C/C++] 백준 16236: 아기 상어 (BFS, 반례 및 주의점!) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 사실 BFS로 돌면서 풀면되는 아주 간단한 문제인줄 알았지만 생각보다 해야할게 많아서 굉장히 고민을 많이 했다. 무려 3시간만에 겨우 풀었다... 문제 해설보다는 내가 실수했던 부분 위주로 한번 써보려고 한다. 주의해야할 점! 1. 지나가는 것과 먹을 수 있는 경우 문제에 그대로 나와있다싶이 자신의 크기보다 큰 물고기가 있는 칸을 제외한 칸은 모두 지나갈 수 있고 자신의 크기보다 작은 물고.. 2023. 9. 17. 이전 1 ··· 3 4 5 6 7 8 9 ··· 26 다음
