분류 전체보기
-
[백준]16929: Two Dots - JAVA문제풀이/백준 2021. 4. 21. 15:37
[백준]16929: Two Dots www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 풀이 해당 게임을 알고 있다면 아주 쉽게 이해할 수 있다. 싸이클을 이루는 같은 색의 점 4개를 선택할 수 있는지 출력하는 문제이다. DFS탐색을 사용해 문제를 풀었다. 싸이클을 확인하는 방법을 아래와 같이 구현하였당. 첫번째로 선택한 점과 마지막에 선택한 점이 같아야 한다. 선택된 점들의 개수가 4개 이상이어야 한다. 위의 조건을 만족하면 true를 반환하고, 아니..
-
[백준]5430: AC - JAVA문제풀이/백준 2021. 4. 18. 18:44
[백준]5430: AC www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 복잡한(자바에선 이정도 문자열이면 복잡한 문자열에 속한다고 생각한당.)문자열을 입력받은 후 문제의 조건에 맞게 출력하면 되는 문제이다. 자바로 문자열 문제들을 풀때 입력 받을때, 출력할때, 문자열 쪼개고 예외케이스 처리할 때마다 머리가 아프다.. 처음에는 StringBuilder객체를 사용해서 직접 reverse()와 substring() 함수를 사용하여 문자열을 조작해 주었는데 시간초과가 났다. 그래서 start, end포인터를 만들어 ..
-
[백준]3109: 빵집 - JAVA문제풀이/백준 2021. 4. 17. 16:56
[백준]3109: 빵집 www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 첫 번째 열에서 마지막 열까지 도달할 수 있는 최대 경로를 반환하는 문제로 DFS를 사용하였다. ' DFS함수의 반환타입을 Boolean으로 설정하여 첫 번째 열에서 행의 위치를 변경하며 마지막 열까지 도달할 수 있다면 true, 아니면 false를 반환하도록 하였다. true를 반환했다면 도달 할 수 있다는 의미이므로 count++를 해주었다. 이때 파이프를 설치할 수 있는 위치는 현재 위치의 오..
-
[백준]1747: 소수&팰린드롬 - JAVA문제풀이/백준 2021. 4. 15. 16:44
[백준]1747: 소수&팰린드롬 www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 소수와 팰린드롬을 모두 판별하는 문제이다. 소수를 판별할 때에는 에라토스테네스의 체 알고리즘을 사용하여 빠르게 소수를 판별해 주었다. 간단히 설명하자면 소수를 판별하기 위해 나누어 지는 수가 있는지 확인할 때 나누어지는 수의 범위를 제곱근으로 줄여 빠르게 판별할 수 있다. 팰린드롬은 간단하게 입력받은 숫자를 문자열로 변경해 첫 문자와 마..
-
[백준]2665: 미로만들기 - JAVA문제풀이/백준 2021. 4. 11. 15:44
[백준]2665: 미로만들기 www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 BFS + 다익스트라를 활용하여 풀었다. 첫 노드에서 오른쪽 아래 노드로 가는 최단 거리 중에서 검은색 벽을 가장 적게 바꾸는 방법의 횟수를 출력하는 문제로 이전에 풀었던 '벽 부수고 이동하기'와 유사한 문제였다. 검은색 벽을 흰색 벽으로 바꾸는 최소 횟수를 누적하여 계산하며 탐색하기 위해 다익스트라 방법을 사용하였다. dist배열을 사용하여 현재 위치의 가장 최소 횟수를 저장할 수 ..
-
[백준]1600: 말이 되고픈 원숭이 - JAVA문제풀이/백준 2021. 4. 4. 18:11
[백준]1600: 말이 되고픈 원숭이 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 출발 위치에서 도착위치까지 움직일 수 있는 최소 값을 반환하는 문제이므로 BFS를 사용하였다. 이때 말이 움직일 수 있는 위치와 원숭이가 움직일 수 있는 위치를 따로 배열로 만들어 주었다. 최소값을 계산할 때는 한번 방문한 위치는 재 방문해서 안되기 때문에 visited배열을 선언하여 재 방문을 허용하지 않도록 하였다. 이때 단순히 visited배열을 ..
-
[프로그래머스]풍선 터트리기 - JAVA문제풀이/프로그래머스 2021. 3. 31. 15:47
[프로그래머스]풍선 터트리기 코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 풀이 이 문제의 조건 중 가장 중요한 조건은 '인접한 두 풍선 중에서 번호가 더 작은 풍선을 터뜨리는 행위는 1번만 할 수 있다'라는 조건이다. 즉, 인접한 풍선의 번호가 모두 더 작다면 마지막까지 남을 수 없다는 것이다. 그럼 이러한 상황에서 마지막까지 풍선이 남기 위한 조건은 무엇일지 생각해보쟝. 임의의 풍선을 중심으로 인접한 풍선의 번호가 모두 더 작으면 안된다. 그럼 모든 원소 값을 기준으로 왼쪽, 오른쪽 풍선 번호의 최소값을 찾고 해당 값보다 현재..
-
[백준]1240: 노드사이의 거리 - JAVA문제풀이/백준 2021. 3. 28. 16:28
[백준]1240: 노드사이의 거리 www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 풀이 두 노드 사이의 최단 경로를 반환하는 문제였다. 다양한 방법이 있겠지만 나는 다익스트라 알고리즘을 사용하여 풀었다. 노드와 간선 가중치의 정보를 입력 받은 후 M개의 개수 만큼 다익스트라 알고리즘을 돌려 M개의 거리를 출력하였다. 다익스트라 알고리즘은 우선순위 큐(최소힙)와 dist배열, visited배열을 사용하여 구현해 주었다. 기본적인 다익스트라 알고리즘을 구현할 수 있는지 묻는 수준의 문제였고 어렵지 않게 풀었..