본문 바로가기

이론/문제풀이

[백준 알고리즘 -2011] 암호코드 - java (신나는 삽질일기) 문제만 보면 여느 DP 문제인데 정답률이 왜이렇게 낮나 했다.제가 그 낮은 정답률에 또 일조하고 왔슴다 (_ _) 문제상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. ​ 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아? 선영: 예가 적절하.. 이론/문제풀이 2018. 9. 26.
[백준 알고리즘 -11722] 가장 긴 감소하는 부분 수열 - java (Collections.reverse(), Java 8 Stream API) int[] 뒤집기 (Collections) feat. 백준 11722문제풀다보면 Arrays나 Collections의 도움을 참 많이 받게 되는데,간단한 sort는 따로 정리할 것도 없지만, 요론건 또 정리해줘야 기억날듯하다.int형 배열을 뒤집으려면 간단하게는 새로운 배열을 생성해서 하나하나 for문 돌릴 수 있겠지만,사람이 또 뭔가 그런 방법말고 다른 방법 없나 찾고싶고 그런 마음이 있다ㅎㅎㅎㅎㅎ JAVA 8에서 Stream API로 Object[]로 바꿔서 반환해주는게 있긴 하던데, Object[]를 또 int[]로 바꾸기 한참 걸려서 패스 하고,Collections를 사용하기로 했다. 물론 List를 int[]로 바꾸는데 활용하긴 했음 사실 Arrays에서 reverse메소드를 제공해주면 참 쉬워.. 이론/문제풀이 2018. 9. 24.
[백준 알고리즘 - 1946] 신입사원 - java 문제 조건: 채용되기 위해서는 서류 심사 성적과 면접 심사 성적 둘 중 하나는 다른 어떤 사원보다 높아야 한다. = 서류 심사 성적과 면접 심사 성적이 둘 다 낮은 신입 사원이 한 명이라도 존재하면 신입사원으로 채용될 수 없다문제 해결 과정: 1) 하나하나 모두 비교하면 O(N^2) -> 10000000000 이기 때문에 제한 시간을 넘어간다. 2) 한 명의 지원자를 대상으로 채용여부를 검사할 때, 그 사원의 서류 점수보다 높은 지원자들과의 면접 점수만 비교하면 된다.Key 1) 서류 심사 등수 순으로 정렬한다(반대의 경우도 가능) 2) 면접 등수는 서류 심사 등수가 현재 검사하는 지원자보다 높은 지원자들 중 가장 높은 등수랑만 비교하면 된다. 즉, 반복문을 돌면서 max값을 업데이트 하면 O(1) 로 .. 이론/문제풀이 2018. 9. 18.
[백준 알고리즘 1464] 1로 만들기 - java(Dynamic Programming) 다이나믹 프로그래밍을 푸는 첫 번째 과정은 DP[n] (또는 k차원의 배열]이 무엇인지를 정의하는 것이다. 일반적인 문제는 그대로 정의하면 된다. 이 문제에서는, dp[n] = n을 1로 만드는 최소한의 연산의 수 라고 생각할 수 있다. 또, dp[n]은 dp[n-1]+1, dp[n/2] +1, dp[n/3] +1 중 하나이고, 이전 단계 즉, N-1 또는 N/2 또는 N/3 을 1로 만드는 최소한의 연산의 수 라는 조건을 만족한다면, N을 1로만드는 최소한의 연산의 수라는 조건도 만족한다. 간단한 문제이기 때문에 바로 코드, Top-Down 방식으로 재귀 호출로 구현한 코드이다. d배열에 메모를 하는 방식이다. 문제는 충분히 시간 안에 해결할 수 있지만 재귀 호출의 오버헤드 문제 때문인지 Bottom-.. 이론/문제풀이 2018. 9. 12.
[백준 알고리즘 - 2632] 피자판매 - java/완전탐색(재귀호출) 진짜 전혀 어려울 것 없는 문제였는데, 조건문 계속 삽질하고 예외케이스 하나 계속 못찾아서 4시간 걸렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 발전좀하자!! 제발! A, B에 대한 부분집합을 각각 구해준 뒤 하나씩 합해서 경우의 수를 세면 되는 문제인데, 첫 번째 신경써야 할 부분은 1. "연속된" 원소만 더해야 할 것 -> 따라서 최대 1000000개이기 때문에 완전탐색이 가능하다 -> 난 여기에 추가로 S가 넘지 않으면 아예 탐색을 종료하도록 구현하였다. 아주 조금이라도 시간을 줄이겠다는 욕망 ,,? 2. 둘 중 하나는 아예 담지 않아도 되게 할 것 -> 0을 추가해준 뒤 오름차순 정렬해주면 쉽게 처리 가능하다. 3. 배열에 담았을 시 맨 뒤를 담으면 끝나는 것이 아닌 맨.. 이론/문제풀이 2018. 9. 9.
[백준 알고리즘 - 1208] 부분집합의 합 2 - java/재귀호출 크기가 n인 집합이 주어졌을 때, 그 부분집합의 갯수는 2^n이다. 이 문제에서 최대 N은 40이기 때문에 2^40=1.0995116e+12 어느정도인지는 모르겠고, 1초 안에 해결할 수 없는 크기인건 알겠다. 따라서 이 문제는 분할하여 풀어야한다. 2^20은 약 1000000으로 1초안에 계산할 수 있기 때문에 주어진 집합을 반으로 쪼개어서 각각 구한 후 풀이한다. 풀이과정은 다음과 같다. [ A, B, C, D, E, F ] 집합이 주어졌을 때, [ A, B C ] [ D, E, F ] 로 쪼갠다. 분할된 두 집합의 부분집합을 구한 후(공집합 포함) 두 분할을 활용하면 문제를 풀이할 수 있다. 여기서 공집합을 포함하는 이유는 앞의 부분집합의 공집합을 선택할지라도 뒤에서 공집합이 아닌 집합을 선택하면 .. 이론/문제풀이 2018. 9. 6.
[백준 알고리즘 - 1261] 알고스팟 (java, BFS) 가중치가 있는 그래프 문제라고 할 수 있다. 일반적으로 가중치가 있는 그래프 문제는 BFS로 풀 수 없지만0과 1로만 구성되어있는 경우에는 예외적으로 BFS로 해결이 가능하다. 0인 곳으로 이동할 때는 dist를 증가시켜주지 않고, 1인곳으로 이동할 때는 dist를 증가시켜 주는데두 vertex를 구분짓기 위해 DEQ를 사용하였다 무조건 나중에 삽입한 vertex를 사용한다고 정한다면 0인 곳은 Last에 삽입하고 1인 곳은 First에 삽입함으로써 0인 곳을 먼저 방문하도록 설정할 수 있다 0인 곳을 모두 방문하였다면 별도의 설정 없이도 다음 1인 곳을 탐색하게 된다 상태 저장 변수는 check와 dist를 활용하였다. import java.io.BufferedReader; import java.io... 이론/문제풀이 2018. 9. 4.
[백준 알고리즘 -1182] 부분집합의 합 - java(재귀호출/부제:오랜만에 삽질일기) 아 너무 삽질했다 ㅠ__ㅠ 부분 집합을 하나하나 구하는 것이기 때문에 현재까지의 합이 S와 일치하더라도 해당 호출을 종료하는 것이 아니라count 계속 탐색해야한다. 여기에 너무 꽂힌 나머지 종료 조건을 잘못 생각하고 삽질 했다. 현재 검색하는 index를 선택할지 선택하지 않을지를 구분하여 재귀호출을 하고함수의 맨 윗부분에 if(cur == S) 조건을 달아주었는데, 생각해보니 이렇게 하고 나서 if( idx >= arr.length) 조건을 통해 종료한 뒤 다시 저 조건으로 들어가 중복되어 세지는 문제가 발생하였다.사실 굳이 호출하면서 바로바로 cur과 S를 비교해주지 않아도 결국 arr 끝까지 오면 그 모든 경우를 들어가는 것인데 말이다 ㅠ__ㅠ arr의 모든 idx를 고려했을 때(선택할지/선택하지.. 이론/문제풀이 2018. 9. 1.

티스토리툴바