yeony's story

> 이분탐색 평소에는 이분탐색을 풀 때 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

>> 이분 탐색 >> 정렬 처음에는 left, right의 값은 인덱스 값이 아닌 현재 톱날의 높이에 기준을 맞춰 지정해주어야 한다. sorted를 하고 array[n-1]로 최댓값을 구하는 것보다 max(array)로 하는게 실행속도를 더 빠르게 한다! n, m = map(int, input().split()) array = list(map(int, input().split())) left = 0 right = max(array) while left

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

> 이분탐색 > 수학 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) 고정 소수점 방식 실수를 정수부와 소수부로 나눈다. 소수부의 자..

> 수학 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) 이런식으로 작성하면 됨.

> dfs > bfs 실행시간 약 112ms 해당 좌표의 위치가 집인지 그리고 해당 좌표에 방문했었는지 안했는지에 대한 조건이 중요했던 문제 from collections import deque n = int(input()) array = [[] for _ in range(n)] for i in range(n): for j in list(input()): array[i].append(int(j)) # 상,우,하,좌 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] answer = [[0 for _ in range(n)] for _ in range(n)] cnt = 1 def bfs(i, j): queue = deque() queue.append((i, j)) global cnt if a..

> BFS 처음에 떠올렸던 생각은 다이나믹 프로그래밍 근데 지나야하는 최소의 칸 수를 구해야하므로 BFS로 풀었음. 문제에서 주어진 예제 2번의 과정을 풀어보았음. 그림이 좀 지저분하긴 한데.. 일단 노란색 형광펜으로 쳐져있는 길로 가야 최소의 이동칸 수를 구할 수 있다. 오른쪽에 써있는 작대기 + 숫자는 -> 이동순서 여기서 현재 위치란 nx,ny (x,y에서 이동한 값) 1. 만약 길이라면? 1.1 방문한 적이 없는 경우라면? 1.1.1 큐에 현재 위치 append 1.1.2 현재 위치 방문처리 1.1.3 answer 리스트의 현재 위치 부분에 +=1 해주기 1.2 방문한 적이 있는 경우라면? --> *** 이 부분이 중요 *** 1.2.1 answer[nx][ny]의 값과 answer[x][y]+1..

> 자료구조 > 스택 > 재귀 https://www.acmicpc.net/problem/1662 이 문제를 풀 때 스택을 생각해내지 못하고 빡구현으로 하려고 시도했으나 처참하게 실패했다. 문자열 스택!! 문자열 문제에서 스택이 자주 쓰였던 것 같은데 왜 항상 까먹는지 이번 기회에 기억해두길.. 이 문제를 풀 때 길이가 아니라 문자열 자체를 저장해두다보니 메모리초과가 발생했다. words = input() answer = '' temp = '' stack = [] for idx in range(len(words)): if words[idx] != ')': stack.append(words[idx]) else: while True: x = stack.pop() if x != '(': # 숫자 temp+=x ..

> Dp 처음에 떠올렸던 알고리즘은 dfs였다. 그런데 dp로 풀게 되면,, 조건을 처리해주는 부분이 매우 까다로울 것 같아서 힌트를 봣더니 역시나 틀린 방법을 .. ㅎ 이 문제는 다이나믹 프로그래밍 기법을 이용하여 풀어야한다. D분 후 위치해있어야하는 곳은 정보과학관이다. 초기값은 정보과학관 전산관 미래관 신양관 한경직기념관 진리관 형남공학관 학생회관 초기값 (0분) 1 0 0 0 0 0 0 0 1분 후 정보과학관에서 전산관으로 가는 방법은 1가지 정보과학관에서 미래관으로 가는 방법은 1가지 정보과학관 전산관 미래관 신양관 한경직기념관 진리관 형남공학관 학생회관 초기값 (0분) 1 0 0 0 0 0 0 0 1분 후 0 1 1 0 0 0 0 0 2분 후 정보과학관 전산관 미래관 신양관 한경직기념관 진리관..

> 정렬 처음에 이 문제를 보고 묶음이 여러개 있어도 된다는건가?라는 생각과 함께 묶음이 짝수인 경우 묶음 안에 있는 호반우를 품질을 기준으로 정렬했을 때 (묶음개수/2+1)번쨰 호반우를 중앙값으로 정의해야한다는 글을 보고 묶음 개수가 배열에서 내가 정한 묶음의 개수를 의미하는건가..라는 생각과 함께 한참 헤매고 있었다. 그런데 묶음의 개수가 이 의미가 아니었다. 만약 배열이 [2,4,8,9]라고 가정하자. 그러면, 지금 내가 2랑 9를 묶으면 이 묶음의 총 길이는 2이다. 짝수이므로 중앙값은 2/2+1 = 2가 되니까 배열의 2번째 값인 9가 중앙값이 되는 것이다. 만약 내가 [2,4,9]라고 묶었다고 가정하면 총 길이는 3이다. 홀수이므로 중앙값은 3+1/2=2이고 우리는 최대 이익을 만들어야하기 때..