마탁이의 개발 블로그

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 미로 탐색을 살짝 응용한 문제 풀면서 주의했던 점은 미로 탐색은 100이 MAX_SIZE 였으나, 이 문제는 1000 이라 vector 사용해서 구성. 또한, 같은 날짜에 모든 '1'의 값을 가진 곳에서 상,하,좌,우 확장이 된다. 176ms 의 시간이 걸렸지만 80ms도 있는 것을 봐선 더 개선할 수 있다. 코드 더보기 #include #include #include // def #define..

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 탐색의 과정에서 최단 거리를 구하는 문제 -> BFS 인접 행렬을 사용하여 해결을 할려고 하니 메모리 초과가 나온다. (답은 출력됨) 미로의 입력의 경우 배열을 이용[101][101]하여 사용하였고 std::vector와 std::find()를 이용하여 방문여부를 검사하니 메모리 초과는 나오지 않으나 68m의 시간이 걸렸다. 채점현황에서 0ms가 소비되는 코드가 많은 것을 보아 효율을 높일 수 있는 (?) 코드로 수정이 필요하다. 코드 ..

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이전 2667과 유사한 문제라고 생각되어 같은 방식으로 해결. BFS 탐색을 이용해 문제를 해결 코드 더보기 #include #include #include #include // def #define BOARD_MAX_SIZE 50 #define POS_PAIR std::pair // method bool CheckingValid(int x, int y, int X, int Y); void BFS_Search(int map..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 한국 올림피아드 초등부 문제 역시나 DFS를 초등부 문제에 있다는 것에 신기했지만 정답률도 낮은 것에 신기했음.(다른 분들이 단계별로 풀어보기에 신경안쓰는 것일까.) 풀이 주어진 입력을 인접행렬로 생각해 해결 방문하지 않은 1이 나올때마다 BFS 함수 사용 처음에 결과값을 std::set에 저장해서 정렬 과정의 코드를 생략할려고 했었으나 생각해보니 중복값은 std::set에 저장이 안됨 -> std::vector ..

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 한국정보올림피아드 지역본선 2004 초등부 문제 단계별로 풀어보기 대학교때 코딩 배운 나와 달리 초등부 문제가 DFS 탐색을 이용하는 것은 조금 신기하긴 했다. 풀이 1260 - DFS와 BFS에서 인접행렬을 사용한 DFS를 std::vector를 이용한 인접리스트로 구현하여 탐색하도록 했다. 확실히 속도와 공간 복잡도에 이점은 있다. (문제 난이도가 쉬워 구현도 쉬웠다.) 코드 더보기 #include #includ..

www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS를 이용한 그래프 탐색 문제 아주 오래전에 C++를 이용해 해결하였으나, 다시 풀면서 시간이 꽤 걸렸음. 다른 사람들은 0 ms 시간도 있어 시간을 줄일려고 했으나 이전(28ms)보다 못 한 결과를 보였음 인접 리스트를 이용해 풀면 더 빠른 시간내 문제 해결이 가능할 것으로 보임(현재는 인접 행렬로 풀어봄) 코드 더보기 #include #include #inc..

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 삼성 SW 역량 테스트 문제. 최대 이익을 구하는 문제와 유사함. 브루트 포스와 다이나믹 프로그래밍을 이용할 수 있음 브루트 포스를 이용할 경우 : O(N^2) 다이나믹 프로그래밍을 이용할 경우 : O(N) 풀이 하루마다 입력을 받으면서 다음날과 현재의 최대값을 비교하여 다음날의 값이 현재 보다 작다면 현재의 값으로 변경 상담일이 끝나는 날의 다음날 값(dp[n+time])이 (현재 dp[n] + price) 보다 작다면 dp[n+time]을 치환. 느낀점 아직도 dp 문제는 점화식이나 bottom-top, top-bottom 등 여러 가지 방법으..

www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 재귀를 이용하여 하노이 탑의 총 이동 횟수와 이동 과정을 출력. A, B, C 3개의 기둥과 N개의 원판이 있을 때, 규칙을 지키며 A to C로 원판을 그대로 옮기는 문제. 풀이 작은 원반 n-1 개를 'A'에서 'B'로 이동 큰 원반 1개를 'A' 에서 'C' 로 이동 작은 원반 n-1 개를 'B' 에서 'C' 로 이동 느낀점 실질적으로 풀이를 아래와 같이 생각하지 못 해 구글링을 하였고, 이해..