'PS/BOJ&Programmers' 카테고리의 글 목록 (2 Page)

[백준/1015] 수열 정렬

2023.09.30·

PS/BOJ&Programmers

수열 정렬 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 입력된 배열 A의 오름차순을 새로운 배열에 저장하는 문제다. 처음에 문제 이해 자체가 좀 어려웠는데, 예시를 통해서 비교적 쉽게 이해할 수 있었다. 일단 배열 A는 수열 P처럼 0부터 N-1까지의 수를 한 번씩 포함하는게 아니라 예시의 2 1 3 1 처럼 같은 숫자가 2번 이상 반복될 수 있기 때문에 가장 작은 값부터 큰 값까지 하나씩 차례대로 순서를 찾았다. 복잡도를 따졌을 때 이러한 방식으로 문제를 해결하더라도 N

[백준/11004] K번째 수 | Python 정렬 함수의 알고리즘

2023.08.02·

PS/BOJ&Programmers

K번째 수 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 N(1

[백준/1032] 명령 프롬프트 | 문자열 비교

2023.07.04·

PS/BOJ&Programmers

명령 프롬프트 알고리즘 문자열 비교 알고리즘이다. 이런 문제를 풀 때는 모든 보기를 다 비교해야 할지, 일부로도 해결이 가능한지 판단한다. 어차피 N의 범위가 적으니까 할 수 있는 건 다 해서 풀어낸다. 전체 코드 내가 작성한 코드 import sys; input=sys.stdin.readline n=int(input()) file=[input() for _ in range(n)] tmp=[] for i in range(n): for j in range(i+1, n): if file[i] != file[j]: a = file[i] b = file[j] for k in range(len(a)): for l in range(len(b)): if a[k] != b[k] : tmp.append(k) break ..

[백준/1009] 분산 처리 | 반복되는 숫자 어떻게 효율적으로 처리할까

2023.07.03·

PS/BOJ&Programmers

분산 처리 알고리즘 승수의 마지막 자리 반복 0 0 1 1 2 2 4 8 6 3 3 9 7 1 4 4 6 5 5 6 6 7 7 9 3 1 8 8 4 2 6 9 9 1 수의 끝자리만 가져오는 두 가지 방법 문자열 활용 a = str(a) a = int(a[-1]) 나머지 활용(%10, %100, %1000, ....) a %= 10 # 끝 한 자리만 a %= 100 # 끝에서부터 2개 전체 코드 import sys; input=sys.stdin.readline t=int(input()) for _ in range(t): a,b = map(int,input().split()) a = str(a) a = int(a[-1]) if a == 1 or a == 5 or a == 6: print(a) # 4 번씩..

[백준/10158] 개미 | 점화식 그게 뭔데 그거 어떻게 하는 건데

2023.06.29·

PS/BOJ&Programmers

10158 개미 알고리즘 t의 범위가 1 ≤ t ≤ 200,000,000이므로 완전탐색을하면 타임아웃이다. 그렇다면 어떤 점화식을 세워서 문제를 풀어야 한다는 건데 1. x와 y의 독립성 이 문제는 1초의 시간이 지날 때 x = (x+1) or (x-1)이 되고 y = (y+1) or (y-1)이 된다. 따라서 각각의 값이 독립적으로 움직인다는 결론에 도달할 수 있다. 2. 이동 횟수와 이동 거리의 관계 x좌표와 y좌표는 각각 t만큼 이동을 하게 되고, 이 이동 주기가 2*w, 2*h이다. 아래와 같은 그래프를 보면 이해가 쉽다. 따라서 이동 자체에 대한 점화식은 다음과 같다. (p+t) % 2*w (q+t) % 2*h 이제 이동 좌표에 관한 점화식을 얻었으니, 거리를 구하면 된다. 거리는 수학적으로 뺄..

[백준/9252] 음식물 피하기 | 배운 점이 많은 문제

2023.05.12·

PS/BOJ&Programmers

1743 음식물 피하기 알고리즘 그냥 dfs로 푸는데 cnt 처리방식 구현이 쉽게 떠오르지 않아서 고민을 좀 했다. 바로 이 부분 def dfs(x,y) : cnt = 1 visited[x][y] = True for dx, dy in d : nx, ny = x+dx, y+dy # 여기가 연결되는 부분이니까 cnt += 1 처리를 해주고, if 0

[백준/9251] LCS | 최장공통수열

2023.05.12·

PS/BOJ&Programmers

9251 LCS LCS 문제 해결 기법 두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다. 문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자. dp table은 memoization 방식으로 이어나간다. 알고리즘 이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,, table 설명을 위해 i=6, j=4일 때를 예를 들어보자면 일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다. 가장 긴 공통 문자열의 ..

[백준/2178] 미로 탐색 | BFS와 최단 경로

2023.05.12·

PS/BOJ&Programmers

BFS와 최단 경로 BFS는 최단거리와 관련있다. 왤까? BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다. bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다. 그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다. 흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자. 시작점 A에서 F까지의 최단경로를 알아..

[백준/14565] 역원(Inverse) 구하기 | 확장 유클리드 알고리즘 | 덧셈역,곱셈역

2023.04.14·

PS/BOJ&Programmers

확장 유클리드 알고리즘 유클리드 알고리즘에서는 나누는 값, 나머지로 r = 0일 때까지의 b값을 통해 최대공약수를 구했다. 확장 유클리드 알고리즘은 이를 활용하여 ax + by = gcd(a,b)가 존재하는 선형 방정식을 푸는 문제다. 지금까지 이런 식으로 유클리드 알고리즘을 통해 최대공약수를 구했다면 다음과 같이 x, y 값을 통해 gcd 값과 선형방정식의 정수해를 구할 수 있다. 이 문제에서 구하고자하는 곱셈역은 결국 (a*c) % n = 1을 찾는 문제인데, 물론 주어진 a와 n을 활용하여 1부터 n까지의 연산을 통해서 구할 수도 있다. 하지만 n의 범위는 10**12로 더 효율적인 방법인 확장 유클리드 알고리즘으로 해를 구하는 방법이 분명히 존재한다. 이 문제에서는 xgcd(11*x, 26)=1이..

[백준/13706] 제곱근 | 이진탐색

2023.04.13·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/13706 13706번: 제곱근 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. www.acmicpc.net Heron's method(헤론 방법) 제곱근을 근사하는 방법이다. 이 방법은 대략적인 제곱근 값을 계산하고, 이를 시작점으로 반복적인 계산을 통해 값을 얻어낸다. 주어진 숫자 x의 제곱근을 구하는 방법 x의 대략적인 제곱근 값을 구한다.(x/2) x를 x/2로 나눈다. x/2 + x(x/2): 이전 단계에서 구한 대략적인 제곱근 값과 그 역수의 합을 구한다. (x/2 + x(x/2)) / 2 : 이전 단계에서 구한 대략적인 제곱근 값과 그 역수의 평균값을 구한다. 이후 다시 ..

[백준/2003] 수들의 합| 부분합과 누적합의 차이를 명확하게 | 투포인터

2023.04.04·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 알고리즘 누적합: psum[i] = psum[i-1] + li[i]로 피보나치처럼 누적해서 더함. 끝으로 갈수록 앞의 값들이 누적되어 값이 커짐 부분합: psum은 앞에서부터 차차 누적해서 더한다면 부분합은 i와 j까지의 합이다. psum[j]-psum[i-1]을 통해 구할 수도 있지만 이렇게 되면 이중 포문을 사용해야 하기 때문에 복잡도가 커진다. 따라서..

[백준/1913] 회의실 배정 | 그리디 | 우선순위 lambda 활용

2023.04.04·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 오늘 문제해결기법 강의 시간에 그리디 알고리즘을 배웠다. 교수님께서 가르쳐주신 내용을 정리해보고자 한다. 그리디 알고리즘을 예전부터 알고있었는데 활용을 잘 하지 못했다! 이번 기회에 확실히 잡아두자. 알고리즘 그리디 알고리즘: Greedy(욕심쟁이) [기본 마인드] 어떤 기준을 정하고 가장 최선의 선택을 먼저 시작한다. ✅ 그리디 문제를 풀 때는 기준을 세우는 게 중요하겠다. 어떤 문제를 푸는데 도저히 생각이 안 날 때 일단 이거부터 써보자. ➡️ 아이디어 생각은 어렵지 않으나 구현이 어려울 수 있다. ⭐️ 내 ..

[백준/1912] 연속합 | 누적합, 부분합

2023.03.29·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 구간합 알고리즘 크기가 N인 배열에 부분합을 구하는 연산을 M번 수행해야 한다고 하자. li[l] + li[l+1] + li[l+2] + ・・・ + li[r]는 다음과 같은 코드를 통해 구할 수 있다. ans = 0 for i in range(l,r): ans += li[i] l, r의 범위가 최악의 경우 0 ~ N-1이므로, 연산의 시간 복잡도는 O(N)이다. 이 연산을 M번 수행해야 하므로 최종적인 시간..

[백준/1912] 연속합 | 누적합 | max의 활용

2023.03.27·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [알고리즘] 처음에 이 문제를 보고 이중 for문의 인덱스를 i를 기준으로 띄워가면서 누적합을 통해 결과를 도출하려고 했다. n=int(input()) li = list(map(int, input().split())) total = 0 ans=[] for i in range(n): total = 0 for j in range(i,n): total+=li[j] ans.append(total) print(max..

[백준/1312] 소수 | 런타임에러? | 부동소수점과 컴퓨터 연산에 대한 이해

2023.03.26·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 투 포인터 헷갈려서 쉬운 문제 찾다가 된통 당한! 문제.. 단순하게 str로 바꿔서 풀면 런타임 에러가 난다. 백준 문제에서 오타 등의 문제가 아닌 알고리즘으로인해 런타임 에러가 난 경우는 처음이다. 그만큼 배울 점이 많아서 기록해본다. 이 문제는 컴퓨터의 부동소수점 연산에 대한 이해가 기반되어야 한다. 사실 문제에서 대놓고 힌트를 제공하고 있다. 첫 번째 줄에 A와 B(1 ≤ A, B ≤ 1..

티스토리툴바