백준문제풀이
7562번-나이트의 이동
문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 접근방법 1) 접근 사고 1. 나이트의 이동 좌표에 대한 설정값을 구해줍니다. 2. bfs 탐색을 통해 나이트의 이동에 대한 탐색을 시작합니다. 3. 이때 1초당 걸리는 탐색의 경우의 수는 탐색을 진행할 때 queue의 크기와 같으므로 탐색을 시작할 때 큐의 크기만큼 탐색을 진행하고 시간을 1증가 시켜줍니다. 2) 시간 복잡도 O(V+E) 3) 실수 4) 배운점 5) PS 다른 문제풀이를 보니..
11725번-트리의 부모 찾기
문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근방법 1) 접근 사고 깊이 우선 탐색에서 가장 깊은 탐색을 진행한 뒤 재귀가 끝난 경우를 노드의 현재 번호값에 저장하면 되는 문제였습니다. 2) 시간 복잡도 3) 실수 4) 배운점 5) PS 정답 코드 #include using namespace std; int n; const int MAX = 100005; vector edge[MAX]; bool visited[MAX]; int ret[MAX]; void DFS(int cur) { visited[c..
2606번-양
문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 접근방법 1) 접근 사고 1. DFS 탐색을 통해 1번 바이러스와 연결된 간선들을 탐색해주면 됩니다. 2. 바이러스의 숙주인 1번은 제외하고 출력해야 합니다. 2) 시간 복잡도 3) 실수 4) 배운점 5) PS 정답 코드 #include using namespace std; int n, m, ans; const int MAX = 105; vector board[MAX]; bool visited[M..
3184번-양
문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 접근방법 1) 접근 사고 1. 울타리가 아닌 영역을 탐색한다. 2. 울타리가 아닌 영역의 양과 늑대수를 측정한다. 3. 양이 늑대수보다 클 경우에는 양의 결과를 반환하는 변수에 양의 수를 더해주고 아닌 경우에는 늑대의 결과를 반환하는 변수에 늑대의 수를 더해준다. 2) 시간 복잡도 O(v + e) 3) 실수 4) 배운점 5) PS 정답 코드 #include using namesp..
4963번-섬의 개수
문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 접근방법 1) 접근 사고 1. 섬을 8가지 방향으로 탐색을 합니다. 2. 탐색을 하면서 방문한 섬은 visited배열을 사용해서 방문 체크를 진행해줍니다. 3. 시도한 BFS 횟수가 섬의 개수를 의미하는것을 알 수 있습니다. 2) 시간 복잡도 O(V + E) 3) 실수 r과 c의 위치가 바껴서 나온다. 문제 설명이 너무 불친절한거 아닌가.. 예제를 다시 보고 입력 부분이 잘못되었다는것을..
11724번-연결 요소의 개수
문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 접근방법 1) 접근 사고 1.연결 요소의 개수를 구해주면 되기 때문에 방문한 노드 지점을 visited 배열을 사용해 체크해줍니다. 2. 방문한 지역은 visited를 사용해 제외해주었기 때문에 DFS 시도횟수의 의미가 전체 연결 개수의 의미를 의미하므로 DFS 시도 횟수를 출력해줍니다. 2) 시간 복잡도 O(V + E) 3) 실..
1012번-유기농배추
문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 접근방법 1) 접근 사고 문제를 읽고 해석해보면 배추가 있는 구역인 1부분을 탐색하면 해결되는 문제였습니다. 2) 시간 복잡도 O(V + E) 3) 실수 fill을 사용할 때 열만 +1하면 되는데 행까지 +1을 해서 outofmemory오류가 발생하였다. 4) 배운점 5) PS 정답코드 #include using namespace std; int t, r, c, ea; const int MAX = 50;..
12100번-2048(easy)
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 접근방법 1) 접근 사고 1.상하좌우로 기울이는 모든 경우를 DFS로 탐색 2.이때 탐색이 5가 되면 배열중 가장 큰 값을 찾고 비교해준다. 2) 시간 복잡도 O(n ^ 2) 3) 실수 1. 113번째 줄에서 처음에 memcpy를 사용하여 배열의 복사와 갱신을 진행해주려고 하였다. 그러나 DFS 재귀함수에 매개변수 배열을 넘겨서 재귀함수 상태에서 배열의 사이즈는 ..
20058번-마법사 상어와 파이어스톰
문제 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 접근방법 1) 접근 사고 1. 입력받은 배열들을 2^L * 2^L 로 나눈다. 2.이후 모든 분리된 격자를 시계 방향으로 90도 회전한다. 3.Board에 모든 얼음들을 돌면서 인접해 있는 얼음이 3개가 아닌 경우는 1씩 감축한다. 4.이중 반복문을 활용한 얼음의 총합값과, BFS를 활용한 가장 큰 얼음 덩어리를 탐색하여 정답을 반환한다. 2) 시간 복잡도 O(n ^ 3)..
20057번 - 마법사 상어와 토네이토
문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 접근방법 1) 접근 사고 태풍에 대한 구조체를 두어 태풍의 이동을 계산하기 쉽게 작성했다. 1. 태풍이 이동한다. 2. 이동한 위치에 모래가 존재한 지 파악한다. 모래가 있을 경우 태풍의 구조체 중 c.perBoard에 담긴 수치 값을 활용하여 비율에 맞게 모래를 전파한다. 없을 경우 다음 탐색으로 넘어간다. 3. 범위가 초과하여 합계에 더 해줘야 하는지 bo..
20055번-컨베이어 벨트 위의 로봇
문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 주어진 그대로 구현하면 되는 문제엿다. 1.컨베이어벨트와 로봇들을 한 칸씩 회전시킨다 2.로봇들만 앞으로 한 칸 전진한다. 이때 내리는 위치에 가면 로봇이 사라진다.(내린다는 표현이 애매한거 같다. 컨베이어 벨트 밑으로 로봇을 내린다는 의미로 해석해서 푸는데 어려움이 있었다.) 3.첫 번째 위치에 가중치가 있고 로봇이 없다면 로봇을 둔다..
19238번-스타트택시
문제 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 접근방법 1) 접근 사고 1. 내가 태울 승객을 BFS 탐색으로 정한다, 이때 소모한 가스값은 갱신해준다. 2. 태울 승객의 위치에서 도착지까지 BFS 탐색을 한다, 이때 소모한 가스값은 갱신해준다. 2) 시간 복잡도 O(V + E) 3) 배운 점 여러 번 시도한 문제이다. 테스트 케이스는 다 통과하나 문제가 자꾸 틀렸습니다가 나와서 힘들었다 이에 대해..
19237번-어른 상어
문제 https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 접근방법 1) 접근 사고 1. 상어의 이동 1-1. 상어의 방향에서 냄새가 없는 경우 1-2. 냄새가 없다면 상어의 방향에서 냄새가 있는 경우 2.냄새 1씩 감축 2.현재 상어의 위치에 상어의 냄새 추가 의 알고리즘인데 사실 특별한 알고리즘도 없고 그냥 구현하면 되는 문제였다. 그러나 디버깅 단계에서 런타임 오류를 잡아내지 못해서 시간이 정말 오래..
19236번-청소년상어
문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 접근방법 1) 접근 사고 런타임 에러 때문에 거의 3일을 고민하면서 푼 문제라서 죽을 때까지 잊지 못할 문제인 거 같습니다. 알고리즘의 단계는 밑에 단계로 이루어져 있습니다. 1. 입력값을 받는다. 2. 물고기를 이동시켜준다. 이때 죽은 물고기의 방향은 -1로 표시한다.(모든 물고기를 각 단계마다 움직여야 하는데 -1 물고기는 죽은 물고기 이므로 움직이지 않는다.) 3. 상..
17779번-게리멘더링2
문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 접근방법 1) 접근 사고 전체적인 로직은 각 구역의 가능한 인덱스 범위를 먼저 구합니다. 그리고 완전탐색을 통하여 각 구역의 범위들과 일치하는 조건을 통하여 구역별로 값을 구합니다. 이후 정렬을 하여 가장 큰 값과 가장 작은 값을 마이너스 연산을 한 뒤 최소값 갱신을 진행해주면 됩니다. 더 자세한 설명은 주석 첨부하였습니다. 실제 시험 문제로 나온다면 식 정리를 하다가 실수해서 못 풀거 같습니다...
17142번-연구소3
문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 접근방법 1) 접근 사고 바이러스의 경우를 조합으로 구현하여 바이러스가 퍼질 수 있는 모든 경우의 수를 BFS를 사용하여 탐색하였습니다. 주의해야 할 점은 BFS를 사용하여 시간을 측정할 때 0의 갯수를 cnt해서 바이러스가 모두 퍼져있는지의 유무의 형태로 작성하신다면 중간에 탐색을 통한 cnt 갯수가 0의 모든 갯수와 일치한 경우 탐색을 종료하는 조건절을 추가하셔야 합니다. 그렇지 않으면 모두 탐색..
17140번-이차원 배열과 연산
문제 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 접근방법 1) 접근 사고 까다로운 구현 문제였습니다. 자세한 로직은 주석으로 첨부하였습니다. 2) 시간 복잡도 O(N^2) 3) 배운 점 특별히 없는거 같습니다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40..
17143번-낚시왕
문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 접근방법 1) 접근 사고 구현 문제 였습니다. 상어를 잡는 구현은 쉬우나 상어의 이동 부분을 구현하는 것이 까다로운 문제였습니다. 나머지 위치를 통해서 위치를 구해야겠다는 생각은 했으나 왼쪽 벽에서 떨어진 위치와 오른쪽 벽에서 떨어진 위중 어느곳에서 위치를 정해야 하는지 구현하는데 시간을 많이 소모했습니다. 2) 시간 복잡도 O(N^3) 3) 배운 점 이런 이동 기법은 코..
17144번-미세먼지 안녕
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 접근방법 1) 접근 사고 특별한 알고리즘이 없지만 인덱스의 값 설정에 주의해서 풀어야 하는 문제였습니다. Spread, upper_move, Bottom_move 3가지 함수로 각 동작들을 정의하여 문제를 해결하였습니다. 2) 시간 복잡도 O(N^2) 3) 배운 점 람다식을 사용할때 캡쳐영역을 전체로 사용할 때 밖에 있는 변수와 이름이 같은 것을 사용하면 안된다는것을 알게 되었습니다. 만약..
16236번-아기상어
문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 접근방법 1) 접근 사고 개인적으로 구현이 어려웠던 문제였습니다. 상어가 탐색하는 경우를 q 배열에 넣어주었고 경로중 문제에서 주어지는 최적의 조건을 탐색하기 위해 우선순위 큐(코드에서 pass 변수)를 사용했습니다. 물고기를 먹을 수 있는 경우도 문제에서 최적의 조건이 주어지므로 우선순위 큐를 한 개 더 사용(문제에서 pq)하여서 이동한 경우를 다시 q배열에 넣어주고 반복하였습니다...
16235번-나무재테크
문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 접근방법 1) 접근 사고 그대로 구현하면 되는 문제였습니다. 저는 봄을 구현하는 과정에서 잘못된 구현으로 시간을 많이 낭비하였습니다. 양분을 먹고 새로 추가해주는 과정에서 새로운 배열에 담은 뒤에 기존 배열을 갱신해야하는데 그렇게 하지 않고 같은 배열에 두고 값을 넣어서 죽은 나무, 갱신 전에 나무의 값이 남아있어서 틀린 답이 나왔습니다. 이 부분을 제외한 계절의 구현은 정확..
16234번-인구이동
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근방법 1) 접근 사고 구현량이 많은 구현 문제였습니다. 갱신 이후에 갱신을 할 것인지 말 것인지 구분하는 부분을 작성하는 부분이 핵심 구현입니다. 처음에 visited로 갱신 부분과 중복 부분을 같이 사용하였으나 값을 갱신할 때 값이 중복되는 부분이 생기는것을 알았습니다.(국가와 국가가 i, j번 타이밍에 연합되는 것을 i, j + 1 때에도 가져가는 실수를 저지름) 그래서..
15686번-치킨배달
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근방법 1) 접근 사고 문제를 요약하면 치킨집을 m개의 경우를 선택했을때 각 집마다의 치킨 거리가 최소가 되는 것들의 합을 구하는 문제였습니다. 저는 치킨이 가능한 경우의수 m개를 numArr에 넣어주고 m - chicken.size()의 개수만큼 0을 넣은뒤 next_premutaion을 통해 모든 경우의 수를 만든뒤 집과의 거리를 연산하였습니다. 2) 시간 복잡도 ..
15685번-드래곤커브
문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 접근방법 1) 접근 사고 단순 구현 문제인데 "드래곤 커브의 회전을 어떻게 구할 것인가?"라는 명제가 핵심인 문제였습니다. 처음에는 재귀함수로 구현을 할 생각을 했었는데 0 ~ n 세대 순으로 증가하기 때문에 각 방향에서 방향의 크기만큼 한 번더 회전을 해주면 총 드래곤 커브의 회전량이 나오기 때문에 재귀함수로 구현하지는 않았습니다. 2) 시간 복잡도 O(n^2) ..
15684번-사다리조작
문제 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 접근방법 1) 접근 사고 https://jaimemin.tistory.com/1078 백준 15684번 사다리 조작 문제 링크입니다: https://www.acmicpc.net/problem/15684 백준 15683번 감시(http://jaimemin.tistory.com/1070)와 유형이 비슷한 브루트 포스(Brute Force) 문제였습니다. 알고리즘은 아래와 같습니다. 1. 사다...
15683번-감시
문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 접근방법 1) 접근 사고 1.CCTV의 갯수만큼 DFS를 진행해야 합니다. 각 재귀함수마다 회전할 수 있는 방향의 경우의 수를 계산해야 하기 때문입니다. 2.DFS를 진행한 뒤에는 방향을 회전시킵니다. 3.1 ~ 2를 반복한 뒤에 탐색이 CCTV의 모든 경우를 탐색했다면 안전 구역의 값을 최소값으로 최신화 합니다. 2) 시간 복잡도 완전 탐색이므로 O(N^2)을 가집니다. 3) 배..
14891번-톱니바퀴
문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 접근방법 1) 접근 사고 1.입력값을 받습니다. 2.톱니바퀴와 방향을 입력받은 뒤 3.해당 톱니바퀴와 인접해 있는 톱니바퀴의 이동 방향을 계산한 뒤(인접해 있는 톱니바퀴가 움직일 경우 인접해 있는 톱니바퀴의 인접해 있는 톱니바퀴도) -> BFS를 활용하여 탐색하기 4.이동 방향이 저장된 배열을 활용해 톱니바퀴의 저장정보를 변경해줍니다. 2) 시간 복잡도 인접해 있는 톱니바퀴의 탐색들이 가..
14890번-경사로
문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 접근방법 1) 접근 사고 정말 구현문제 그 자체였습니다. 특별한 알고리즘 없이 구현력만 보는 문제인데 문제 설명이 저는 한 번에 이해가가지 않아서 어려웠습니다. 자세한 동작은 주석 첨부 하였습니다. 2) 시간 복잡도 O(n^2) 3) 배운 점 breack과 continue 사용 연습을 엄청 한 문제였습니다. 4) PS 문제 이해가 너무 어려웠다. 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
14889번-스타트와 링크
문제 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 접근방법 1) 접근 사고 start팀과 link팀을 구분하기 위해 visited배열을 활용하여 탐색의 높이가 3이 되었을 때 visited 배열값을 활용하여 팀을 구분하고 결과 값을 계산하여 최소값을 갱신해주었습니다. 2) 시간 복잡도 BackTracking을 통한 모든 경우를 탐색해야 하므로 O(n^2)의 시간복잡도를 가집니다. 3) 배운 점 구현력이 무럭무럭 자라고 있습니다. 4) PS 정답 코드 1 2 3 ..
14888번-연산자 끼워넣기
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근방법 1) 접근 사고 가능한 모든 연산의 경우를 탐색해줘야 하는 문제였습니다. DFS 알고리즘을 통해 모든 경우의 수를 구해주었습니다. 2) 시간 복잡도 O(V + E) 3) 배운 점 매개변수를 적절하게 사용하면 코드의 라인이 절약될 수 있다는걸 느낀 문제입니다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 ..