모항이코딩한다

풀이방법 사용된 것: Stack 2022.07.19 후위 표기식은 무조건 앞에서부터 계산하면 올바른 답이 나오도록 되어있다. 그러니 그냥 식을 앞에서부터 탐색하며, 식이 끝날 때까지 아래와 같은 과정을 반복하면 된다. 피연산자가 등장하는 동안에는 피연산자들을 스택에 차곡차곡 쌓다가, 연산자가 등장하면 즉시 그 연산자의 바로 직전에 있는 두 개의 피연산자 즉 스택의 top과 top 바로 아래에 있는 피연산자 두 개를 꺼내온 뒤, 그 두 개를 가지고 연산을 한 값을 다시 스택에 쌓아주면 된다. 등장한 연산자가 곱셈/나눗셈인지, 덧셈/뺄셈인지는 신경 쓸 필요 없다. 그들 사이의 우선순위까지 모두 고려하여 그냥 앞에서부터 계산하면 되도록 정렬해놓은 것이 바로 후위 표기식이기 때문이다. 코드 Java(2022.0..

풀이방법 사용된 것: 수학 2022.07.13 간단한 문제이지만 기억해야 할 것이 한 가지 있어서 적는다. 정답을 구하기 위하여 나눗셈과 곱셈을 한 번씩 해야 하는 문제이다. 이때 주의할 점은 정답을 출력할 때 소숫점 아래를 모두 버린다고 해도, 출력연산 대상인 세 수를 정수 형태로 읽어오면 안 된다는 것이다. 먼저 double 등의 소수 타입으로 받아온 다음, 연산을 모두 마치고, 정답이 도출된 뒤에 그 정답을 정수로 만들어 출력해야 한다. 그러지 않으면 오차가 발생한다. 예를 들어, 1 / 3 * 4 라는 연산을 하는데, 세 수를 모두 정수로 읽어왔다고 치자. 1 / 3 의 값은 0.33333.....이지만, 1과 3 두 수 모두 정수형이라면 프로그램은 소숫점 아래를 버리고 0이라는 정수형의 결과를 ..

풀이방법 사용된 것: Comparator Overriding 2022.07.11 일단 문제에서 말한 기준대로 나라를 내림차순으로 쫙 정렬한다. 이렇게 정렬된 배열 상에서, K나라의 위치(인덱스)를 찾는다. 그 인덱스 값을 정수형 변수 answer에 저장해둔다. 만약 K나라와 동점인 나라가 하나도 없다면 answer+1이 답이다. 동점인 나라가 존재한다면 동점인 나라의 개수만큼을 answer에서 빼준 뒤에 1을 더하면 그것이 답이다. 따라서 아래의 과정을 통해 동점인 나라의 개수를 센다. 먼저 동점인 나라의 개수를 저장할 정수형 변수 cnt를 선언하고 0으로 초기화한다. 인덱스가 answer-1인 나라부터, 즉 K나라의 바로 직전 순서로 정렬되어있는 나라부터 시작하여 1등 나라(인덱스 0)까지 탐색한다. ..

강의 초반부에서는 트리에 대한 기본적인 설명을 해주었다. 특히 적어둘 만한 것으로는 이진 트리에 관한 내용이 있었다. 학교 수업에서 배웠으나 잊고 있었던 내용인데, 이 기회에 확실히 기억해둬야겠다. 포화, 완전 이진 트리의 인덱스 포화 이진 트리와 완전 이진 트리는 그 정의로 인해 반드시 인덱스가 특정한 규칙을 띤다. 루트의 인덱스를 1로 하고 각 레벨의 왼쪽부터 차례대로 번호를 매기면 각 노드의 인덱스는 다음의 그림과 같이 된다. 이때 요소들은 반드시 다음의 규칙을 따른다. 부모의 인덱스를 i라 할 때, 왼쪽 자식의 인덱스는 2i 이고 오른쪽 자식의 인덱스는 2i+1 이다. 이진 트리의 순회법 이진 트리의 순회법에는 3가지가 있다. 전위 순회(Preorder) : 루트 - 왼쪽 서브트리 - 오른쪽 서브..

풀이방법 2022.06.23 간단한 문제이지만 기억해야 할 내용이 하나 있어서 적는다. 다음과 같이 Scanner를 사용한 코드를 제출하면 런타임 에러(NoSuchElementException)가 발생한다. import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); for(int i=0; i=0; j--) System.out.print(arr[j]); System.out.print(System.lineSe..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.06.19 브루트포스로 풀면 매우 쉽다. 굳이 이분 탐색을 써보려고 하다가 계속 실수를 해서 그냥 브루트포스로 풀었다. 각 버스 노선마다, 영식이의 터미널 도착 이후에 출발하는 배차들 중 가장 이른 것 하나만 다룬다. 이 조건을 만족하는 버스 출발 시간은 각 노선마다 1개 혹은 0개 있다. 이렇게 찾아낸 출발 시간들 중 최솟값을 취하면 된다. 영식이의 터미널 도착 이후에 출발하는 배차가 하나도 없을 때, 즉 영식이가 탈 수 있는 버스가 없을 때는 화면에 -1을 출력한다. 코드 Java(2022.06.19) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStrea..

풀이방법 사용된 것: 수학 BigInteger 2022.06.19 반복문을 통해 곱셈과 나눗셈을 해서, 예전 수학 시간에 배웠던 공식 그대로 계산해주면 된다. 이때 정답의 값이 매우 커질 수 있으므로 꼭 BigInteger를 사용해야 한다. long으로도 부족하다. 코드 Java(2022.06.19) import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); //입력값 읽어오기 int n = sc.nextInt(); int m = ..

