koucop의 개발탐방기 koucop의 개발탐방기

이번에는 BOJ의 1717번 문제 "집합의 표현"를 풀어보도록 하자 문제를 풀어서 설명해 보면, 입력으로 맨처음에 주어지는 원소들의 총 크기, n 이 주어지고, 연산의 개수 m이 주어진다. 연산중에서 "0 a b"의 형태로 주어지는 것은 합집합으로, a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합치는 연산이다. 그리고, "1 a b"의 형태로 주어지는 연산은 확인하는 연산으로, 두 원소 a b가 같은 집합에 포함되어 있는지를 확인해서 포함되어 있으면, "YES"를 아니면 "NO"를 출력하는 문제이다. 가장 기본적인 디스조인트셋(Disjoint-set)문제이다. 이런 문제는 기본적으로, 초기에 set을 만들어주는 makeset public static void makeSet(int n){ par..

이번에는 백준알고리즘의 1049번 "기타줄"문제이다. 다 같이 기타리스트 강토를 도와서 기타줄을 가장 저렴하게 살 수 있게 도와줘 보자 문제 자체는 매우 간단하다. 일단, 입력으로 기타리스트 강토씨 기타의 끊어진 기타줄 개수 N과 기타줄을 살 수 있는 브랜드 M이 주어진다. 먼저 각각의 브랜드에서는 기타줄 6개가 같이 들어있는 패키지 가격이있고, 낱개로 살 때의 가격 2가지의 가격이 있고, 끊어진 기타줄 N개를 사기위해 필요한 최소의 돈을 출력해주는 프로그램을 만들어 주면된다. 먼저 패키지 가격을 집어넣을 Int행렬인 pack과, 낱개 가격을 집어넣을 Int행령인 one을 지정하고, 오름차순으로 정렬해준다. int[] pack = new int[M]; int[] one = new int[M]; for (..

이번엔는 BOJ의 17298번 오큰수를 풀어보도록 하자 일단 크기가 N인 수열 A 를 입력으로 받고 각 원소 Ai 에 대해서 오른쪽에 있으면서 해당 원소보다 큰 가장 왼쪽에 있는 수를 출력하는 문제이다. 문제자체는 간단한데, 시간제한은 1초로 짧고, 입력으로 주어지는 수열A의 크기가 1,000,000(백만) 으로 꽤나 크다는 것을 알 수 있다. 즉, 그냥 루프로 돌려버리면 안된다는 것이다. 일단, 개삽질했다... 머리가 나빠서 그런지 될 것 같은데 계속 안되서 컴퓨터 부실뻔하다가 다시 처음부터 마음을 가다듬고 만들었다. 일단, 입력값을 받는 루프안에 모든 것을 해결하려고 했다. 그래서, LIFO 방식인 Stack을 이용해서 이전 값들을 비교하는 방식을 선택했다. 먼저, Int배열인 ans배열을 만들어 주..

이번에는 BOJ의 9461 번 문제 파도반 수열을 풀어보도록 하자 처음에 변의 길이가 1인 정삼각형부터 시작해서, 변을 이어가며 정삼각형을 그리는 문제이다. 일단, P(1) = 1, P(2) = 1, ... , P(10) = 9, P(11) = 12 가 되는 것이 그림으로, 예시로, 주어져있다. 입력으로는 테스트케이스 T가 먼저 주어지고, 각각의 테스트 케이스에 P(N) 의 N의 값이 주어진다. 출력으로 각 테스트케이스마다 P(N) 값을 출력해주면 되는 문제이다. 이문제를 풀때, 일단 N = 5 일때 까지는, 예외로 생각하고 문제를 풀었다. N = 6일 때부터 P(N) = P(N - 1) + P(N - 5) 가 되므로, 이를 이용해서 N = 1 부터 N = 100까지의 P[N]의 값을 먼저 구하게 해서,..

백준 알고리즘 1436번 영화감독 숌 문제를 Java로 풀어보자 살짝 문제를 이해하기가 힘들 수도 있다 영화감독 숌 씨는 네이밍 센스가 오지게 없으셔서 영화제목을 꼭 세상의 종말 + 666이 들어가게 만드신다는데, 두번째 편은 1666, 세번째 편은 2666, ... , 일곱번째 편은 6660, 여덟번째 편은 6661, ... 이렇게 만드신다는 건데, 살짝 생각하기 어려울 수도 있다. 여기서 적용시킨 알고리즘은 브루트포스로 완전탐색을 해서 문제를 풀었다. 성공한 코드는 다음과 같이 작성했다. import java.io.*; import java.util.*; public class sample { public static void main(String[] args) throws Exception { Bu..

우리 모두 BOJ 의 1904번문제 01타일을 풀어보도록 하자 문제 자체는 무척이나 간단하다 일단 2진 수열을 만드는 문제인데, 0은 없고, 00 만 있는 상황이다 예를들어, 크기 N = 1일 때, (1) 밖에 없으므로 수열의 개수는 1이고, N = 2 일 때, (11, 00) 으로 수열의 개수는 2개가 된다. N = 3 일 때, (111, 100, 001) 으로 수열의 개수는 3개가 된다. 매우 간단한 다이나믹 프로그래밍(Dynamic Programming) 문제이다. N = 3 일 때, 가능한 수를 보면, N = 1 일 때, 가능한 (1) 에다가 00 을 더한 100 N = 2 일 때, 가능한 (11, 00) 에다가 1을 더한 111, 001 이렇게 3개 이다. N = 4 일 때도 똑같이 N = 2 ..

BOJ의 가장 최신문제인 17300번 패턴을 풀어보자 일단, 문제가 오지게 길다 풀어서 설명해 보자면, 안드로이드의 패턴 형식이 적절한지 아닌지 판단하는 문제로, 일단 3X3 으로 구성된 잠금화면이 주어진다. 입력으로 주어지는 수열을 통해 유효한 패턴이면 "YES" 를 아니면 "NO" 를 출력하면 되겠다 일단 주어진 수가 중복되는지 알려줄 boolean배열인 numberDup, 이전 수를 집어넣을 pre, 답이무엇인지 체크해줄 chk를 먼저 지정해주고, amhoChk(int cur) 이라는 함수를 만들어서 계산을 진행했다. 계산은 정말 하드하게 하나하나 일일이 생각해서 안될경우 될경우 모두 코드로 나타내 주었다... 문제에 관한 생각법 자체를 간단하게 해서 코드가 길어지고 더러워 졌지만, 좀만 다듬으면 ..

BOJ 1712번 손익분기점 문제를 풀어보도록 하자 일단 문제 자체는 매우 간단하다 여기서 주의해야할 점은 입력으로 주어지는 고정비용 A, 가변비용 B, 그리고 노트북 가격인 C가 21억 이하의 자연수 라는 점이다 Java의 자료형인 int는 범위가 -2,147,483,648 ~ 2,147,438,647이므로, 해당문제에서 사용해선 안된다. 그렇다면 좀더 큰범위를 가지는 자료형중 long(-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)을 사용 해야한다 그리고 또한가지 주의 해야되는게 손익분기점이 존재하지 않으면 -1 을 출력해야 된다. 즉, (C - B)가 0보다 크면 판매량을, 그렇지 않으면 -1을 출력해야 된다 손익분기점이 존재하지 않으면 어떻게해...