분류 전체보기
-
[백준]14226: 이모티콘 - JAVA문제풀이/백준 2021. 5. 16. 14:58
[백준]14226: 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 걸리는 시간의 최소값을 구하는 문제 이므로 BFS 탐색을 사용하여 문제를 풀었다. BFS탐색을 하면서 조건에 맞게 1, 2, 3번을 진행하고 현재 개수가 S와 같아진다면 BFS탐색을 종료하고 현재 시간을 출력하도록 하였다. 탐색을 하면서 계속 같은 구간을 반복하지 않도록 visited 배열을 사용하였다. 각각의 인덱스가 의미하는 바는 [clipboard에 현재 복사..
-
[백준]1300: K번째 수 - JAVA문제풀이/백준 2021. 5. 13. 15:05
[백준]1300: K번째 수 풀이 이분탐색 문제이다. 문제의 조건에 따라 직접 배열을 만들고, 정렬하는 것도 방법 중 하나이겠지만 입력 조건에 N은 10의 5제곱 이기 때문에 이를 2차원 배열로 만들면 메모리 소비와 시간도 엄청 걸릴 것 이다. 그러므로 이분탐색으로 풀어야 한다. 문제의 예제입력을 푸는 과정을 살펴보자. 배열 A를 2차원 배열로 표현하면 다음과 같다. 배열A 1 2 3 2 4 6 3 6 9 이때, 6이라는 숫자가 오름차순 정렬되었을때 몇 번째에 오는지 알아보자. 1번열은 모두 6이하 이므로 3을 더해준다. 2번열은 모두 6이하 이므로 3을 더해준다. 3번열은 3, 6 두개의 숫자가 6이하 이므로 2를 더해준다. 즉, 6은 8번째에 오는 숫자가 된다. 진짜인지 확인해 보자. A를 오름차순 ..
-
[백준]16236: 아기 상어 - JAVA문제풀이/백준 2021. 5. 11. 15:53
[백준]16236: 아기 상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 BFS + 구현 문제로 조건이 까다롭고 신경써야 할 조건들이 많아 어렵다고 느껴졌던 문제였다. BFS안에서 현재 이동할 수 있는 곳으로 이동하면서 물고기의 크기가 자신의 크기보다 작으면 먹어주도록 하였다. 물고기의 크기가 자신의 크기보다 작거나 같다면 이동시켜 주었다. 자신의 크기보다 작은 물고기를 만나면 모두 ArrayList에 담아준 다음 위쪽 -> 왼쪽 좌표를 비..
-
[백준]1068: 트리 - JAVA문제풀이/백준 2021. 5. 10. 15:27
[백준]1068: 트리 www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 부모 인덱스를 입력받고, 노드를 삭제한 후 리프 노드를 count하는 문제로 깊이 우선 탐색 방법을 적용하여 문제를 풀었다. (약간 변형된 DFS문제라고 생각한다.) 노드를 삭제할 때에는 재귀 함수를 활용하여 현재 노드의 부모 인덱스가 삭제된 노드라면 연쇄적으로 삭제가 일어나도록 구현해 주었다. 리프노드를 카운트 할 때에는 깊이 우선 탐색을 활용하여 현재 노드를 부모로 가지는 ..
-
[백준]2636: 치즈 - JAVA문제풀이/백준 2021. 5. 7. 15:37
[백준]2636: 치즈 www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 BFS 탐색 알고리즘을 사용하여 문제를 풀었다. 우선, 현재 치즈의 개수를 세어 준 다음 치즈 개수가 0이 아닐때까지 BFS 탐색을 하며 치즈의 개수를 줄여나갔다. 탐색은 0,0부터 시작하여 치즈를 만나면 해당 치즈를 없애주고, 치즈가 아니라면 큐에 넣어 근처에 있는 치즈를 탐색하도록 하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..
-
[백준]1806: 부분합 - JAVA문제풀이/백준 2021. 5. 5. 20:22
[백준]1806: 부분합 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 가장 짧은 길이의 부분합을 만족하는 길이를 출력하는 문제로 투포인터의 대표적인 문제라고 할 수 있다. 처음에는 투포인터 문제인줄 모르고 중첩 반복문을 사용하여 풀었다. 당연히 시간초과가 발생했고 투포인터 문제라는 힌트를 얻고 start, end 두 개의 인덱스 포인터를 사용하여 풀었다. 풀이 과정을 그림으로 표현하면 아래와 같다. start와 end 포인터를 조건에 ..
-
[프로그래머스]다단계 칫솔 판매 -JAVA문제풀이/프로그래머스 2021. 5. 4. 15:00
[프로그래머스]다단계 칫솔 판매 programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 풀이 이 문제는 올해 프로그래머스 Dev-Matching 문제라고 한다. 문제에서 주어진 조건대로 따라가며 풀었고 별다른 자료구조를 사용하지 않고 그리디하게 풀었다. 조건에 맞게 반복문을 돌리면서 현재 판매원이 가져갈 금액을 더해주고, 금액을 현재 금액의 10퍼센트로 바꾸어 주면서 연산을 했다. 테스트 코드는 모두 통과되지만, 걸리는 시간..
-
[백준]11559: Puyo Puyo - JAVA문제풀이/백준 2021. 5. 3. 16:01
[백준]11559: Puyo Puyo www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 BFS알고리즘을 사용하여 문제를 풀었다. BFS + 구현 능력을 보기에 아주 적절한 문제라고 생각했다. 코드를 구현할 때는 다음과 같은 순서로 구현해 주었다. 입력받은 필드를 탐색하며 뿌요가 있는 필드에 도달하면 그 근처에 같은 색의 뿌요가 몇개 있는지 BFS 알고리즘을 통해 탐색한다. 같은 색의 뿌요가 4개 이상이라면 해당 뿌요들을 연쇄시킨다..