여니의 취준 준비 253

[11657] 타임머신 in python

> 벨만포드 알고리즘 다익 스트라 : 모든 간선의 비용이 양수일 때 최단 경로를 구할 수 있다. 심지어 음수간선이 포함되어 있더라도 해당 간선이 순환되는 구간이 없으면 된다. https://youtu.be/Ppimbaxm8d8 그러나 음수 간선이 순환되는 경우에는 다익스트라는 사용할 수 없고, 벨만 포드 알고리즘을 사용해야한다. 1. 출발 도시 설정 2. 최단 거리 테이블 무한으로 초기화 3. 벨만 포드 알고리즘 시행 3.1. 다음 과정을 n-1번 반복한다. 3.2. 만약 dist[a]의 값이 무한이 아니고, dist[b]의 값이 dist[a]+c값보다 크면? dist[b]에 dist[a]+c, 최단경로를 넣어준다. 3.3 만약 현재 i가 n인데도 갱신이 이뤄졌다면? -> 음수..

[4803] 트리 in python

> dfs dfs 개념을 다시 짚고 넘어가자.. 갑자기 막 헷갈림 ㅠㅠ (1) 재귀함수를 이용한 dfs 구현 방문처리는 함수 맨 첫줄에...! 방문하지 않은 노드가 있다면 재귀함수만 호출시킴. def dfs(node): visited[node]=False # 현재 노드 방문처리 for i in array[node]: # 현재 노드와 연결된 노드들중에 if not visited[i]: # 방문하지 않은 노드가 있다면 dfs(i) # dfs(i) 재귀함수 호출 (2) stack을 이용한 dfs 구현 방문처리는 while문 안에서..! 방문한 노드가 아닐 경우의 조건문 안에서! def dfs_iteration(graph, root): visited = [] stack = [root] while(stack): ..

[15681] 트리와 쿼리

> 깊이 우선 탐색 > 그래프 탐색 아래와 같이 코드를 작성해서 제출했더니 재귀 관련 오류가 났다. n, r, q = map(int, input().split()) tree = [[] for _ in range(n + 1)] for i in range(n - 1): a, b = map(int, input().split()) tree[a].append(b) tree[b].append(a) query = [int(input()) for _ in range(q)] def check(node): count[node] = 1 for child in tree[node]: if not count[child]: check(child) count[node] += count[child] return count[node] ..

[16948] 데스 나이트 In python

> bfs 문제 최소 경로를 출력해야한다길래 max로 매번 경로횟수를 체크해줘야하나 생각했으나 1칸씩 이동할때마다 +1씩 증가시키고 도착점에 도착하면 현재 횟수를 출력한다. 큐에 cnt 횟수까지 넣으면 메모리초과 남.. from collections import deque n = int(input()) r1, c1, r2, c2 = map(int, input().split()) # 1~6번 순으로 dx = [-2, 0, 2, 2, 0, -2] dy = [1, 2, 1, -1, -2, -1] def bfs(): queue = deque() queue.append((r1, c1, 1)) visited = [[False for _ in range(n)] for _ in range(n)] visited[r1][..

[1254] 팰린드롬 만들기 in python

> 문자열 예시는 s= abab 1번째 생각) s = s + s[0] 위 식은 위 예시에만 성공적 2번째 생각) s=qwerty s=s+s[len(s)-1::-1] qwerty + trewq = qwertytrewq 위 예시에서는 성립. 하지만 abab + aba abababa 똑같이 역으로 해도 똑같은 값이 나오긴 하지만 가장 짧은 팰린드롬을 만드는 방법은 아니다. 3번째 생각) s = abdfhdyrbdbsdfghjkllkjhgfds 위 예시에서 2번째 방법을 대입했더니 53이 나옴 나와야하는 답은 38... 그래서 다시 살펴봄 문자열 내 부분 문자열이 팰린드롬일 경우를 생각해줘야한다. 만약 팰린드롬이 문자열 끝부분에 위치해있다면? 2번째 방법을 사용하면 가장 짧은 팰린드롬을 구할 수 없게 된다. s..

[2792] 보석상자 in python

> 이분탐색 평소에는 이분탐색을 풀 때 cnt==n일때, cntn일때 각각 조건을 나눠 계산을 진행해줬다. 그러나 이번 문제처럼 최솟값이나 혹은 최댓값을 구할 땐 위 방식보다는 아래 코드와 같이 작성을 해야한다. if cnt > n: left = mid + 1 else: # cnt [2805] 나무 자르기 in python >> 이분 탐색 >> 정렬 처음에는 left, right의 값은 인덱스 값이 아닌 현재 톱날의 높이에 기준을 맞춰 지정해주어야 한다. sorted를 하고 array[n-1]로 최댓값을 구하는 것보다 max(array)로 하는게 실행속 eboong.tistory.com

[2108] 통계학 in python

> 수학 > 구현 > 정렬 시간 초과가 나서 input() -> readline()으로 바꿈. 1. 산술평균 처음에는 아래와 같이 작성했다. 그러나 바로 직전에 풀었던 문제가 떠올랐다.. 부동 소수점 문제가... 여기서도 어쩔 수 없이 소수가 나오기 마련이다. 그리고 round 함수는 우리가 알고 있는 반올림과는 큰 차이가 있다. 예시를 들어보자. 1.5를 반올림하면 -> 2 2.5를 반올림하면 -> 3 위 같은 결과가 나와야한다. 하지만 round 함수를 쓰면 1.5는 -> 2 2.5도 -> 2 위 같은 결과가 나온다. 띠용(?!) 우리가 알고 있는 방식은 "사사오입 방식"이라고 한다. 즉 0.5, 0.6처럼 절반 이상일 땐 반올림을 진행하고 그 이외엔 버리게 되는 형식이다. 그러나 round 함수는 ..

[2417] 정수 제곱근 In python

> 이분탐색 > 수학 1. 수학적인 공식을 이용하여 푼 방법 * 틀린 코드 * 아래 코드와 같이 했는데, 90% 가까이 성공하다 틀렸습니다 파티가 일어났다.. 왜지? 왜 안되는거지?라는 의문을 가지고 질문 게시판을 뒤적인 결과 부동소수점 오차 문제 때문이란다.. f,e=0,int(input())**.5 if e-int(e)==0: print(e) else: print(int(e)+1) 일단 컴퓨터가 실수를 표현하는 방식에 대해 알아야한다. 컴퓨터는 모든 수를 2진수(0과 1)로 표현한다. 정수는 표현이 간단하지만, 실수는 그리 간단하지 않다. 실수 표현 방식에는 두 가지 방식이 존재한다. 1. 고정 소수점 방식 2. 부동 소수점 방식 (1) 고정 소수점 방식 실수를 정수부와 소수부로 나눈다. 소수부의 자..

[1789] 수들의 합 In python

> 수학 1) 반복문을 이용하는 방법 수들의 합을 구하는 공식은 N * (N+1) / 2 = S 문제에서 주어진 값은 수들의 합 N의 값을 구해야한다. 처음에는 While문을 이용했다. 1부터 시작해서 수들의 합이 S를 넘기 직전까지 돌리고 해당 값을 출력해준다. 실행시간 88ms s = int(input()) answer = 0 i = 1 while i * (i + 1) //2 이렇게 해주면 된다. 물론 Math 라이브러리의 sqrt를 이용해도 구할 순 있음. 세제곱근을 구하려면 8**(1/3) 이런식으로 작성하면 됨.