begong블로그

처음 볼땐 감이 안잡히던 다이나믹 프로그래밍 문제 절차는 다음과 같다 1.전봇대 A를 기준으로 정렬을 한다(B기준이여도 됨) 2.전봇대 A기준으로 정렬된 배열에서 [N][1]번째 (전봇대B) 배열의 가장 긴 증가하는 부분수열을 구한다 3.총 갯수에서 2에서 푼 가장 긴 증가하는 부분수열의 길이를 빼준다. 가장 긴 증가하는 부분수열이 다른 일을 안해도 유지될 수 있는 전깃줄의 개수이다. 가장 긴 감소하는 부분수열은 안되나? => 안된다. 1 => 10, 2=>9로 될시에 x자로 교차해버리기 때문에 틀리다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arr..

스택을 활용하는 자료구조 문제 stack의 크기가 3이상이고, 새로 들어오는 토큰이 "P", 스택의 가장 위에 있는 토큰이 "A"일때 하나씩 꺼내며 검사를 시작한다. 스택의 상위 요소가 "PPA"였다면 (코드에서는 굳이 Reverse를 안해서 "APP"로 검사) "P"만 넣어주면 된다. 만약 아니라면 다시 원상복귀 시킨다 1차적으로 스택에 넣으며 검사를 했다면 그다음은 뒤에서부터 거꾸로 검사를 해야한다. (반례는 찾지 못했는데 뒤에서 검사를 해야 정답이 나왔다) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; class Main { public ..

다이나믹 프로그래밍 문제 입력 받는 방법이 괴랄해서 문제이지 풀이 자체는 어렵지 않다. dp[T][N+2] 배열을 만든다 여기서 T는 주사위를 굴린 횟수, N+2는 시작점, 끝점을 포함한 칸의 개수이다. 주사위를 n번 굴렸을때 도달할 수 있는 지점에서 획득할 수 있는 코인의 최대치를 구한다. 구하는 방법은 주사위를 n-1번 굴렸을때, 주사위의 눈 s가 나와서 현재의 지점에 도달했다고 가정하는 것이다. (그래서 3중 반복문이 쓰인 것이다) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main{ public stati..

다이나믹 프로그래밍 문제이다. 하나의 조건에만 집중에서 풀면 쉽게 풀린다. n번째 집과 n+1번째 집의 색깔만 안겹치면 된다. Blue Red Blue, Red Blue Green 등 모두 상관없다. 따라서 n+1번째 집을 Red로 칠하고 싶다면 n번째집의 Blue Green중 작은 값을 가져와 Red를 칠하는 비용을 더해주면 된다. Red, Blue, Green 모두 칠하는 경우를 기록해놓고 반복해주면 dp 배열의 마지막에 모든 집을 칠하는 비용의 경우가 나오고 거기에서 최소값을 구해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays;..

Stack을 활용하는 문제 한 방향으로만 건물을 볼수있다 => 이미 앞에있는 건물들은 신경안써도 된다. 이미 stack안에 존재하는 건물들이 새로 들어온 건물을 볼수 있냐 없냐에만 신경쓰면됨 => 이미 stack에있는 건물보다 큰 건물이 들어왔을때는 stack에서 제거 : stack에 있는 건물들은 이 건물을 볼 수 없기 때문에 => stack에 있는 건물보다 작은 건물이 들어왔을때 : stack에 push 이 로직으로 진행한다면 stack안에는 새로 들어오는 건물을 볼 수 있는 건물만 남게 된다. 새로 들어온 건물을 몇개가 볼수있느냐? 로 이해하면 금방 풀리는 문제 단 건물의 크기가 10억까지 존재함으로 long타입을 써야 overflow가 나지 않는다. import java.io.BufferedRea..

소켓통신 프로그래밍 소캣 생성 및 기본 연결 Client public class client{ static final String IPADDRESS = "127.0.0.1"; static final int PORTNUM = 8000; public static void main(String[] args) throws IOException { try(Socket socket = new Socket(IPADDRESS, PORTNUM)){ System.out.println("서버연결완료"); } } } ip와 port를 통하여 서버와 연결 Server public class server{ //8000번 포트로 서버오픈 public static void main(String[] args) throws IOExce..