풀이방법 사용된 것: 수학 에라토스테네스의 체 2022.06.19 에라토스테네스의 체를 사용하여 1부터 1,000,000 사이의 모든 소수를 구해놓는다. 구해놓은 데이터를 바탕으로 정답을 출력하면 된다. 코드 Java(2022.06.19) import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner (System.in); int start = sc.nextInt(); int end = sc.nextInt(); //에라토스테네스의 체 수행 boolean[] arr..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.06.17 주어지는 문자열의 길이가 최대 50이므로, 단어를 쪼개는 두 지점을 고르는 경우의 수가 최대 50 곱하기 49 밖에 안 된다. 각 경우마다 쪼개고 뒤집는 과정을 수행하는 데에는 상수시간이 걸린다. 따라서 브루트포스 알고리즘으로 충분히 풀 수 있는 문제이다. 쪼개고 뒤집을 때는 String의 substring 메소드와 StringBuffer의 reverse 메소드를 사용했다. 이렇게 만들어낸 모든 문자열은 TreeSet에 저장하였고, TreeSet의 가장 앞에 있는 문자열을 화면에 출력하여 해결하였다. 코드 Java(2022.06.17) import java.io.BufferedReader; import java.io.IOException; im..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.06.17 문제에 나와있는 것을 그대로 해보면 풀리는 문제이다. 수의 범위가 적기 때문에 브루트포스 식으로 일일이 세어서 풀어도 시간초과 없이 해결된다. 나는 다음과 같이 구현하였다. 먼저, 현재 존재하는 땅 중 가장 낮은 땅보다 더 파내려가면 무조건 손해이며, 가장 높은 땅보다 더 쌓는 것도 무조건 손해이다. 그러므로 정답은 반드시 본래 존재하는 땅의 높이 중 최솟값과 최댓값 사이에 존재한다. 본래 땅 높이의 최솟값부터 최댓값까지에 대하여, 모든 땅을 해당 높이로 평평하게 맞추려면 블럭과 시간이 얼마나 필요한지 직접 세었다. 그 다음, 주머니에 있는 블럭이 모자라지 않았다고 판별될 때만, (걸린 시간, 높이)를 짝지어 TreeMap에 넣었다. Key값을..