개발/알고리즘(32)
-
[알고리즘/자바] 백준 5622번 - 다이얼
5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net 전화기의 번호를 누르기 위해선 몇초간 기다리는 시간이 필요하며, 각 번호에는 3~4개 알파벳이 매핑 되어있다. 입력은 번호가 아닌 알파벳으로 주어지며 이 알파벳을 보고 전화를 거는데 걸리는 시간을 구하는 문제다. 첫번째 아이디어. 문제에 각 알파벳을 선택하는데 소요되는 시간은 이미 확정 되어있다. A,B,C는 3초가 소요되며 D,E,F를 선택할때는 4초가 걸린다. 아스키 코드를 통해 문자를 10진수 정수로 변환했고 아래와 같은 방법으로 알파벳을 선택하는데 걸린 시간을 구했다. 이런식으로 풀면 정답일줄 알았는데 한가지 실수가 있었다. (위에 형광펜..
2021.07.14 -
[C++]비트마스크를 이용한 에라토스테네스의 체 구현
이전에 백준 사이트에서 에라토스테네스의 체 문제를 푼적이 있다. 자료구조를 공부해보고 싶어서 종만북 2권을 보는데 첫번째 장에서 비트마스크를 통한 에라토스테네스의 체를 구현한 부분이 있어서 블로깅 해본다. 비트마스크는 bit연산을 통해 문제를 해결하는 방법을 말한다. [알고리즘/자바] 백준 2960번 - 에라토스테네스의 체 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 주어진 N이 소수라면 2보다 크거나 같고 N보다 작은 수로 나눠 떨어지면 안된다. ( 주어 soojong.tistory.com 아래는 종만북을 학습하고 있는 과정에서 작성한 글이기 때문에 오류가 있을수 있으니 수정해야할 부분 있으..
2021.07.11 -
[알고리즘/자바] 백준 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 -
[알고리즘/자바] 백준 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