241226 TIL

 

프로그래머스 3진법 뒤집기

https://school.programmers.co.kr/learn/courses/30/lessons/68935

프로그래머스

 

10 진법을 n진법으로 바꾸는 방식은 원래

String a = "";
//b가 진법
while(n>0){
	a = (n%b) + a;
    n = n / 3;
}

 

이런식으로 나누면서 만드는 방식으로 알고 있었는데

// 10진법을 3진법으로 변경
String s = Integer.toString(n, 3);

// 3진법을 10진법으로 변경
int a = Integer.parseInt(s,3);

이런 방식으로 아주아주 간단하게 변경가능하다! 기억해두자!

 

 

• 백준 11054번 가장 긴 바이토닉 부분 수열
  • 입력 : 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)  
  • 출력 : 가장 긴 바이토닉 수열의 길이 출력
  • 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라 한다.
  • dp를 두 종류로 나눠 증가하는 값의 수량을 찾는 dp와 감소하는 값의 수량을 찾는 dp로 구분
  • 한 지점에서 이전부터 증가해온 값과 앞으로 감소할 수 있는 값의 합이 최대한 부분을 찾고 두 값을 더한 값에 -1 하여 출력

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int arr[] = new int[n];
        int mindp[] = new int[n];
        int maxdp[] = new int[n];
        for(int i=0;i<n;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	mindp[i] = 1;
        	maxdp[i] = 1;
        }
        
        for(int i=1;i<n;i++) {
        	for(int j=0;j<i;j++) {
        		if(arr[j] < arr[i])
        		maxdp[i] = Math.max(maxdp[i], maxdp[j]+1);
        	}
        }
        mindp[n-1] = 1;
        for(int i=n-2;i>=0;i--) {
        	for(int j=n-1;j>i;j--) {
        		if(arr[j] < arr[i])
        		mindp[i] = Math.max(mindp[i], mindp[j]+1);
        	}
        }
        int max = 0;
        for(int i=0;i<n;i++) {
        	if(max < maxdp[i]+mindp[i]) {
        		max = maxdp[i] + mindp[i];
        	}
        }
        System.out.println(max-1);
    }
}

 

 

• 백준 2565번 전깃줄
  • 입력 : 두 전봇대 사이의 전깃줄 개수와 연결되는 위치의 번호가 차례로 주어진다.
  • 출력 : 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력
  • LIS 문제다! 가장 길게 증가하는 수열 문제로 생각하자
  • Comparator을 이용해서 배열을 정렬하고 하나씩 줄을 추가해서 선에 겹치는지 확인하자
  • 제일 핵심 코드는 아래로 B 전봇대의 값이 안겹치면 겹치지 않는 선으로 dp 값에 1을 더해주자

for(int j=0;j<i;j++) {
        		if(arr[i][1] > arr[j][1]) {
        			dp[i] = Math.max(dp[i], dp[j]+1);
        		}
        	}

 

전체 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int arr[][] = new int[n][2];
        int dp[] = new int[n];
        for(int i=0;i<n;i++) {
        	StringTokenizer st = new StringTokenizer(bf.readLine());
        	arr[i][0] = Integer.parseInt(st.nextToken());
        	arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr , new Comparator<int[]>() {
			@Override
			public int compare(int[] l1, int[] l2) {
				// TODO Auto-generated method stub
				return l1[0] - l2[0];
			}
        	
        });
        int max = 0;
        for(int i=0;i<n;i++) {
        	dp[i]=1;
        	for(int j=0;j<i;j++) {
        		if(arr[i][1] > arr[j][1]) {
        			dp[i] = Math.max(dp[i], dp[j]+1);
        		}
        	}
        	max = Math.max(dp[i], max);
        }
       System.out.println(n - max);
    }
}

 

• 백준 9251번 LCS
  • 입력 : 두 문자열 최대 1000글자, 알파벳 대문자로만 구성
  • 출력 : 두 문자열의 LCS 길이를 출력
  • 부분 수열 중 가장 긴 것을 찾는 문제로 1시간 실패하고 검색해서 알게 되었다.
  • 부분 수열에서 순서가 지켜지기 때문에 각 문자열의 문자를 비교하며 서로 같으면 1씩 증가시키기
  • 표를 한번 그려보면 쉽게 점화식을 찾을 수 있다 나중에 한번 그려보자

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s1 = bf.readLine();
        String s2 = bf.readLine();
        int dp[][] = new int[s1.length()+1][s2.length()+1];
        for(int i=1;i<s1.length()+1;i++) {
        	for(int j=1;j<s2.length()+1;j++) {
        		if(s1.charAt(i-1)==s2.charAt(j-1)) {
        			dp[i][j] = dp[i-1][j-1]+1;
        		}
        		else {
        			dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        		}
        	}
        }
        System.out.println(dp[s1.length()][s2.length()]);
    }
}

 

 

• 백준 1912번 연속합
  • 입력 : 첫째 줄에 정수 n (1~100,000) 둘째 줄에 n개의 정수로 이루어진 수열 수는 -1000~1000
  •  출력 : 연속된 몇 개의 수를 선택해 구할 수 있는 가장 큰 합
  • 반복문으로 dp[i]의 값을 dp[i-1] + arr[i] 와 arr[i] 값을 비교해서 큰 값을 넣는 식으로 반복
  • 전체 dp 값 중 가장 큰 값이 연속 합의 가장 큰 값! 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int arr[] = new int[n];
        int dp[] = new int[n];
        for(int i=0;i<n;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	dp[i] = arr[i];
        }
        int max = dp[0];
        for(int i=1;i<n;i++) {
        	dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
        	max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

 

 

팀 프로젝트 : 자기 소개 페이지 제작 중 배운 점!

 

• 카드 로직 제작 중 다른 html 파일로 id 값을 전달해야하는 경우 URL 쿼리 스트링에 id 값을 추가하여 넘기는 방식을 사용한다.
• id를 URL로 전달

window.location.href = "./~~html?id="+id;

 

• 해당 html에서 쿼리 스트링으로 전달된 id 값 읽기

const urlParams = new URLSearchParams(window.location.search);
const id = urlParams.get("id"); // 전달된 id 값 가져오기

 

• 이렇게 쉽게 id 값을 넘겨 받을 수 있다!
• 주의할 점은 비밀번호 같은 값은 전달해선 안된다! 
• LocalStorage를 이용하여 ID 값을 넘겨줄 수도 있다고 하는데 다음에 시도해보자!

 

• 아이콘에 링크를 달아보자!
• 기존의 <i></i> 태그는 기울임꼴(Italic) 의 역할
• 요즘의 역할은 아이콘 라이브러리에서 아이콘을 나타내는 역할로 사용!
• Font Awesome 아이콘 라이브러리 사용

<link href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.0.0-beta3/css/all.min.css" rel="stylesheet">

<i class="fas fa-home"></i> <!-- 집 아이콘 -->
<i class="fab fa-github"></i> <!-- GitHub 아이콘 -->
<i class="fas fa-link"></i> <!-- 링크 아이콘 -->