'PS' 카테고리의 글 목록 (2 Page)

[백준/7785] 회사에 있는 사람 | 딕셔너리 | 코드 비교

2023.11.25·

PS/BOJ&Programmers

회사에 있는 사람 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 회사에 출입하는 사람의 기록이 남는다. 이 기록을 통해 회사에 남아있는 사람의 목록을 출력한다. 알고리즘 회사에 남아있는 사람을 체킹해야 하므로 출입 카운트를 해주었다. 입장 + 퇴장은 무조건 짝수이므로 홀수 카운팅이된 사람은 회사에 남아있는 사람이다. 입력 받은 이름을 정답 출력에 사용해야 하고 각각의 사람마다 카운팅 기록을 남겨주어야 하기 때문에 딕셔너리를 활용했다. 전체 코드와 알게된 점 import sys; input = sys.stdin.readline n = int(input()) dic = dict() le..

[백준/1015] 수열 정렬

2023.09.30·

PS/BOJ&Programmers

수열 정렬 Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net 알고리즘입력된 배열 A의 오름차순을 새로운 배열에 저장하는 문제다. 일단 배열 A는 수열 P처럼 0부터 N-1까지의 수를 한 번씩 포함하는게 아니라 예시의 2 1 3 1 처럼 같은 숫자가 2번 이상 반복될 수 있기 때문에 가장 작은 값부터 큰 값까지 하나씩 차례대로 순서를 찾았다. 복잡도를 따졌을 때 이러한 방식으로 문제를 해결하더라도 N 같은 숫자를 어떻게 처리할 것이냐가 관건이었는데, k라는 변수를 하나 만들어서 indexing하도록 지정해주었다. 전체 코드import sys; input = sys.stdin.read..

[백준/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 이제 이동 좌표에 관한 점화식을 얻었으니, 거리를 구하면 된다. 거리는 수학적으로 뺄..

[알고리즘] 다익스트라 알고리즘

2023.06.07·

PS/Algorithm

다익스트라다익스트라는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.bfs, dfs처럼 원리를 통해 특정 경로, 비용 등을 계산하는 알고리즘이다. 최단경로(출발, 도착, 비용)**이때 cost는 양의 가중치, 유향 그래프 특징1. 시작점이 주어진다.2. 시작점을 출발지로 [INF] * (n+1)로 초기화된 node의 가중치 정보를 갱신하며 그래프 탐색을 한다.3. 이때 노드들을 방문하면서 python heapq를 사용하여 노드 번호와 가중치를 체크하면 최단거리를 찾을 수 있다.4. graph는 i번째 노드에서 j번째 가는 가중치(w)를 저장해야 하므로 이차원 리스트로 구현한다. 구현 방법구현은 python heapq를 활용한다. python의 우선순위 큐.원소들..

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

2023.05.12·

PS/BOJ&Programmers

1743 음식물 피하기 알고리즘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 이 문제에서 dfs 함수는 #를 발견하면 주변(d 좌표)을 탐색하면서 같은 영역에 속하는 곳의 크기가 얼마인지 세어주는 함수이다. 따라서 if문 조건은 주변 영역에서 계속 #이 이어지는 경우이므로, 이때 개수를 세어주어야 한다. 처음에 잘 생각이 안나서 cnt += 1 이런식으로 세어주고 return했는데 그러면.. 같은 ..

[백준/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까지의 최단경로를 알아..

[알고리즘] convex hull(컨벡스 헐)

2023.05.02·

PS/Algorithm

계산 기하 2/3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제 실생활에 매우 밀접하게 응용된다. 일단 2차원 공간/정수 좌표/정수 연산으로 가정한다. → 가급적 +,-,*,>,=,

[알고리즘] Segment Tree

2023.04.28·

PS/Algorithm

1. 구간 l,r의 합 구하기(O(N)) 2. i 번째 수를 v로 바꾸기(O(1)) ⇒ 총 시간 복잡도는 O(NM) + O(M) = O(NM) segment tree를 써야 하는 이유 이때 구간합 알고리즘 사용해서 앞에서부터 차례대로 합을 구해놓는 방식으로 풀 수 있음. 여기서 2번 연산을 하려면 수가 바뀔 때 마다 prefix_sum 배열을 변경해줘야 한다. 가장 앞에 있는 0번째 수가 바뀐다면 모든 prefix_sum 배열을 변경해야 하기 때문에 시간 복잡도는 O(N) 따라서, M과 N이 매우 큰 경우에는 결국..! 시간 초과. 세그먼트 트리를 사용하면 O(N) → O(lg N), O(M) → O(lg N) 정의 리프 노드를 제외한 다른 모든 노드는 항상 2개의 자식을 가진다. ⇒ Full Binar..

[알고리즘] 헷갈려서 정리해보는 DP 🙀 | 재귀 - Memoization | for 배열 - Tabulation | Top-down & Bottom-up | 문제 유형

2023.04.17·

PS/Algorithm

피보나치 수와 파도반 수열 동적계획법 알고리즘 마인드를 떠올리기 힘들면 피보나치 수열, 파도반 수열을 떠올려 보자. 재귀함수와 dp의 관계: Memoization Top-down 재귀함수와 dp의 관계는 "비교 대상이자 구현법"이다. 따라서 dp의 특성을 파악하기 위해 먼저 재귀함수에 대한 이해가 필요하다. 재귀함수는 아래와 같은 그림을 기억해두면 이해하기 훨씬 수월하다! 한동안 재귀, 백트레킹 이해를 힘들어 하고 있었는데 재귀 작동 방식과 아래 그림을 연결해서 생각해보니 훨씬 이해가 잘됐다. 재귀 구현 코드는 다음과 같다. n = int(input()) def fibo(n) : if n memoization if m[n] != -1: return m[n] elif n 오 형태로) 바텀업 방식이다. dp..

[백준/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 : 이전 단계에서 구한 대략적인 제곱근 값과 그 역수의 평균값을 구한다. 이후 다시 ..

티스토리툴바