본문 바로가기

전체 글

 (174)
백준 2193 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 2차원 다이나믹 배열 이용(변수 두개 사용) D[ N ][ L ] = D [ 자리수 ] [ 마지막수 ]라 했을 때, 경우의 수를 나누어서 생각해보자. 1) 마지막 자리에 0이 오는 경우 => D[ N ][ 0 ] = D[ N - 1 ][ 0 ] + D[ N - 1 ][ 1 ] 2) 마지막 자리에 1이 오는 경우 => D[ N ][ 1 ] = D[ N - 1 ][ 0 ] 두가지 경우의 수..
백준 10844 쉬운 계단 수 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다. ex) 1234567, 1212345, 345676567 ... 길이가 N인 계단수의 개수를 출력해야하는 문제로, N = 1 : 1, 2, 3, 4, 5, 6, 7, 8, 9 .. N = 2 : 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67 .. 계단 수를 보면 다음과 같은 점화식을 도출 할 수 있다. D[ N ][ L ] = D[ N - 1 ][ L - 1 ] + D[ N - 1 ][ L + 1 ] => D[ ..
백준 15661 링크와 스타트 문제 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 해당 문제는 브루트 포스 유형의 문제이다. n명을 두팀으로 나눌 수 있는 총 가능한 방법을 생각해보면(이때 팀의 인원수는 같지 않아도 된다.) 1번 사람이 1번팀에 들어가는 경우, 2번팀에 들어가는 경우 2번 사람이 1번팀에 들어가는 경우, 2번팀에 들어가는 경우 . . . n번 사람이 1번팀에 들어가는 경우, 2번팀에 들어가는 경우 총 경우의 수..
백준 14891 톱니바퀴 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 톱니바퀴가 동시에 돌아가는걸 코드로 구현만 하면 되는 문제였으나 "동시에 돌아가는 톱니바퀴의 상태"를 코드로 구현하는게 쉽지않았습니다. 톱니가 a b c d e 이 있고 c번 톱니를 회전 시계방향으로 회전 한다고 하면 1) 톱니 회전 방향을 왼쪽->오른쪽 / 오른쪽 -> 왼쪽 진행 방향으로 나뉘어서 상태를 판단한다. (1) 왼쪽 -> 오른쪽으로 진행 : c번 톱니바퀴의 2번 톱니 극성값 ..
./gradlew build 실패 오류 1. ./gradlew build를 하려고 하는데 실패가 났다. 원인은 자바 버전이 안맞았던것. 그래서 sudo vi ~/.zshrc export JAVA_HOME=$(/usr/libexec/java_home -v 1.8) source ~/.zshrc 로 자바 버전을 변경하고 다시 ./gradlew clean build를 하였는데 아래와 같은 오류가 남. 아래 사이트를 참고하여 export JAVA_HOME=$(/usr/libexec/java_home -v 1.8.0_291) 로 변경하여 해결함. https://stackoverflow.com/questions/64968851/could-not-find-tools-jar-please-check-that-library-internet-plug-ins-jav..
백준 14499 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 해당 문제는 시뮬레이션 유형으로 주사위를 동 / 서 / 남 / 북 으로 굴릴 때 어떻게 표현해야할지가 핵심이었던 문제이다. 초기 주사위값을 이용하여 동 / 서 / 남 / 북으로 주사위를 굴릴 때 변화하는 값을 아래 그림에 표현하였다. 이를 dice 배열에 담아주었고, 각 direction 에 맞게 주사위의 값을 갱신해주었다. 코드 ..
백준 12015 가장 긴 증가하는 부분 수열 2 C++ 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해당 문제는 Longest Increasing Subsequence(LIS), 최장증가부분수열 문제로 수열의 크기가 1,000,000개로 주어지기 때문에 O(n^2)의 시간복잡도의 알고리즘은 시간초과가 난다. 이분탐색을 활용하여 풀어야하는 문제이다. 다음과 같은 풀이를 이용하였다. else 구문을 보면 입력받은 num 값을 다시 갱신해주고있다. 이 부분이 이문제의 핵심이 아닐까 생각한다. 왜..
분할 정복이란(Divide & Conquer) 분할 정복이란? 분할 정복은 문제를 2개 또는 그 이상의 작은 부분 문제로 나눈 다음 푸는 것(분할)으로 푼 다음에는 다시 합쳐서(정복) 정답을 구하는 알고리즘이다. 말 그대로 분할하고 정복하여 정답을 도출하는 알고리즘이다. 분할 정복 대표 알고리즘 퀵 소트 : 평균적으로 O(nlogn), 최악의 경우 O(n^2)의 시간복잡도를 가지는 알고리즘으로 평균적인 상황에서 최고의 성능을 자랑한다. 피벗을 하나 고른다음 그것보다 작은 것을 앞으로, 큰 것을 뒤로 보낸다. 그 다음 피벗의 앞과 뒤에서 퀵 정렬을 수행한다. https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 머지 소트 : O(nlogn)의 시간복잡도를 가지는 알고리즘으로 N개를 N/2, N/2 개..

티스토리툴바