본문 바로가기

Algorithm221

[백준] 15729: 방탈출 - JAVA https://www.acmicpc.net/problem/15729 풀이그리디 문제. 불이 켜진 상태를 주어진 상태와 똑같게 만들어야 한다. 스위치는 자신과 오른쪽 두 개 스위치를 한번에 누르게 된다. 왼쪽부터 탐색할 때 이전 스위치에는 영향을 주지 않는다는 것. 왼쪽부터 오른쪽으로 탐색하며 정답과 상태가 다른 스위치만 눌러가며 카운트했다.  메모리: 77944KB시간: 440ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu.. 2024. 5. 12.
[백준] 14890: 경사로 - JAVA https://www.acmicpc.net/problem/14890 풀이구현 문제 였다. 이전 칸과 비교하여 체크해주는 문제. 높이가 이전과 같다면 지나갈 수 있고, 1 차이나면 경사로를 설치해야 한다. 경사로의 높이는 1로, 길이는 L로 고정되어 있어서 이전 칸과 1 차이날 때,  L길이의 for문을 통해 경사로를 놓을 수 있는지 탐색했다. 경사로의 바닥면의 높이가 다 같은지, 이미 설치된 경사로가 없는지 체크해 주었다. 이차원배열의 행과 열을 모두 체크해야 했다. 함수를 재사용 하기 위해 탐색할 부분을 일차원배열로 만들어 하나의 함수를 이용했다.  메모리: 15048KB시간: 144ms언어: Java 11import java.io.*;import java.util.*;public class Main .. 2024. 5. 12.
[백준] 1535: 안녕 - JAVA https://www.acmicpc.net/problem/1535 풀이DP, 배낭 문제. 인사를 할때마다 체력을 잃고 기쁨을 얻는다. 체력 100에서 시작해서 0이 되면 죽는다. dp배열을 dp[사람의 수][100] 으로 설정했다. 사람마다 잃는 체력, 얻는 기쁨을 통해 이전 dp배열과 비교해준다. 점화식은 다음과 같다.dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - L[i]] + J[i]);  메모리: 14196KB시간: 176ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 12.
[백준] 6198: 옥상 정원 꾸미기 - JAVA https://www.acmicpc.net/problem/6198 풀이그리디스러운 문제였다. 알고리즘 분류는 자료 구조, 스택. 자기보다 오른쪽에 있는 빌딩을 보는데 높이가 자기보다 낮은 빌딩을 볼 수 있다. 중간에 같거나 높은 빌딩을 만나면 그 다음부터 빌딩은 보지 못한다. 나는 현재 빌딩의 높이를 기준으로 이 빌딩을 볼 수 있는 왼쪽 빌딩들의 개수를 카운트했다. stack에 빌딩의 높이를 담으면서 진행하며 현재 빌딩보다 낮은 빌딩을 스택에서 빼줬다. stack의 사이즈를 답에 더해주고 현재 빌딩을 stack에 넣어주면 끝.  메모리: 24236KB시간: 324ms언어: Java 11import java.io.*;import java.util.*;public class Main { public s.. 2024. 5. 12.
[백준] 2800: 괄호 제거 - JAVA https://www.acmicpc.net/problem/2800 풀이브루트포스 문제. 괄호의 쌍을 매칭하여 출력하거나 출력 안 하거나 하면 되는 문제였다. 서로의 짝을 매칭 시킬 방법으로 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 제일 위에 있는 괄호와 짝을 맺는다. 서로의 짝의 번호를 배열에 저장했다. 짝을 모두 저장한 후 dfs 탐색을 통해 해당 괄호를 boolean 배열에 true, false로 체크하여 출력할지 안 할지를 저장했다. 중복 식을 제거하기 위해, 사전 순으로 정렬하기 위해 TreeSet을 이용했다.  메모리: 24900KB시간: 280ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12.
[백준] 2624: 동전 바꿔주기 - JAVA https://www.acmicpc.net/problem/2624 풀이dp문제. 동전으로 특정 금액을 만드는 문제였는데 동전의 개수가 정해져있어서 어려웠다. 동전 금액과 각각의 개수가 주어지는데 동전들을 이용해서 T원을 만들어야 한다. 금액에 대해 동전 몇 개를 썼을 때 경우의 수를 저장하는 dp배열을 만들었다. 동전 * 개수를 price라고 하면 점화식은 다음과 같다. `dp[k][i + 1] += dp[k - price][i];`dp[k][i+1]은 동전 (i+1)개를 썼을 때 k의 금액을 만들 수 있는 경우의 수이다.  메모리: 18072KB시간: 164ms언어: Java 11import java.io.*;import java.util.*;public class Main { public sta.. 2024. 5. 12.
[백준] 1991: 트리 순회 - JAVA https://www.acmicpc.net/problem/1991 풀이트리, 재귀. 이진 트리가 주어지고 전위순회, 중위순회, 후위순회한 결과를 출력하면 되는 문제이다. 이진 트리는 각 노드와 왼쪽 자식 노드, 오른쪽 자식노드로 주어져 트리를 구현하여 저장해야 했다.  메모리: 14188KB시간: 124ms언어: Java 11import java.io.*;import java.util.*;public class Main { static StringBuilder sb = new StringBuilder(); static class Node { char ch; Node left; Node right; public Node(char ch) { .. 2024. 5. 12.
[소프티어] [21년 재직자 대회 본선] 코딩 테스트 세트 - JAVA https://softeer.ai/practice/6261 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 풀이난이도별로 문제의 개수가 주어지고, 이 문제들을 난이도별로 하나씩 배치할때 최대 몇개의 세트가 나올 수 있는지 구하는 문제이다. 난이도는 1부터 N까지 있고, i레벨 또는 i+1레벨로 할 수 있는 문제가 있다. 각각 c와 d배열에 나누어 저장했다. d배열의 값들을 c에 적절히 옮겨야 한다. 최댓값은 c[N]에 d[N-1]을 모두 옮겼을 때이다. 따라서 (0, c[N] + d[N-1])의 범위로 이분탐색을 통해 해당 값이 될 수 있는지 검사했다. 이분탐색으로 풀어야겠다고 생각을 못했던 문제였다. 최종 값을 이분탐색으로 찾아 체크하는 방식으로 풀 수 있구나 알게된 문제였다.  .. 2024. 5. 12.
[프로그래머스] [카카오 인턴] 경주로 건설 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이(0, 0)에서 (N-1, N-1)까지 이동해야한다. 1은 벽을 의미하므로 0만을 통과해서 갈 수 있고, 직선도로는 100, 코너는 500이 필요하다. 즉, 방향을 같이 저장하여 방향이 달라지면 코너가 생기는 것이므로 500을 추가하고, 항상 100을 추가하면 된다. 방향을 같이 저장하면서 bfs탐색을 진행했고, 비용을 최소로 해야하기때문에 board 이차원배열에 비용을 같이 저장하면서 진행했다... 2024. 5. 12.
[백준] 12919: A와 B 2 - JAVA https://www.acmicpc.net/problem/12919 풀이문자열, 브루트포스 문제이다. A와 B로만 이루어진 단어들이 있는데 첫번째 주어지는 단어(S)로 두번째 단어(T)를 만들 수 있는지 확인하는 문제이다. 문자열을 바꿀 때는 "문자열의 뒤에 A를 추가한다", "문자열의 뒤에 B를 추가하고 문자열을 뒤집는다" 이 두가지의 연산이 가능하다. S에서 T를 만드려면 두 가지 연산을 모두 시도해야 하지만 T에서 S를 만들 때는 문자열의 뒤에 A가 있는지, 문자열의 앞에 B가 있는지 확인하여 그 경우에만 연산을 하면 된다. 문자열을 뒤집는 방법으로는 for문을 이용한 방법과 StringBuilder의 reverse를 이용한 방법이 있다. String reverse = "";for (int i = .. 2024. 5. 12.

티스토리툴바