본문 바로가기

분류 전체보기

 (107)
[JAVA] BOJ 11399 ATM 그리디 알고리즘 문제 중에서도 가장 쉬운 문제인 것 같다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 찾는 문제인데 단순하게 각 사람의 기다리는 시간이 주어졌을 때 오름차순으로 정렬해서 세우는 것이 최소이다. 왜냐하면 돈을 인출하는데 걸리는 시간이 긴 사람이 앞에 있으면 계속 누적이 되기 때문에 값이 커질 수밖에 없다. 따라서 주어진 배열을 오름차순으로 정렬한 다음 각 요소를 이전 값까지의 누적 값과 더해 새롭게 저장한다. 즉, A(i) = A(i-1) + A(i) 이다. Input에는 BufferedReader 와 Output에는 System.out.println을 사용했다. public class Main { public static void main(String[] args) throw..
[JAVA] BOJ 11047 동전 0 그리디 알고리즘은 탐욕 알고리즘이라 하여 뒤를 생각하지 않고 각 상황에서 최선의 선택만을 하는 알고리즘을 의미한다. 이 문제에서는 예제에서 주어진 4200원을 만들기 위해 4200원보다 작은 것 중 가장 큰 동전을 선택하여 (예제에선 1000원) 개수에 4200/1000 한 것을 더해주고 K = 4200%1000 = 200으로 만들어주어 K가 0이 될 때까지 위의 과정을 반복합니다. 첫 번째 동전의 값은 1이기 때문에 K가 0이 안될 가능성은 없다. Input으로 주어지는 값이 많기 때문에 BufferedReader를 사용했고 출력되는 수는 한 개 밖에 없기 때문에 System.out.println을 사용했다. public class Main { public static void main(String[]..
[JAVA] BOJ 1158 요세푸스 문제 원으로 앉아있다는건 배열을 순환한다는 것과 같다. 따라서 배열의 끝에 도착하면 다시 처음으로 돌아가도록 해주는 것이 핵심이다. 또한 K번째 사람을 제거한다는 것은 배열을 순환하면서 K번째를 방문했으면 넘어가도록 구현하였다. 독특한 출력형태로 input은 Scanner로 받고 출력은 BufferedWriter를 사용하였다. public class Main { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String st = sc.nextLine(..
알리바바 기업분석 Information 기업명 : 알리바바 Nasdaq BABA 사업 : Internet Retail CEO : Mr. Yong Zhang CEO 이력 : 장융 회장은 조용하며, 자신을 외부에 잘 드러내지 않는다. 그래서 중국 최대 전자상거래 기업의 수장이지만, 잘 알려지지 않았다. 장 회장이 알리바바에서 맡은 첫 직책은 온라인 쇼핑몰 타오바오(淘寶)의 최고 재무책임자(CFO)였다. 그가 알리바바로 입성한 2007년 당시 타오바오는 인기 있는 웹사이트였지만, 가짜 상품으로 가득 차 있었다. 게다가 수익은 바닥이며 재무상태도 엉망이었다. 블룸버그통신은 장 회장이 재무제표를 보더니 "오 예수님"하고 탄식했다고 보도한 바 있다. 장 회장은 타오바오의 정상화를 위해 애썼고, 결과는 찬란했다. 지난 2016년 타오..
[JAVA] BOJ 9012 괄호 스택을 이용해서 푸는 문제이다. Stack은 LIFO구조로 한쪽 끝이 막혀있는 병을 생각하면 된다. 이 문제의 경우 입력값으로 들어오는 괄호를 병(스택)에 넣기 전에 병에 가장 마지막에 들어가 있는 괄호와 더해 () 즉 VPS 인지 검사한 다음 만약 VPS라면 병에 들어있는 마지막 괄호를 제거해주고 아니라면 병에 넣어주면 된다. INPUT/OUTPUT 에는 BufferedReader/BufferedWriter 를 사용하였다. import java.io.*; import java.util.*; public class Main { public static long[] N_li = new long[101]; public static void main(String[] args) throws IOException..
하이트진로 기업분석 Information 기업명 : 하이트진로 000080 사업 : 음식료품 CEO : 김인규 CEO 이력 : 1962년 11월 16일 서울에서 태어나 배재고등학교와 연세대 수학과, 연세대 경영대학원을 졸업했다. 1989년 하이트맥주에 입사한 뒤 한 회사에서만 30년여 동안 인사와 마케팅, 경영기획, 영업 업무를 두루 맡은 ‘하이트 맨’이다.하이트맥주 영업본부 본부장과 하이트맥주 부사장을 거쳐 하이트진로 대표이사 사장에 선임됐으며 하이트진로홀딩스 대표이사 사장도 겸직하고 있다. 신제품 ‘진로’를 내놓아 소주시장 점유율 1위 자리를 단단히 다진 데 이어 맥주시장에서 아성을 되찾기 위해 ‘테라’에 사활을 걸고 있다. 김인규는 사업 추진력이나 정무적 감각도 뛰어나다는 평가를 받는다. 영업과 생산 현장에서 직원들과..
[JAVA] BOJ 11053 가장 긴 증가하는 수열 동적 계획법 문제답게 메모이제이션과 점화식을 생각해봐야 한다. A= {10, 20,10, 30, 20, 50} 라면 F(N) 은 N번째 요소가 이전 요소 중 몇 번째로 증가하는 수열인지 저장한다. 즉, 3번째 요소인 10은 이전 값 {10, 20} 중 1번째로 증가하는 수열이기 때문에 1이 F(3) = 1이 된다. 이처럼 A의 모든 요소를 반복문으로 돌면서 F(N) 값을 저장한 뒤 출력할 때는 F(N) 중 가장 큰 값을 출력하면 된다. 코드로 보면 import java.io.*; import java.util.*; public class Main { public static Integer[] DP; static ArrayList cost = new ArrayList(); public static void..
[JAVA] BOJ 1463 1로 만들기 생각보다 간단하게 풀 수 있는 문제였는데 정답 비율이 낮아서 놀랐다. 동적 계획법 문제이다 보니 이 역시도 메모이제이션과 점화식만 찾아내면 문제를 풀 수 있다. 이 문제는 연산을 사용하는 횟수의 최솟값을 출력하는 문제이다 보니 메모이제이션 해야 하는 값은 주어진 N을 1로 만드는데 까지 드는 연산 횟수의 최솟값이다. N이 2로 나누어지는지 3으로 나누어지는지에 따라 다른 케이스로 나뉘며, 각 케이스마다 N을 1로 빼는 케이스가 더해져 최솟값을 비교해야 한다. 예제를 보면, 10을 입력했을 때 10은 2로 나눠지기 때문에 F(10) = Math.min(F(10/2),F(10-1)) + 1으로 구할 수 있다. 한번 다음 단계로 갈 때마다 횟수를 추가해줘야 하기 때문에 +1을 한 것이다. 위의 식은 다시 F(..

티스토리툴바