공부하자

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 정리 그래프 만들고 경로 찾으면 되는 문제 생각 dfs 써서 그래프 연결 유무 확인을 하자! 방문했으면 1, 안했으면 0 출력 코드 #include #include using namespace std; int N, M; int graph[100][100]; bool visited[100]; void dfs(int start){ for(int i=0 ; i> N; for(int i=0 ; i graph[i][j]; } }..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 문제 정리 주어진 정보로 트리를 만들고 노드 사이의 거리를 출력하는 문제 생각 트리 문제가 너무 오랜만인데... dfs나 bfs 쓰면 될 것 같다 1. 그래프를 만든다 2. dfs로 노드 사이의 최단거리를 구한다 3. 출력 2차원 배열에 두 노드와 노드 사이의 거리를 입력받고 노드를 연결하고 (양방향) 그 후 dfs를 실행하는데 배열이 0이 아니라면 탐색을 하고 0이면 df..

https://www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 문제 정리 근손실 미친놈 근손실 정도 = 입력받은 두 근손실 정도 벡터(또는 배열) 2개의 합 합의 max값이 가장 적게 되는 max(==M)을 구해라! 생각 모든 경우의 수를 전부 구해서 가장 작은 M값을 구하면 될 것 같은데... 중요한 건 두 개를 고르는 경우를 조합으로 구해야 중복도 안나고! 좋을 듯 전에 썼던 조합으로 푸는 dfs를 사용하면 될 것 같다! 근데 이렇게 어려운 문제가 아니었나보다... 그냥 정..

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 문제 정리 1번째 영화 - 666, 2번째 영화 - 1666, 3번째 영화 - 2666 ... 이런식으로 n번째 영화의 666을 찾아라! 생각 근데 이해하는데 좀 시간이 걸렸는데 이렇게 생각하면 된다 666이 들어간 모든 숫자중에서 작은 순으로 배열이나 벡터를 만들어서 그것의 n번째 인덱스 찾기! 즉 666 1666 2666... 10666 이게 아니라 6661이 그 사이에 있다는 소리! 숫자를..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 정리 팀의 능력치 : 팀에 속한 모든 쌍의 능력치 Sij의 합 = Sij + Sji 두 팀의 능력치 차이의 최솟값을 구하기 생각 모든 경우의 수를 구해야 하긴 하는데… 1. 팀 구성 방식 - 중복이 허용되지 않으니까 순열로 구해야 하긴 함! 한 팀에 속하면 visited로 방문 표시를 하면서 방문한 팀이 n/2될 때 까지 방문하고! 이런 식 2. 팀의 능력치 비교 - 표에서 그대로 가져오는데 두 팀의 능력치 차를..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 정리 주어진 도시 정보에서 M개의 치킨집만 남기는데 치킨집과 집 사이의 총 거리가 가장 적게 되도록 M개를 골라서 도시의 치킨 거리의 최솟값을 구하면 됨! (각 집과 치킨집 사이의 거리의 총 합이 최소가 되는) 생각 브루트포스로 모든 M개를 골랐을 때마다 거리를 다 구해놓고 그 중 min을 구함! 근데 M개를 고르는 로직은 어떻게 하지? 모든 경우의 수를 구한다고 하면 ..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 정리 문자가 들어있는 보드 값이 주어지면 위치를 서로 바꿔 같은 행이나 열을 만들면 사탕을 먹을 수 있다. 먹을 수 있는 최대 사탕의 개수를 구하는 문제 생각 음... 근데 이동만 하면 3의 배수로 사탕이 없어지는 거 아닌가? 아닌가 문제 이해를 잘못했나... -> 먹으면 그 다음은 이동을 못하나봐 문제 이해!!!! 그냥 딱 한 번만 바꿨을 때 최대의 사탕을 구하면 된다! 상하좌우 4방향을 전부 검사할 것인지, 두 방향만 고정해서 반복되는 경우를 줄일 것인지 선택을 해야된다 그냥 중복되는 경우를 줄이기 위해 ..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 알고리즘 스터디 하는 친구가 가져온 문제가 백트래킹 문제들인데 브루트 포스 개념조차 기억이 안 나서... ㅠㅠ 개념 리마인드 겸 브루트 포스 문제의 대명사인 블랙잭 문제를 다시 풀어보고자 한다 브루트 포스의 종류 순차 탐색 - 선형 구조를 순차적으로 탐색 DFS(깊이 우선 탐색) - 비선형구조를 점점 더 깊게 깊이를 우선적으로 탐색하는 방법 BFS(너비 우선 탐색)..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 정리 하 머야 생각 벨트를 두 개를 만들어서 관리하는데 배열을 따로 쓸지 2차원 배열을 쓸지 고민이다 로봇 유무는 bool로 확인, 먼저 올라간 로봇 먼저 움직인다 -> 큐를 사용? 뭐가 일케 많음 하 넘 생각할 게 많아 코드 #include using namespace std; int main() { int N, K; cin >> N >> K; int durabilit..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제 정리 주어진 상자들의 크기를 고려하여 각 상자 안에 다른 상자를 넣을 수 있는 최대 개수! 자르긴가 생각 각 상자를 마지막으로 포함하는 최대 상자 개수를 저장하는 배열 만들기 -> 저번에 했던 dp랑 비슷한데? 똑같은 형식인듯!! 코드 #include #include using namespace std; int main() { int n; cin >> n; int box[n]; int dp[n]; f..