순간을 기록으로

문제 https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 풀이 구하는 값은 사용할 수 있는 정사각형의 갯수이다. 크게 식으로 보면 다음과 같다. 전체 정사각형의 갯수 - 사용할 수 없는 정사각형의 갯수 = 사용할 수 있는 정사각형의 갯수 이것은 다음과 같다. w*h - ? = 사용할 수 있는 정사각형의 갯수 따라서 사용할 수 없는 정사각형의 갯수만 구할 수 있으면 문제를 풀 수 있다. ..

Jar(Java Archive)는 여러개의 자바클래스 파일과 메타데이터, 리소스(텍스트, 이미지 등)를 하나의 파일로 모아서 배포하기 위한 패키지 파일이다. 간단히 생각해서 압축 파일이라고 생각해도 된다. 파일 확장자는 .jar이다. 인텔리제이 안에서 실행하는게 아닌 콘솔에서 내가 만든 프로그램을 실행하려면 어떻게 해야할까? jar 파일을 실행하려면 'java -jar 파일명.jar'을 사용하면 된다. 만약 aws에 내가 만든 프로그램을 올리고 싶다면 jar 한 파일만 서버에 올려두고 실행하면 된다.(참고로 jar 명령어는 JDK에 포함되어 있다.) 빌드하고 실행하기 1. 콘솔에서 해당 프로젝트 루트위치로 이동한다. 그리고 jar파일과 비슷한 파일 형식 war이란 것도 있다. War 파일 형식은 클래스파..

문제 풀이 철수가 다리를 건너는 모든 경우의 수를 구해야한다. 복잡한 문제다. 큰 문제는 작은 문제로 만들고, 점점 크게 문제를 풀면 된다. 여기서는 동적 계획법을 사용한다. 먼저 첫 번째 돌다리에 오는 경우의 수는 1이다. 두 번째 돌다리에 오는 경우의 수는 2이다. 조심해야되는 것은 n을 입력받았을 때 n번째 돌다리에 오는 경우의 수를 구하는게 아니다. 개울을 '건너야' 한다. 그러므로 만약 7을 입력받았다면 그 다음 번째를 구해야 답이 나온다. 코드 package 인프런.동적계획법.돌다리건너기; import java.util.Scanner; public class Main { static int[] dp; public int solution(int N) { dp[1] = 1; // 첫 번째 돌다리에..

문제 풀이 처음 접하면 어려운 문제다. 한 번에 N번째 계단까지 오르는 방법의 수는 너무 많기 때문이다. 이러한 큰 문제는 문제를 본질은 같게 하면서도 작게 쪼개어 풀 수 있다. 바로 동적 계획법(dp, 다이나믹 프로그래밍)을 이용해서다. 동적 계획법은 큰 문제를 작은 문제로 만들어 푸는 방식을 말한다. 작은 문제를 조금씩 확장에서 앞에서 구했던 답을 기억(메모이제이션)한다. 그리고 확장된 문제에서 그 답을 사용해서 푼다. 끝까지 가면 마지막으로 구하고 싶었던 N번째 답을 구할 수 있다. 이러한 방식을 Bottom-Up 방식이라고 한다. 위의 문제를 풀어보자. 1번째 계단까지 가는 경우의 수는 1가지이다. 2번째 계단가지 가는 경우의 수는 2가지이다. 1, 2번 값을 미리 dp 배열에 초기화한다. dp[..

문제 풀이 점프의 '최소' 횟수를 구하는 문제다. 이렇게 최소를 구할 때는 최단거리 알고리즘을 사용한다. 코드 package 인프런.재귀와트리와그래프.송아지찾기.방법2; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { int[] dis = {1, -1, 5}; int[] check; // 값이 같은 노드를 다시 방문하지 않기 위해 Queue Q = new LinkedList(); public int BFS(int s, int e) { check = new int[10001]; // 값이 1~10000이니깐 check[s] = 1; Q.offer(s); // 노드 만들기 int ..

문제 풀이 좌표를 정렬할 수 있는지에 관한 문제다. x를 기준으로 오름차순으로 정렬하되 만약 값이 같다면 y를 기준으로 정렬해야 한다. 좌표는 x와 y로 이루어져 있다. 즉 독립적인 변수 한 개가 아니고 두 개로 구성된다. 따라서 객체를 만들어 관련된 두 변수를 갖게 만들고 객체를 정렬하기 위해 Comparable 인터페이스 compareTo() 메서드를 구현해야 한다. 코드 package 인프런.정렬과검색.좌표정렬.방법1; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Point implements Comparable{ // 좌표 int x; int y; public Point(int x,..

문제 풀이 '도착한 순서대로 진료를 받는다'를 통해 Queue를 이용한 문제를 알 수 있습니다. 코드 package 인프런.스택과큐.응급실.방법1; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Person { int id; int priority; public Person(int id, int priority) { this.id = id; this.priority = priority; } } public class Main { int solution(int n, int m, int[] arr) { int answer=0; Queue q = new LinkedList(); for (int i=0; i..

문제 N을 입력하면 1~N을 원소로하는 공집합을 제외한 부분집합을 출력하기 풀이 DFS를 이용해서 풀 수 있다. 예를들어 {1, 2, 3}이라는 집합이 있다고 하자. 이 집합의 공집합을 제외한 부분 집합의 갯수는 2^3-1이므로 7이다. 즉 원소마다 있느냐, 없느냐에따라 경우의 수가 2가지이고 원소의 갯수만큼 그만큼 곱해주면 모든 경우의 수가 나온다. 마지막에 공집합은 제외하니 -1을 하면된다. 그럼 DFS원리를 이용해서 이진트리로 풀어보자 코드 package 인프런.재귀와트리와그래프.부분집합구하기; /* * 어떤 집합의 모든 부분집합을 출력하는 문제 * */ public class Main { static int n; // 원소의 갯수 static boolean[] ch; // 부분 집합의 원소로 사용..