빅맥좋아요

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 11779번 최소비용 구하기 2 를 풀었다. 최대 도시의 개수가 1000개이고 간선에 음수 가중치가 없어서 다익스트라 알고리즘을 사용했다. 다익스트라 알고리즘에 최단 경로 출력을 합치면 된다. 경로를 저장하기 위해 path_temp 배열을 사용했다. 어느 도시에서 오는지 저장하는 배열이다. index 1 2 3 4 5 value 0 1 1 1 4 예제의 경우 ..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 백준 2573번 빙산 문제를 풀었다. 빙산을 BFS나 DFS로 탐색하는 문제다. 빙산이 두 덩어리 이상으로 분리되면 BFS나 DFS 탐색을 두 번 이상 할 것이다. 그러면 year를 출력해주면 된다. 만약 빙산이 동시에 사라져서 탐색을 하지 않는다면 0을 출력하면 된다. 빙산이 녹는 과정에서 주의할 것은 next_map배열에 빙산이 녹는 값을 넣어두고 일괄적으로 map배열을 갱신시켜줘야 한다..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 백준 4485번 녹색 옷 입은 애가 젤다지?를 풀었다. 문제가 특정 노드에서 특정 노드까지의 최단 거리를 요구하고 간선에 음수 가중치가 없어서 다익스트라 알고리즘을 사용했다. 입력으로 주어진 2차원 배열을 다익스트라 알고리즘에 맞게 노드와 간선으로 바꿔준 후 다익스트라를 실행했다. 테스트케이스가 끝나면 항상 초기화를 해야한다. 정답을 맞추고 다른 사람들의 코드를 참고해보니 typ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 백준 1520번 내리막 길을 풀었다. 처음엔 DFS와 visited배열을 사용해서 백트래킹으로 문제를 풀었는데 시간 초과가 나왔다. 이것 저것 시도하다가 검색을 해보니 DP를 같이 사용해서 풀면 된다고 나와 있었다. DP를 사용하면 이미 계산했던 경로는 DP배열에서 값을 얻어오니까 훨씬 빠르게 문제를 해결할 수 있다. 아래는 전체 코드입니다. #include #include #include #inclu..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백준 1987번 알파벳을 풀었다. DFS와 백트래킹을 사용해서 풀었다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,-1,0,1 }; char board[20][20]; int usedAlphabet[26]; int r, c; int ..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 백준 10026번 적록색약을 풀었다. DFS를 두 번 실행하면 되는 문제다. 두 번째 실행이 적록 색약인 사람이 보는 구역의 수를 구한다. 첫 번째 실행 후 visited 배열을 초기화하고, grid 배열 중 'G' 값을 'R' 값으로 바꿔줬다. 그 다음 DFS를 실행하면 문제에서 요구하는 답을 구할 수 있다. 아래는 전체 코드입니다. #include #include #include #in..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 백준 1865번 웜홀을 풀었다. 가중치가 음수인 간선이 존재하고 문제에서 음의 사이클이 존재하는지 묻고있다. 벨만 포드 알고리즘을 사용해서 문제를 풀었다. 1번 노드와 연결되어 있지 않아도 음의 사이클이 존재하면 그 사이클을 통해 시간을 되돌리는 여행을 할 수 있다. 2022.04.22 - [알고리즘/PS] - [C++] 백준 11657 : 타임머신 따라서 위의 글에서 사용한 dist..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 백준 11657 타임머신을 풀었다. 출발 노드로부터 다른 모든 노드까지의 최단 경로를 구해야 하는 문제다. 간선의 가중치가 음수인 경우가 있어서 벨만 포드 알고리즘을 사용해야 한다. 벨만 포드 알고리즘을 사용해서 n-1번째 노드까지 최단 경로를 구했으면 다시 한번 모든 간선에 대해 비용 연산을 해서 음의 사이클을 찾아야 한다. 주의해야 ..

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 백준 2660번 회장뽑기를 풀었다. N이 50이하이고 모든 노드 간의 거리를 구해야해서 플로이드 와샬 알고리즘을 사용했다. 회원의 친구 관계를 모두 입력받고 플로이드 와샬 알고리즘을 수행하면 모든 노드 사이의 친구 관계가 구해진다. 조건문을 잘 설정해서 문제에서 요구하는 출력 값을 추가하면 된다. 아래는 전체 코드입니다. #include #include #include #include #inclu..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 백준 13913번 숨바꼭질 4 를 풀었다. 모든 간선의 가중치가 1이고 최단 거리를 찾는 문제여서 BFS 알고리즘을 사용했다. 처음엔 경로를 저장하기 위해서 100001개의 벡터 배열을 만들고 거기에 경로를 저장했는데 메모리 초과가 나왔다. 10만개의 벡터 배열에 평균 경로의 수가 10개라고 쳐도 100만개의 int이고 그러면 400메가의 크기가 된다. 게다가 벡..