본문 바로가기
반응형

전체 글1305

오일러 피(파이) 함수(Euler's phi function) 오일러 피(파이) 함수 ϕ(n) 1~n까지의 수 중에서 n과 서로소인 수의 갯수 ※ 서로소 관계: 두 수 a, b의 공약수가 1뿐인 두 정수를 의미한다. ϕ(1) = 1 (1은 1과 서로소) ϕ(8) = { 1, 3, 5, 7 } = 4개 ϕ(13) = = 12개 ϕ(13) = = 12개 ϕ(15) = = 8개 성질 ① pk에서 p가 소수이며, k가 1 이상의 자연수 일 때, ϕ(p) = p−1. 역으로, ϕ(n) = n−1 이면, n은 소수이다. ex) ϕ(7) = = 7 - 1 = 6개 ② a가 p의 배수이다 = pk와 a가 서로소가 아니다. pk이하의 p의 배수가 아닌 수는 pk-pk-1개 존재, 이것은 ϕ(pk ). → ϕ(pk ) = (p-1) × pk-1 = pk - pk-1 ex) ϕ(9) .. 2021. 2. 22.
[BOJ] 백준 17406 배열 돌리기 4 출처: https://www.acmicpc.net/problem/17406 Input 5 6 2 1 2 3 2 5 6 3 8 7 2 1 3 8 2 3 1 4 5 3 4 5 1 1 1 9 3 2 1 4 3 3 4 2 4 2 1 Output 12 회전 연산] 6 x 6 배열과 (r, c, s) = (3, 4, 2) 일 때, 좌측 상단: (r-s, c-s) / 우측 하단: (r+s, c+s) 『배열 A의 값』은 각 행에 있는 모든 수의 합 중 최솟값을 의미. 주어진 회전을 순서로 임의로 배정했을 때, 『배열 A의 값』 중 최소값을 구하는 문제입니다. 구현 순서 ① 모든 회전 가능한 회전 경우의 수 구현 ← 순열 ② 회전 순서가 정해지면 배열 내부에서 특정 영역(정사각형)에 대한 회전(재배치) 회전(재배치)을 .. 2021. 2. 22.
[BOJ] 백준 1786 찾기 출처: https://www.acmicpc.net/problem/1786 Approach [문자열] KMP 알고리즘을 이용하여 해결할 수 있다. [문자열] KMP 알고리즘 KMP 알고리즘이란? 『KMP 알고리즘』 문자열을 검색할 때, 불필요한 반복을 줄이기 위해 검색 문자열의 접두사와 접미사의 중복 길이를 이용한 알고리즘 입니다. (※ Knuth–Morris–Pratt algorithm, KMP) zoosso.tistory.com import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWrit.. 2021. 2. 22.
[문자열] KMP 알고리즘 KMP 알고리즘이란? 『KMP 알고리즘』 문자열을 검색할 때, 불필요한 반복을 줄이기 위해 검색 문자열의 접두사와 접미사의 중복 길이를 이용한 알고리즘 입니다. (※ Knuth–Morris–Pratt algorithm, KMP) [Case] 문자열을 검색할 때 비효율적인 알고리즘 A = aab, B = aaaaaaaaaa 비교 문자열 (A)를 대상 (B)와 일일이 비교하는 경우입니다. 결과적으로 위의 경우에는 문자열 A, B는 같은 구간이 없지만, (A) 문자열 『aab』 에서 『b』를 제외하고는 B문자열과 일치하기에 (A) 문자열 전체로 불필요한 비교를 하게 됩니다. 문자열 A의 길이가 N / 문자열 B의 길이가 M일 때, 결과적으로 O(NM)의 시간을 가집니다. ※ 관련 문제: [BOJ] 1120 문.. 2021. 2. 22.
[BOJ] 백준 1120 문자열 출처: https://www.acmicpc.net/problem/1120 Approach 문자열을 일일이 비교해서 차이를 최대로 하는 구간을 찾는 문제입니다. 주어지는 문자열 A 2021. 2. 22.
[BOJ] 백준 14620 꽃길 출처: https://www.acmicpc.net/problem/14620 Input 6 1 0 2 3 3 4 1 1 1 1 1 1 0 0 1 1 1 1 3 9 9 0 1 99 9 11 3 1 0 3 12 3 0 0 0 1 Output 12 위와 같이 각 1평당 가격이 주어졌을 때, 꽃 3개를 심기위한 최소 비용을 구합니다. ⅰ. 만개된 꽃잎이 화단을 벗어나면 죽기 때문에 꽃을 가장자리에 심을 수는 없다. 결국, □범위에서 3곳을 지정해야 한다. ⅱ. 만개된 꽃잎이 겹치지 않으려면 어떻게 해야 할까? ▶ 『 』 영역에 꽃이 만개 되었으므로, 『 X 』에는 다른 씨앗을 놓으면 꽃잎이 겹친다. 구현 순서 ① 제일 바깥 테두리를 제외한 영역 탐색 ② 심어진 씨앗의 좌표가 (A.x, A.y) 다른 씨앗 좌표가 .. 2021. 2. 22.
[BOJ] 백준 7569 토마토 출처: https://www.acmicpc.net/problem/7569 Input 5 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Output 4 2차원으로 해결하는 [BOJ] 백준 7576 토마토에서 달라진 점은 상자가 여러개 쌓여 있으므로 3차원으로 이를 처리해야 한다. [BOJ] 백준 7576 토마토 출처: https://www.acmicpc.net/problem/7576 Input 6 4 1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 1 Output 6 - 익은 토마토(1)는 인접한 익지않은 토마토에 영향을 줘서 익게 한다. (영향을 주는.. zoosso.tistory.com impo.. 2021. 2. 22.
[BOJ] 백준 7576 토마토 출처: https://www.acmicpc.net/problem/7576 Input 6 4 1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 1 Output 6 - 익은 토마토(1)는 인접한 익지않은 토마토에 영향을 줘서 익게 한다. (영향을 주는 것에는 하루가 걸리며, 상하좌우로 영향을 준다.) - 토마토가 놓여있지 않은 곳(-1)이 존재한다. 모든 토마토가 익기까지 최소 일수를 출력하시오. (토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.) BFS 처리할 때, 출발점을 초기에 주어진 익은 토마토(1)를 모두 Queue에 담아둔다. (마치 동시다발적으로 탐색하는 것처럼...) 방문 표시로 이미 익은 토마토에는 재방문 하지 않는다. import java.. 2021. 2. 22.
[BOJ] 백준 8979 올림픽 출처: https://www.acmicpc.net/problem/8979 Input 4 3 1 1 2 0 2 0 1 0 3 0 1 0 4 0 0 1 Output 2 국가별로 금, 은, 동 개수로 올림픽 순위를 구해보려고 합니다. 1. 금메달 수가 더 많은 국가 2. 금메달 수가 같으면 은메달 수가 더 많은 국가 3. 금, 은메달 수가 모두 같으면 동메달 수가 더 많은 국가 (개수가 동일하면 두 나라의 등수는 같습니다.) * K 국가가 K 번째로 입력되는 것은 아닙니다. Input 4 2 1 3 0 0 3 0 0 2 4 0 2 0 2 0 2 0 Output 2 ① 금, 은, 동 우선순위별로 우선순위 큐에 넣는다. ② 큐에서 poll() 하면서 등수를 매긴다. (* 공동 순위 주의) import java.u.. 2021. 2. 22.
[BOJ] 백준 3425 고스택 출처: https://www.acmicpc.net/problem/3425 Input DUP MUL NUM 2 ADD END 3 1 10 50 NUM 1 NUM 1 ADD END 2 42 43 NUM 600000000 ADD END 3 0 600000000 1 QUIT Output 3 102 2502 ERROR ERROR 600000000 ERROR 600000001 알려져 있는 스택을 변형한 문제로 입력 횟수, 데이터 범위, 예외 처리 등 코드 최적화가 필요한 문제입니다. Sample Case 분석 DUP: 스택의 첫번째 숫자를 복사해서 저장 → MUL: 스택의 첫번째 숫자와 두번째 숫자를 곱해서 저장 → NUM 2: 숫자 2를 스택에 저장 → ADD: 첫번째 숫자와 두번째 숫자를 더합니다. if) 처음.. 2021. 2. 22.
반응형