개발하는 기계공학도

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Q_9935 { //두 줄 받을 거라 오랜만에 Scanner 사용해보자. static Scanner sc = new Scanner(System.in); //끝 쪽 추가 삭제를 주로 할테니까 ArrayDeque static..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net import java.io.*; public class Q_17609 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int result; public static vo..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 전형적인 DFS, BFS 문제에 효율성을 추가한 문제이다. 아무것도 안 잠기는 경우 = 안전 영역 1개 그 외에 판단해야 하는 경우 각 위치의 높이가 해당하는 지점 예를 들면 높이가 (1, 2, 2, 3, 3, 4, 8) 이라면, 1, 2, 3, 4, 8 일때 확인함으로서 확인 횟수를 줄일 수 있다. => Set을 사용해서 중복된 높이를 지웠다. 이번에는 dfs로 풀어보고 싶었는데 최악의 경우에 스택이 ..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 전형적인 bfs, dfs 문제이다. 일정 때문에 마음이 급해 코드를 깔끔하게 작성하지 못했다. 각 그림마다 최댓값을 구하기 위해 큐 하나를 더 사용했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.S..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 사실 얼마 전에 풀었던 탑 문제와 개념적으로 아예 같은 문제라 금방 풀었다. 100만개를 전부 비교하면 시간복잡도 N^2 이라 시간이 부족할 것이고 스택을 사용해 비교할 필요가 없는 부분들은 제거하면서 확인했다. https://godhkekf24.tistory.com/93 [백준 - JAVA] 2493번 : 탑 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 먼저 Java Collection Framework에 대해 깔끔하게 정리된 자료가 있어 공유한다. 이 문제는 Deque를 LinkedList로 구현하면 indexOf 메서드를 사용할 수 있어서 미리 예측해서 연산을 진행할 수 있다. 기준이 되는 인덱스를 찾고 그 인덱스보다 작으면 왼쪽으로 돌리고 크면 오른쪽으로 돌리면 된다. 코드는 다음과 같다. import java.io.*; import j..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 처음에는 단순히 값 비교를 하나하나 하는 방식을 생각했는데 최악의 경우 500000^2 회 비교를 해야하기 때문에 시간초과가 날 것 같았다. 매번 전부를 계산하는 것은 안되고 진행 과정 중간에 쳐낼 수 있는 것은 쳐내야 했는데 스택에 쌓으면서 전에 있던 숫자보다 크다면 더 이상 스택에 쌓아놓을 필요가 없다는 것을 알았다. 새로운 숫자가 들어올 때 본인보다 작으면 버리고 본인보다 크면 위에 쌓는 ..

https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 취업 스터디 덕분에 알고리즘을 다시 블로그에 올리게 됐습니다. 취업 스터디 감사합니다. 어떤 3가지 작업을 실행했더니 1 ~ N 으로 정렬이 되었다! 그럼 반대로 돌려봐라! 아래에서부터 N->1 로 쌓여 있었기 때문에 1부터 N까지 순서대로 반대 작업을 수행하면 된다. 1번의 반대 작업은 첫번째 순서에 넣으면 된다. 2번의 반대 작업은 두번째 순서에 넣으면 된다. 3번의 반대 작업은 마지막 순서에..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net // 먼저 받은 수들을 배열에 넣고 정렬한다. 그 이후 이분탐색으로 수를 찾는다. // 사실 하나의 수가 있는지 없는지 확인하는 과정은 정렬 후 이분탐색을 활용하는 것보다 하나씩 확인하는 작업이 더 빠를 수 있다. // 하지만 지금은 여러개의 수를 확인해야 하기 때문에 정렬 후 이분탐색이 훨씬 빠른 것으로 추측해 볼 수 있다. //프로덕션코드 imp..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net // 기본값 0층 i호에 있을때 i명이 있다고 먼저 초깃값 지정해준 뒤에. // 재귀함수로 계속 역으로 불러오면 되겠다. //프로덕션코드 mport java.util.Scanner; public class Quiz2775 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numberOfTestCase = scanner.nextIn..