알고리즘(27)
-
[알고리즘/자바] 백준 2164번 - 카드2
2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제에서 알려준 동작을 정직하게 Java의 Stack을 통해 구현했다. 1부터 N까지의 숫자를 Stack에 넣고, while문을 통해 문제에서 제시한 동작을 수행하도록 했다. 아니나 다를까 시간초과ㅠㅠ 이렇게 하면 정답은 나오겠으나 입력 N이 커질수록 수행 속도가 떨어져 시간초과가 발생한다. 아래는 시간초과가 발생했던 코드. ( Java의 Stack을 썻던 이유는 Queue와 달리 Stack은 add를 통해 Top이 아닌 Bottom에도 데이터를 넣을 수 있기때..
2021.05.28 -
[Design Pattern] 옵저버 패턴(Observer Pattern)
Head First Design Patterns를 읽고 학습한 내용을 기록합니다. 정의 옵저버 패턴에서는 한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식으로 일대다(one-to-many) 의존성을 정의한다. 특정 객체에 변경이 발생했을때 그 객체에 의존하는 모든 객체에게 변경 사실을 알려 줄 수 있는 디자인 패턴이다. 책에선 신문 발행-구독을 예로 설명하고 있다. 여기서 정보를 구독하는 구독자를 옵저버(Observer)라고 부른다. 옵저버 패턴에서 발행자와 구독자는 느슨한 결합으로 연결되어 있는데 이 뜻은 두 객체가 상호작용을 하긴 하지만 서로가 내부적으로 어떤일을 하는지는 관심이 없다는 걸 의미한다. 발행자는 데이터를 제공만 할 뿐이지 구독자들이 ..
2021.02.01 -
[알고리즘/자바] 백준 9252번 - LCS 2
9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 처음에 LCS를 푸는 알고리즘을 모르고 접근했다가 한참 고생했다. 아래는 처음에 접근한 방식. 입력으로 문자열 2개가 주어지는데 이를 n1, n2라고했다. n1의 첫번째 문자를 잡고 n2를 처음부터 순회한다. n2에 일치하는 문자가 있다면 정지하고 n1의 두번째 문자를 잡고 n2를 정지한 부분에서 부터 시작한다. 이 방식으로 n2도 똑같이 진행한다. 위에서 생각한 방식으로 구현한 소스코드. 2중 for문을 사용했다..
2021.01.28 -
[알고리즘/자바] 백준 4811 - 알약
4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net DP를 활용해야된다고 해서 계속 수식만 만들려다 시간을 많이 잡아먹었다. 코드를 짜보고나서 더 깊게 생각하는것도 나쁘지 않은 방법. 너무 수식만드는데 얽매이지 말아야겠다. 알약이 1개인 경우는 WH (1개) 알약이 2개인 경우는 WHWH , WWHH (2개) 위에서 알수 있듯이 H는 W보다 먼저 많이 나올수 없다. 알약이 2개일떄 WHHW 같은 것은 불가능하다. (병속에 H가 하나도 없는데 H를 또 뽑는건 말이 안된다. ) 따라서 이 문제에서는 병속에 남은 W와 H의 수를 기억..
2021.01.21 -
[알고리즘/자바] 백준 1699번 - 제곱수의 합
1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀고나면 별거 아닌것 같은데 정답까지 생각이 도달하는데 시간이 꽤 걸렸다. ( 입력이 10 일때 ) dp[10]을 구하기 위해서 이전에 구한 dp[1] ~ dp[9]를 활용할 수 있는 방향으로 머리를 굴렸다. dp[i] = i를 구하기 위한 최소 항 갯수로 dp를 셋팅하고 아래 처럼 모두 적었다. 위에 작성한 부분을 잘보면 dp[10]을 구하기 위해선 아래와 같은 방법을 사용할 수 있다. 이를 코드로 구현하면 아래와 같다...
2021.01.18 -
[알고리즘/자바] 백준 11053번 - 가장 긴 증가하는 부분 수열
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net {8, 2 , 3 , 4} 라는 수열이 있다고 하자. 여기서 가장 긴 증가하는 부분수열을 구하면 {2,3,4}이다. 처음 접근법으로는 단순하게 전수조사했다. {8,2,3,4}라는 수열이 있을때 먼저 8을 선택한 경우와 그렇지 않을 경우를 나눈다. 8을 선택하고 다음으로 가면 2가 있는데 2는 8보다 작으므로 선택할수 없다. 따라서 바로 3으로 넘어가도록 했다. 이런식으로 가장 마지막에 ..
2021.01.17