빅맥좋아요

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메가의 크기가 된다. 게다가 벡..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 백준 13549번 숨바꼭질 3을 풀었다. 처음엔 BFS를 사용해서 풀었다가 틀렸다. 간선의 가중치가 다른 경우엔 BFS를 함부로 사용하면 안된다는 것을 알았다. 우선순위 큐를 사용하지 않으면 dist배열 값에 더 큰 비용이 덮어씌어지는 것 같다. 그래서 다익스트라 알고리즘으로 문제를 해결했다. 아래는 전체 코드입니다. #include #include #includ..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 백준 12851번 숨바꼭질 2를 풀었다. BFS문제인데 도착하는 경로의 수까지 계산해야 한다. 목적지에 가장 빨리 도착하는 시간을 minTime에 기록해둔다. 목적지에 도착하는 경로에 대해서 시간이 minTime인지 확인한 후 cnt값을 올린다. BFS 함수가 종료되면 minTime에 동생을 찾는 가장 빠른 시간이 기록되고, cnt에 가장 빠른 시간으로 동생을..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 14502번 연구소 문제를 풀었다. 바이러스가 퍼지는 과정은 BFS 알고리즘을 사용했고 안전 영역을 구할 때는 전수 조사를 사용했다. 전수 조사 하는 과정에서 매번 초기화를 잘 해줘야 다음 시행에 영향이 없다. 아래는 전체 코드입니다. #pragma warning(disable:4996) #include #include #include #include #include #include using names..