Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 풀이 먼저 모든 눈사람의 크기를 구해준다. 2중for문을 이용하여 모든 조합을 완성 시킬 수 있다. 그런 뒤, 두 눈사람의 크기차이의 최솟값을 찾으면 되는것이기때문에 눈사람의 크기순으로 정렬을 한 뒤, 자신의 바로 뒤의 눈사람과 비교를 해서 값을 갱신시켜주면 된다. 이때 서로다른 4개의 눈덩이를 골라야하므로, 눈사람 2개를 골랐을때, 중복된 눈덩이가 있는지 확인 후,..

2021. 9. 27.

문제풀이/백준oj

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 1. 배열을 모두 탐색하며, 색이 같고 4개이상 붙어있는 퍼즐들을 모두 끌어모은다. 2. 해당 퍼즐들을 모두 터트리며, 터트린 퍼즐의 위에 있는 퍼즐들을 모두 내려준다. 이때, 겹치지 않기 위해, 터트릴땐 맨 위에있는 퍼즐먼저 터트려주며 횟수를 1 증가시킨다. 3. 탐색을 했을때, 색이 같고 4개이상 붙어있는 퍼즐이 없다면 종료한 뒤, 횟수를 출력해준다. 코드 #in..

2021. 9. 26.

문제풀이/백준oj

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 다익스트라 알고리즘을 이용하여, 해킹을 시작한 컴퓨터로부터 의존성이 존재하는 컴퓨터들까지의 최단거리를 모두 구한 뒤, 도달할 수 있는 컴퓨터의 개수(코드에서 dist의 값이 INF가 아닌것들은 도달 할 수 있다는 의미)를 세어주면서, 모두 감염이 되는 시간은, 가장 마지막으로 감염이된 컴퓨터의 시간이 된다. 시간복잡도 우선순위큐를 이용한 다익스트라 알고리즘의 시간복잡도는 O(DlogN)이 된다...

2021. 9. 26.

문제풀이/백준oj

https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 1. 맵을 입력받는다. 2. 입력받은 뒤, 좌 우 좌 우 순서대로 부술 라인을 입력받는다. 3. 해당라인, 해당 방향에서 처음 만나는 미네랄을 부순 뒤, 상/하/좌/우 를 BFS로 탐색을 하면서, 바닥과 연결되어있지않은(중력에의해 떨어져야 하는 미네랄 덩어리)를 찾아준다. 문제에서 2개의 덩어리가 동시에 떨어지지 않는다는 조건이 있으므로, 하나의 덩어리만 찾아질것이다. 4. 만약 3번에서 중력에의해 떨어져..

2021. 9. 26.

문제풀이/백준oj

https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 풀이 전체문제를 부분적으로 쪼개어 문제를 해결하는 분할정복에 해당하는 문제이다. 1. 입력받은 N값으로 초기 문자열을 만들어 준다. 2. 재귀함수를 이용하여 분할정복을 시작한다. 2-0. 베이스케이스 = 해당 토막의 길이가 1 2-1. 3등분을 한다. 2-2. 첫번째 토막은 재귀함수를 호출한다. 2-3. 두번째 토막은 모두 공백으로 바꾸어준다. 2-4. 세번째 토막은 재귀함수를 호출한다. 코드 #..

2021. 9. 26.

문제풀이/백준oj

https://www.acmicpc.net/problem/6416 6416번: 트리인가? 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. www.acmicpc.net 풀이 1. 입력을 받으며 트리를 만들고, 각 정점마다 진입차수를 구해준다. 또 각 정점이 1,2,3,4 처럼 순서대로 나온다는 보장이 없으므로, set을 이용하여 현재까지 나온 정점들을 기록해준다. 2. 만약 처음부터 0 0 이 입력이 됐다면, 트리이다. 3. 2번이 아니라면, 진입차수를 이용하여 트리인지 판별을 해준다. 존재하는 모든 노드들의 진입차수를 탐색하며, 진입차수가 0인것의 개수를 구해주며..

2021. 9. 25.

문제풀이/백준oj

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 dfs를 이용하여, 갈수있는 경우를 모두 구해주고 싶었지만 시간초과가 났다. 그래서 한번 방문한적이 있는 지점은 해당지점까지의 경로의 개수를 기억하는 DP를 이용하여 문제를 해결했다. 그런뒤 도착지점부터시작하면 자신보다 더 높은곳을 찾아주고, 시작지점부터 시작하면 자신보다 더 낮은곳을 찾아 진행시키면서, 목적지에 도달하면 1을 추가해주는 DP를 이용한 dfs를 해주면된다. 코드 #include #..

2021. 9. 16.

문제풀이/백준oj

https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 풀이 기본적으로 BFS를 이용하여 문제를 해결할 것이다. 건물을 BFS로 돌면서, 외벽의 개수를 세어주면 되는 일인데, 여기서 외벽인지 내벽인지 판별하는것이 가장 큰 문제이다. 여러 풀이방법이 있겠지만, 건물에 대한 BFS를 돌기전에, 건물이 지어지지 않은 공간을 먼저 BFS를 돌며, 만약 외부( 범위 밖) 과 접촉한 건물이 없는 공간이라면, 이 비어있는 공간들은 모..

2021. 9. 15.