swanzzz 님의 블로그

[오늘의 문제]https://www.acmicpc.net/problem/14500[오늘의 학습 키워드] DFS구현브루트포스 알고리즘1. 문제설명 보드의 크기 N, M이 주어질 때 해당 보드에 테트로미노 블록 1개만 놓아서 최대의 크기를 가지는 경우를 구하는 문제 입니다. 테트로미노는 위 그림처럼 5개의 모양이 존재합니다. 각 모양을 적절히 회전하거나, 뒤집어서 최대의 크기를 가지는 경우 1가지를 구해 그 크기를 출력하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 512MB4 ≤ N, M ≤ 500둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수..

[오늘의 문제]https://www.acmicpc.net/problem/9466[오늘의 학습 키워드]DFS깊이 우선 탐색그래프 탐색그래프 이론구현1. 문제설명 학생들이 각자 원하는 팀이 있습니다. 위 그림에서 1번 학생은 3번 학생과 팀을 원하고 3번 학생은 혼자 팀을 하기 원합니다. 이 경우 3번 학생이 3번을 선택하였기 때문에 3번 학생혼자 프로젝트를 실시하고 1번 학생을 팀을 이루지 못했습니다. 2번의 경우 1번을 원하지만 1번은 이미 3번을 원했기에 2번도 팀을 이루지 못합니다. 3번의 경우 팀을 이뤘고 4번은 7번을 7번은 6번을 6번은 4번을 원하고 있습니다. 각각 원하는 사람이 겹치지 않고 6번이 4번을 선택했을 때 4번은 다시 7번을 선택하는 사이클이 완성되었으니 이 3명은 팀을 이뤘습니..

[오늘의 문제]https://www.acmicpc.net/problem/1520[오늘의 학습 키워드]DP, DFS, 구현1. 문제설명 지난 시간 해결한 문제와 비슷한 문제 입니다. 지도 안에서 목적지에 도착 가능한 경로를 찾는 문제인데 이동은 4방향으로 이동이 가능하고, 반드시 내리막길로만 가려고 합니다. 목적지에 도착한 경우 그 경로의 개수를 출력하는 프로그램을 작성해야 합니다.[제한사항]시간 제한 2초메모리 제한 128MBM과 N은 각각 500이하의 자연수각 지점의 높이는 10000이하의 자연수2. 접근방식1890 점프 문제를 해결할 때 사용한 방식과 비슷하게 접근해 보았습니다. 현재 위치를 기준으로 다음 이동 가능 경로를 탐색하는데 4방향 중 지도를 벗어나지 않고, 내리막 길 인 경우 DP 테이..

[오늘의 문제]https://www.acmicpc.net/problem/24479[오늘의 학습 키워드]깊이 우선 탐색, 정렬1. 문제설명정점의 수 N, 간선의 수 M, 시작 정점 R이 주어지고다음 M개의 줄에 간선 정보 u, v가 주어집니다.간선은 가중치가 1인 양방향 간선입니다. 이때 간선을 깊이 우선 탐색으로 방문할 때 그 순서를 출력하는 프로그램을 작성해야 합니다. 또 인접한 정점이 2개 이상이라면 오름차순으로 방문 처리를 실시해 줍니다.[제한사항]시간 제한 1초메모리 제한 512MB5 ≤ N ≤ 100,000 1 ≤ M ≤ 200,000 1 ≤ R ≤ N 1 ≤ u 2. 접근방식주어진 조건대로 그대로 깊이 우선 탐색으로 구현하면 됩니다. 1. 양방향 간선이므로 주어진 간선의 정보 u, v를 ..

[오늘의 문제]https://www.acmicpc.net/problem/2206[오늘의 학습 키워드]BFS1. 문제 설명 N x M 행렬의 미로를 탈출하는 문제입니다. 0은 이동이 가능한 길1은 이동이 불가능한 벽을 의미하는데 벽은 1번 부술수 있습니다. 모든 경로중 가장 짧은 경로를 찾아서 이동 시간을 출력하는 문제입니다.만약 탈출이 불가능한 경우 -1을 반환합니다.[제한 사항]시간 제한 2초메모리 제한 192MB1 ≤ N ≤ 1,0001 ≤ M ≤ 1,0002. 접근 방식 전형적인 BFS 문제 같습니다. 벽을 부술수 있을 때 이동 가능한 모든 경로를 queue에 넣어서 다음 위치를 탐색합니다. 그 중 벽을 부숴야 하면 부수고 이동한 뒤 그 상태를 queue에 넣어서 종료까지 탐색을 실시합니다. 한가지..