[백준/1015] 수열 정렬
·
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 정렬 함수의 알고리즘
·
PS/BOJ&Programmers
K번째 수  Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net 알고리즘N(1Ai(-10**9 범위가 위와 같이 주어졌기 때문에, List를 정렬하는 sorted()나 sort()로 하면 당연히 시간 초과 코드일 줄 알았는데 의외로 정답이었다.그래서 이번 기회를 통해 python의 리스트 정렬 연산의 원리와 복잡도에 대해 알아보려한다. sort() This method sorts the list in place, using only comparisons between items. This method modifies the sequence in place for economy of space..
[백준/1032] 명령 프롬프트 | 문자열 비교
·
PS/BOJ&Programmers
명령 프롬프트 알고리즘문자열 비교 알고리즘이다.이런 문제를 풀 때는 모든 보기를 다 비교해야 할지, 일부로도 해결이 가능한지 판단한다.어차피 N의 범위가 적으니까 할 수 있는 건 다 해서 풀어낸다.전체 코드내가 작성한 코드import sys; input=sys.stdin.readlinen=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)): fo..
[백준/1009] 분산 처리 | 반복되는 숫자 어떻게 효율적으로 처리할까
·
PS/BOJ&Programmers
 분산 처리 알고리즘승수의 마지막 자리 반복001122 4 8 633 9 7 144 6556677 9 3 18 8 4 2 699 1 수의 끝자리만 가져오는 두 가지 방법문자열 활용 a = str(a) a = int(a[-1])나머지 활용(%10, %100, %1000, ....)a %= 10 # 끝 한 자리만a %= 100 # 끝에서부터 2개전체 코드import sys; input=sys.stdin.readlinet=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] 개미 | 점화식 그게 뭔데 그거 어떻게 하는 건데
·
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] 음식물 피하기 | 배운 점이 많은 문제
·
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 | 최장공통수열
·
PS/BOJ&Programmers
9251 LCSLCS 문제 해결 기법두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다.문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자.dp table은 memoization 방식으로 이어나간다.알고리즘이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,,table 설명을 위해 i=6, j=4일 때를 예를 들어보자면일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다. 가장 긴 공통 문자열의 길이를 묻는 거..
[백준/2178] 미로 탐색 | BFS와 최단 경로
·
PS/BOJ&Programmers
BFS와 최단 경로BFS는 최단거리와 관련있다. 왤까?BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다.bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다.그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다.흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자.시작점 A에서 F까지의 최단경로를 알아본다고 했을..
[백준/14565] 역원(Inverse) 구하기 | 확장 유클리드 알고리즘 | 덧셈역,곱셈역
·
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] 제곱근 | 이진탐색
·
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] 수들의 합| 부분합과 누적합의 차이를 명확하게 | 투포인터
·
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 활용
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 오늘 문제해결기법 강의 시간에 그리디 알고리즘을 배웠다. 교수님께서 가르쳐주신 내용을 정리해보고자 한다. 그리디 알고리즘을 예전부터 알고있었는데 활용을 잘 하지 못했다! 이번 기회에 확실히 잡아두자. 알고리즘 그리디 알고리즘: Greedy(욕심쟁이) [기본 마인드] 어떤 기준을 정하고 가장 최선의 선택을 먼저 시작한다. ✅ 그리디 문제를 풀 때는 기준을 세우는 게 중요하겠다. 어떤 문제를 푸는데 도저히 생각이 안 날 때 일단 이거부터 써보자. ➡️ 아이디어 생각은 어렵지 않으나 구현이 어려울 수 있다. ⭐️ 내 ..
[백준/1912] 연속합 | 누적합, 부분합
·
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의 활용
·
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..
[백준/15686] 치킨 배달 | 시뮬레이션 | 2차원 공간 좌표 다루기
·
PS/BOJ&Programmers
이번주 주제는 시뮬레이션. 부끄럽지만 시뮬레이션은 처음 공부해본다~^^ 별 것 아님. https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [주요 유형] 1. 2차원 공간(상,하,좌,우) ✅ 방향 벡터를 잘 쓰자. 2. 특정 게임 구현 ✅ 머릿속으로 상상하면서 테스트 케이스를 떠올리자. [Skills] 1. 문제를 잘 읽고 조건을 빼먹지 않게 메모하자 2. 자료구조를 잘 활용하자. 주절..주절...주절.... 사실 이 문제를 포..
sebinChu
'PS/BOJ&Programmers' 카테고리의 글 목록 (2 Page)
상단으로

티스토리툴바