자바

[백준]14720번 우유 축제 - Java

문제 https://www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 풀이 쉬운 문제임 주석 참고하셈! 코드 // 14720번 우유 축제 // https://www.acmicpc.net/problem/14720 package BAEKJOON; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer..

[백준]2239번 스도쿠 - Java

문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 구현 + 백트래킹 문제 처음에는 입력을 받으면서 큐에 0인 칸의 인덱스(행, 열)을 넣어주었다. poll해서 해당 값을 사용하고 정답이 아닌 경우에는 재귀를 return해서 다시 그 값을 사용해야하는데 큐를 쓰면 그게 불가능해서 다시 구현했다. 다시 구현할 때에는 Queue가 아닌 ArrayList로 구현했다. ArrayList에 숫자가 채워지지 않은 칸(0인 칸)을 넣어주고 인덱..

[백준]2579번 계단 오르기 - Java

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 1로 만들기 같은 유형의 DP 문제이다. https://seokmimmmmmmmm.tistory.com/82 [백준]1463번 1로 만들기 - Java 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 흔한 DP 유형의 문제임 하향식, 상향식 ..

[백준]14501번 퇴사 - Java

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 DP 문제임. 1차원 정답 배열(dp)를 만들어서 풀었음 하루가 지날 때마다 최댓값을 dp 배열에 갱신해주는게 포인트 ! 아직 헷갈려서 담에 한번 더 풀어봐야겠음 T, P, dp 배열을 N+6으로 크기를 설정해준 이유는 [맨처음 0번 인덱스 + (1 ≤ Ti ≤ 5)] 이거 때문이다. 코드 // 14501번 퇴사 // https://www.acmicpc.net/problem/14501 package BAEKJOON; import java.io.BufferedReader; import java.io.IOException; i..

[백준]4963번 섬의 개수 - Java

문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 그냥 지금까지 많이 풀었던 탐색 문제이다. DFS로 풀었다. 음 뭐랄까 쉬워서 별로 할 말이 없다 https://seokmimmmmmmmm.tistory.com/42?category=1004588 [백준]2468번 안전 영역 - Java 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서..

[SWExpertAcademy]1263번 사람 네트워크2 - Java

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 가중치가 있을 때 최단 경로를 구하는 경우 다익스트라 알고리즘을 많이들 사용한다. 근데 가중치가 음수라면 다익스트라 알고리즘을 사용하지 못하는데, 그때 사용할 수 있는 알고리즘이 바로 이 플로이드 와샬 알고리즘이다. 얘는 3중 for문을 돌리기 때문에 시간 복잡도는 O(N^3)이 나오지만(다익스트라 알고리즘도 인접 행렬을 이용하면 O(N^3)의 시간 복잡도가 나오기도 함) 구현이 간단해서..

[SWExpertAcademy]3307번 최장 증가 부분 수열 - Java

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 유명한 DP 문제 유형이라고 한다. DP말고 부분 집합으로도 풀 수 있다. 하나하나 첨부터 끝까지 부분집합을 만들어서 가장 긴 증가하는 부분 수열을 뽑아내도 되는데 그렇게 하면 O(2^N)의 시간 복잡도가 소요된다. 개오래 걸리는거지 미친거지 그니깐 물론 뭐 공집합부터 탐색하는게 아니라 전체집합부터 탐색하면 조금 더 빨리 찾을 수는 있겠지만,,, 그니까 부분 집합말고 DP로 풀어야 시간 ..

[백준]13565번 침투 - Java

문제 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 풀이 간단한 DFS, BFS 문제인 듯하다 그래서 DFS로, BFS로 각각 사용해서 풀어봤음 일단 DFS는 그냥 맨 윗줄에서 0이면 DFS 들어가고 돌면서 0인 칸을 2로 바꿔줌 위에서 0인 애들 다 돌렸으면 맨 밑줄에서 2인 애가 나오면 그건 전기가 통하는 거고 안나오면 안통하는거 그니까 2가 나오면 YES 출력하고 System.exit(0);으로 시스템..