본문 바로가기

알고리즘60

[백준 Silver 1] 2961 도영이가 만든 맛있는 음식 - Java 문제링크 : https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 접근 과정 : 재료의 조합을 만들어가면서, 각 조합의 신맛과 쓴맛을 계산해 그 차이를 갱신한다. 완전탐색을 통해 모든 조합을 확인. 사용되는 재료는 비스마스킹으로 체크. 아무것도 사용하지 않은 경우를 제외한, 나머지 조합으로 맛의 차이 계산 소스 코드 및 결과 : package BOJ; /* 도영이가 만든 맛있는 음식 */ import java.io.*; impo.. 2021. 12. 21.
[백준 Gold 2] 1525 퍼즐 - Java 문제링크 : https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 접근 과정 : 3x3 표를 하나의 문자열로 이어서 String으로 관리 0의 위치에 따라서, 이동이 가능한 다음 String을 BFS로 탐색하고, "123456780"과 같으면 종료. 방문체크는 HashSet으로 처리. 소스 코드 및 결과 : package BOJ; /* 퍼즐 */ import java.io.*; import java.util.*; public class BOJ1525 { static int[] dx = { -1, 1, 0, 0 }; static.. 2021. 12. 19.
[백준 Platinum 5] 6549 히스토그램에서 가장 큰 직사각형 - Java 문제링크 : https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 접근 과정 : 주어진 직사각형들을 순회하면서, 현재 i번째 사각형까지 만들 수 있는 직사각형의 넓이를 구하려고 했다. 현재 i번째 사각형과 비교해서 가능한 높이의 이전 사각형을 Stack에 담아서 비교하고자 하였다. 소스 코드 및 결과 : package BOJ; /* 히스토그램에서 가장 큰 직사각형 */ import java.i.. 2021. 12. 19.
[백준 Silver 3] 5397 키로거 - Java 문제링크 : https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 접근 과정 : 화살표로 인한 인덱스 변화에 주목하면서, 패스워드를 입력하면 된다고 생각 자료구조로, 연결리스트나 스택을 사용할 수 있을 것이라 생각 최근 ListIterator를 알게되었고, 연결리스트의 탐색에 필요한 비용을 줄여주기에 이를 사용!! vs 스택을 사용하는 경우도 비교해보았다. 소스 코드 및 결과 : package BOJ; /* 키로거 LinkedList + Li.. 2021. 12. 18.

티스토리툴바