[프로그래머스,Level 1] 문자열을 정수로 바꾸기(JAVA 구현)
·
CodingTest/프로그래머스(Programmers)
- 첫 풀이 처음에는 문자열로 받은 숫자를 charAt() 메서드를 이용해 하나하나 파싱 하여 정수로 변환하려는 과정을 시도했다. (바보 같다.) class Solution { public int solution(String s) { int answer = 0; int num = 1000; for(int i=0;i
[프로그래머스,Level 1] 소수 찾기 (JAVA 구현)
·
CodingTest/프로그래머스(Programmers)
-첫 풀이 class Solution { public int solution(int n) { int answer = 0; for(int i = 2; i
[백준,BOJ 10773] 제로(JAVA 구현)
·
CodingTest/백준 온라인 저지(BOJ)
- 풀이 문제의 분류 자체가 스택이기 때문에 스택을 사용해야 한다는 생각이 들기도 하지만, 문제를 잘 읽어보면 정수가 계속 입력될 때 '0'이 입력되면 0이 입력되기 이전의 정수 하나를 지우기 때문에 최근에 입력된 데이터가 가장 먼저 출력되는 LIFO 구조의 스택을 사용해야 한다는 사실을 알 수 있다. 필자는 처음에 모든 정수를 입력받아 스택에 PUSH해준 뒤, POP 해가면서 0이 나오면 한 번 더 POP을 하는 식으로 접근하였지만, 예제 입력 2와 같이 0이 연속으로 입력되는 경우, 최근의 정수를 제대로 지우지 못하기 때문에 입력받을 때 0이면 바로 지워주게끔 풀이하였다. import java.io.BufferedReader; import java.io.BufferedWriter; import jav..
[백준,BOJ 10828] 스택(JAVA 구현)
·
CodingTest/백준 온라인 저지(BOJ)
-풀이 자료구조 중 LIFO구조인 스택의 기본적인 동작들을 구현하는 문제로, 자바의 경우 배열과 연결 리스트를 활용하여 직접 구현이 가능하며, 별도의 Stack 라이브러리가 제공되어 해당 메서드를 이용해도 된다. 필자는 배열과 라이브러리를 이용해 구현해 보았다. 또, 이 문제에서 주의해야 할 점은 제한시간이 0.5초로 상당히 짧기 때문에, BufferedReader와 BufferedWriter 객체를 사용하는 것이 좋을 것 같다. - 배열을 이용해 직접 Stack 클래스 구현 방법. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; i..
[백준,BOJ 1541] 잃어버린 괄호(JAVA 구현)
·
CodingTest/백준 온라인 저지(BOJ)
- 풀이 이 문제의 경우 예제로 주어진 55-50+40이 55-(50+40)의 형태로 괄호를 씌워야 최솟값을 만들 수 있다는 사실을 알고, -를 기준으로 입력받은 문자열을 하나씩 탐색하며 다음 -를 만날 때까지 숫자들을 더하는 방식을 생각해 시도하였다. 그러나 문제에서 주어진 첫 문자와 마지막 문자는 숫자라는 조건을 보지 못하고 첫 문자에 음수가 입력되는 경우까지 생각하다 너무 복잡해져서 포기했다. 그런데 저 조건을 확인하고 나니 할 수 있을 것 같기도 하다. 결국 이 문제를 풀기 위해서는 -를 기준으로 문자열을 파싱해주면 된다는 것이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanne..
[백준,BOJ 11399] ATM(JAVA 구현)
·
CodingTest/백준 온라인 저지(BOJ)
-풀이 그리디 알고리즘을 사용하기 적합한 문제의 조건은 1. 각 경우가 독립적인 경우 2. 각 경우의 선택으로 다른 경우에 영향을 미치지 않는 경우를 만족하면 된다고 알고 있다. 이 문제의 경우 각 사람들의 대기시간이 상호 영향을 받지 않는 독릭접인 상태이다. 그리디 알고리즘을 이용해 손님들의 소요시간을 최소로 만들기 위해서는 먼저 끝나는 사람을 우선으로 처리하면 최솟값이 나오게 된다. 이는 이전의 회의실 배정 문제와 비슷한 유형이라고 생각된다. 그렇기에 문제에서 알려주고 있는 최솟값을 구하는 방법을 코딩으로 옮기기만 하면 된다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(Str..
[백준,BOJ 1931] 회의실 배정(JAVA 구현)
·
CodingTest/백준 온라인 저지(BOJ)
-풀이 처음 이 문제를 풀 때는 각 회의 정보를 시작시간을 기준으로 정렬하여 회의별 소요되는 시간이 가장 짧은 순서대로 조건을 걸어 카운팅을 하려 했지만, 조건이 애매해져 다른 분의 글을 참고하였다. 다른 분의 글에서는 정렬을 종료시간을 기준으로 하여, 가장 일찍 끝나는 회의 순서대로 카운팅 하는 방법을 사용했다. 맞다. 회의실을 가장 많이 돌리려면, 빨리 끝나는 순서대로 집어넣는 것이 그리디라고 할 수 있다. import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(..
[백준,BOJ 11047] 동전 0(JAVA 구현)
·
CodingTest/백준 온라인 저지(BOJ)
- 풀이 이전에 풀었던 문제였지만, 블로그에 글을 게시하지 않았던 문제이다. 단계별 풀어보기의 그리디 알고리즘으로 분류되어 있는 첫 번째 문제이다. 그리디 알고리즘이란, 한 상황에서 취할 수 있는 최대 이득을 취하는 알고리즘이라 한다. 이러한 방식은 이전 분류인 동적 프로그래밍의 과정이 너무 많은 연산이 이루어지기 때문에 이를 보완하기 위해 고안된 알고리즘이라 한다. 한 상황에서 최선의 것을 선택하다 보니 최적의 해를 보장하지 않는다는 특징이 있다고 한다. 그리디 알고리즘으로 분류되어 있는 특징처럼 문제에서 주어진 값 k를 최소한의 동전 개수로 이루기 위해서는 가장 높은 단위의 화폐부터 사용하면 최소한의 동전 개수를 사용하게 된다. 최소한의 동전 개수를 이루기 위해 가장 높은 단위의 화폐부터 사용한다는 ..
[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)
·
CodingTest/백준 온라인 저지(BOJ)
-내 생각 이 문제의 경우 혼자 풀어보려고 해서 결과는 잘 나오는 것 같은데 어떤 반례에서 걸리는지 계속 오답처리를 받아서 결국 검색을 해봤는데, 이러한 무게와 가치가 함께 주어지는 문제의 경우 knapsack 알고리즘이라고 별도로 존재한다는 사실을 알 수 있었다. -해법 knapsack알고리즘의 경우에 dp 배열을 1차원 또는 2차원으로 해결할 수 있다고 하는데, 많은 사람들이 2차원 배열을 사용하는 것 같다. 나의 경우는 알고리즘 대회를 준비하는 것이 아닌, 취업을 위한 공부이기 때문에 합격선만 만족하면 더 쉬운 것을 사용하는 것이 맞는 것 같다. dp배열을 사용할 때 각 인덱스가 의미하는 바는 dp [i번 째 아이템][무게]를 의미한다고 한다. 이를 표로 그려보면 아래와 같이 나타낼 수 있다. 0번..
[백준,BOJ 1912] 연속합(JAVA 구현,추가풀이)
·
CodingTest/백준 온라인 저지(BOJ)
-내 생각 문제를 제대로 읽어보지 않아서 점화식을 세울 수가 없었다. 이 문제에서 중요하게 보아야 할 내용은 수를 선택할 때 한 개 이상의 수를 연속되게 선택해야 한다는 제약조건이 있다. 즉 1번 숫자를 선택한 후 2번 숫자를 선택하지 않으면 더 이상 선택할 수 가없는 것이다. -해법 그렇다면 이 문제는 어떻게 해결해야 할까? 별도의 dp배열을 생성하여 누적된 값과 현재부터 다시 선택을 시작한 값을 비교해주면 간단하다. 우선 기본적인 점화식은 dp [n] = dp [n-1] + cost [n]이 되는데(기본 누적 점화식), 연속해서 선택해야 한다는 제약조건이 존재하기 때문에 예를 들어, 2번까지 누적해서 선택한 결과와 2번이 첫 번째로 선택된 결과 중 큰 값을 취해야 한다는 것인데, 1번, 2번을 누적하..