Coding Test

[BOJ] 백준 5567 결혼식

https://www.acmicpc.net/problem/55675567번: 결혼식2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다.www.acmicpc.net 풀이 과정상근이의 친구와 친구의 친구까지만 초대가 가능하므로 깊이가 2가 되면 리턴하는 방식의 dfs를 사용했다.양방향 리스트를 만들고, 방문한 정점을 체크할 boolean형 배열을 만든다.dfs를 돌리는데 반복문을 사용해서 리스트의 해당되는 정점을 찾아 연결된 정점에 방문했다는 표시를 하고 재귀 함수를 사용한다.깊이가 2가 됐을 때, 리턴을 하고 방문된 인덱스를 찾아서 값을 센다.시작점인 정점 1을 ..

[BOJ] 백준 1697 숨바꼭질

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 과정 총 3가지의 경우를 탐색해야 한다. 위치가 X일 때, X-1과 X+1, X*2 이렇게 세 가지. int형 checked라는 배열을 만들어서 거쳐온 거리(도착하기까지 걸린 시간)를 기록한다. bfs를 사용해서 시작점인 n부터 큐에 넣고, 만들어둔 배열 인덱스 n에 대한 값으로 방문했다는 의미로 1이라는 값을 넣는다. 반복문을 돌려서 세 가지 경우를 모두 탐색하고..

[BOJ] 백준 11725 트리의 부모 찾기

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 방법 방향에 대한 조건은 없으므로, 양방향 인접 리스트를 만든다. bfs를 돌리는데 루트인 1번 정점부터 큐에 넣고, 부모를 표시할 배열(parents)을 하나 만든다. 1번 정점은 루트 노드이기 때문에 방문했다는 의미로 만들어둔 배열 1번 인덱스 값을 1로 설정한다. 큐에 들어있는 요소를 꺼내서 그 요소와 연결되어 있는 노드를 찾고 그 정점에 방문하지 않았다면 큐에 넣는다. parents 배열의 인덱스와 찾은 노드의 번호가 같을 경우 큐에서 꺼낸 요소 ..

[BOJ] 백준 2343 기타 레슨

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 방법 우선 블루레이의 크기를 임의의 값인 10으로 두고 계산을 하면, 레슨의 순서가 바뀌면 안 되는 조건이 있기 때문에 1+2+3+4를 더해서 한 개, 5+6을 한다면 10보다 커지므로, 뒷부분은 더할 수 있는 값이 없다. 결과적으로 블루레이의 수는 6개가 나온다. m이 3이고 블루레이의 수는 6이기 때문에 블루레이의 크기를 늘려야 된다는 것을 알 수 있다. 그러면 low와 high는 어떻게 정해야..

[BOJ] 백준 7569 토마토

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 방법 익은 토마토에 인접한 토마토들은 보관 후 하루가 지나면 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향으로 익게 된다. 앞, 뒤라는 조건이 있기 때문에 3차원 배열을 이용한다. 3차원 배열에 대해서 간단히 설명하자면, int [][][] = new int [x][y][z] xyz는 일반적으로 x는 y와 z의 배열을 가진 면, y는 배열에서 열(Row), z는 배열..

[BOJ] 백준 2644 촌수계산

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 풀이 방법 예제로 나온 그래프를 그리면 이런 형태가 되는데, 시작점을 7로 잡고 끝점을 3으로 잡으면 이러한 방향 그래프가 나온다. 정점 1번을 보면 들어오는 경우가 있고, 나가는 경우가 있으니 이것은 양방향 인접 리스트를 이용해서 풀 수 있다는 것을 알 수 있다. dfs를 사용해서 시작점을 계속 바꿔주고, 시작점이 바뀔 때마다 count를 한다. 시작점과 끝점이 같아지는 경우에 c..

[BOJ] 백준 14502 연구소

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 방법 벽을 3개를 세울 수가 있는데 어디에 세우느냐에 따라 바이러스가 퍼지는 영역이 달라지게 된다. 따라서 벽을 세울 수 있는 모든 경우를 전부 탐색해야 한다. 초기에 입력받을 배열과 벽을 세울 경우를 탐색하기 위한 배열, 벽을 세웠을 때 바이러스가 퍼졌을 경우의 배열 이렇게 세 가지의 배열이 필요하다. 바이러스가 퍼졌을 경우, 바이러스가 퍼지지 않은 영역인 안전 영역 즉 값이 0인 영역을 bfs를 사용..

[BOJ] 백준 2468 안전 영역

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 방법 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다. 비의 양보다 지점이 더 높을 경우, 안전한 영역이므로 그 영역의 개수를 구한다. 비의 양에 따른 모든 경우를 다 조사해서 안전한 영역의 최대 갯수를 찾아야 하므로, 주어진 영역 높이의 최솟값부터 최댓값까지 모든 경우의 수를 탐색한다. dfs를 사용해서 안전 영역의 갯수를 세고 모든 경우의 수를 비교해서 최댓값을 도출한다. 다..