일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- Recylcer
- bytecode
- 취약점
- 심리학
- Interface
- ㅇ
- abstract
- 심리여행
- opcode
- bytecode 분석
- HelloWorld
- 회피
- Transition
- 일상회피
- Navigation Component
- IMPLEMENT
- 치유
- 일상탈출
- jvm
- throws
- static
- 여행
- javap
- 보안
- 여행계획
- extends
- 보안취약점
- 버킷리스트
- Shared Elements
- Android
- Today
- Total
목록Algorithm/baekjoon (41)
패스트터틀
https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 www.acmicpc.net 초반에 내가 풀었던 코드이다. package GreedyAlgorithm; import java.util.Scanner; publi..
https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 오름차순으로 정렬후에 시작한다.(이거 안했다가 한번 틀렸다.) 복잡하게 생각할거 없이 왼쪽부터 차례대로 붙힌다고 생각하면 된다. 왼쪽부터 차례대로 붙히면서 테이프가 닿지 않으면 개수를 하나 추가하고 그다음거에서부터 다시 테이프를 붙힌다. 위의 과정처럼 너무 어렵게 생각했었지만 그냥 함정이였다. 이게 왜 그리디 알고리즘인지 모르겠다. package GreedyAlg..
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30 www.acmicpc.net = weight[] = 3 1 6 2 7 30 1 1) 우선 오름차순으로 정렬을한다. = 1 1 2 3 6 7 30 2) 숫자 1이 들어있지..
https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net N>=3,M>=7이상부터는 1. 2칸 위로, 1칸 오른쪽 2. 2칸 아래로, 1칸 오른쪽 이 두방법으로 왔다갔다 하는것이 최댓값이다. 모르면 그림그려가면서 경우의수 따져보면 바로나온다. 이게 왜 그리디 알고리즘인지 모르겠다. 다들 if문으로 풀었다. package GreedyAlgorithm; import java.util.Scanner; public class _1783 { static int night_max(int n,int m){ if(n==1) retu..
https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. www.acmicpc.net 232010 일경우 반대부터 수를 넣는다. for (int i = N ; i >= 1; i--) { list.add(height[i],i); } 0 -> 6을 0에다가 추가하기 1 -> 5을 1에다가 추가하기 0 -> 4을 0에다가 추가하기 2 -> 3을 2에다가 추가하기 3 -> 2을 3에다가 추가하기 2 -> 1을 2에다가 추가하기 package ..
https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 이 문제를 풀기위해서 dp -> 2xn 타일링 -> 2xn 타일링2 -> 외판원순회 -> 타일채우기 -> bruteforce -> 부분수열의합 -> dp -> -> lis O(n^2) -> list O(nlogn) 문제를 풀고 왔다. 너무나 오래걸렸다. 최장길이를 구하는 lis와 동일한 문제이다. 다만 n..
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 기존에 하던 방식에서 굳이 자기보다 작은것들을 찾고 거기서 최댓값을 찾기위해 다 검색을 해야하는가? 라는 의문에서 시작하여서 더 빠르게 진행하는 방식으로 이끌어 갈수있다. X,Y테이블을 만든다. X테이블은 기존하던것처럼 A와 D에관한 테이블이고 Y테이블은 D에관한 테이블이다. table X: (D는 ..
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net LIS = Longest Increasing Subsequence, 최장증가수열이다. 주어진 값에서 증가하는 수의 집합들중 가장 큰 원소의 개수를 구하는 방법에 관한 문제이다. 어떠한 알고리즘이 해당문제를 푸는데 최적화된 알고리즘인것을 보장할수있는것은 어떻게 알수가 있을까? 문제를 풀다보니 회의감이 ..