본문 바로가기

전체 글137

수 정렬하기 3 - 10989번 수를 효율적으로 정렬하는 방법을 강구해야하는 문제이다. 먼저 for문에서 input을 넣어서 사용하면 느리기 때문에 sys모듈의 readline을 이용해주었다. 그냥 sort를 써주면 메모리 초과가 발생하기 때문에 문제에서 주어진 숫자의 범위제한을 이용해준다. 10000이하의 수들만 입력받아 정렬해줘야 하므로, 적절한 크기의 배열을 만들어두고 입력받은 수를 index로 하여 배열에 1을 더해준다. 입력이 끝나면 배열을 검사하여 2중for문을 이용해 배열의 값이 0이 아닐 때만 출력해준다. import sys n = int(sys.stdin.readline()) a = [0]*(10001) for i in range(n): a[int(sys.stdin.readline())] += 1 for i in ran.. 2022. 9. 21.
계단 오르기 - 2579번 점화식을 이용해야하는 다이나믹프로그래밍 문제이다. 그리디처럼 보이는 최대값, 최소값 등을 찾는데 동적 프로그래밍(다이나믹프로그래밍을 이렇게 부르기도 한다)을 사용하기도 한다. 문제에 제시된 규칙을 지키며 최대값을 구해야 한다. 첫번째 계단부터 하나씩 올라가면서 각 계단에서의 최대값을 구해보도록 나눠서 생각했다. 이문제에서 특히 고려해야할 점은 3계단을 연속으로 올라갈 수 없는 규칙이다. 변수('cant_go')를 하나 만들어서 계단을 올라가면 1을 더해주고 연속된 계단을 올라갈때 누적으로 1을 계속 더해준다. 변수의 값이 3이 됬을 때 계단을 3칸 연속으로 오른 경우가 되므로 한칸밑에 있는 계단을 스킵할 지, 2칸 밑에있는 계단을 스킵할지 정해줘야한다. 각 경우의 점수중 큰수를 해당 계단에서의 획득할 수.. 2022. 9. 20.
마진상쇄 - 제작중... margin collapsing 이라고 부르는 마진 상쇄는 두 개 이상의 블록 요소의 상하 마진이 겹치게 될 경우 두 값을 더한만큼 렌더링해주는 것이 아닌 둘 중 하나의 값만 적용하여 렌더링해주는 브라우저의 규칙이다. 마진상쇄가 일어나는 3가지 경우 1. 인접 형제 박스 간에 상하 마진이 겹칠 경우 2. 빈 요소의 상하 마진이 겹치는 경우 3. 부모 작스와 첫번째 자식 박스의 마진이 겹치는 경우 https://velog.io/@raram2/CSS-%EB%A7%88%EC%A7%84-%EC%83%81%EC%87%84Margin-collapsing-%EC%9B%90%EB%A6%AC-%EC%99%84%EB%B2%BD-%EC%9D%B4%ED%95%B4 CSS 마진 상쇄(Margin-collapsing) 원리 완벽.. 2022. 9. 19.
A와 B - 12904번 s와 t를 입력받아서 s를 t로 바꿀 수 있는지 알아보는 문제이지만 반대로 뒤집어서 t를 s로 바꿀 수 있는지를 확인해보면 간단하게 해결할 수 있다. 끝에 A를 추가하는 것은 끝이 A이면 끝에있는 A를 삭제해준다. 뒤집고 B를 추가해주는 것은 끝이 B이면 끝에있는 B를 삭제해주고 뒤집어준다. import sys s = sys.stdin.readline().strip() t = sys.stdin.readline().strip() while True: if t[-1]=='A': t = t[:-1] elif t[-1]=='B': t = t[:-1] t = t[::-1] if len(s) >= len(t): if s==t: print(1) else: print(0) break 2022. 9. 19.
스택 - 10828번 파이썬의 모듈인 데큐를 쓰든 안쓰든 값을 input받을 때, readline을 쓰지 않으면 시간초과가 뜬다. input받는 명령들은 단순하게 조건문을 사용해 처리해주었다. from collections import deque import sys dq = deque() n = int(sys.stdin.readline()) for _ in range(n): com = sys.stdin.readline() a = com[:3] if a == 'pus': dq.append(int(com[5:])) elif a == 'pop': try: print(dq.pop()) except: print(-1) elif a == 'siz': print(len(dq)) elif a == 'emp': if len(dq)>0: pr.. 2022. 9. 18.
숫자 카드 - 10815번 몇일 전에 풀었던 숫자카드 2와 같은 코드를 사용했다 마찬가지로 해시맵을 사용하면 시간초과가 안뜨는데 이분탐색을 사용하니 시간초과가 떴다. # 해시 맵을 사용하여 푼 코드, 이진탐색에 비해 더 간단한 느낌이 든다... n = int(input()) n_arr = list(map(int, input().split())) m = int(input()) m_arr = list(map(int, input().split())) result = [] dict = {} for i in n_arr: if i in dict: dict[i] +=1 else: dict[i] = 1 for i in m_arr: if i in dict: print(dict[i],end=' ') else: # 이진탐색을 이용하여 푼 코드, 시간.. 2022. 9. 17.
숫자 카드 2 - 10816번 이분탐색을 연습하고 싶어서 고른 문제이다. 하지만 이상하게도 이분탐색을 사용하여 풀면 시간초과가 뜬다. 따라서 key로 데이터를 접근하고 관리하는 map 을 사용하여 풀었다. 이진탐색트리는 O(log n)의 속도를 가지고, 해시 맵은 O(1)의 속도를 가진다. # 해시 맵을 사용하여 푼 코드, 이진탐색에 비해 더 간단한 느낌이 든다... n = int(input()) n_arr = list(map(int, input().split())) m = int(input()) m_arr = list(map(int, input().split())) result = [] dict = {} for i in n_arr: if i in dict: dict[i] +=1 else: dict[i] = 1 for i in m_a.. 2022. 9. 16.
수 찾기 - 1920번 단순하게 배열에 있는지 없는지를 따지게 되면 시간초과가 뜨는 문제이다. 탐색 중, 이분탐색을 사용하여 풀면 빠르다. 문제 해결을 위해 이분탐색하는 함수를 만들어주었다. return값은 인덱스를 뽑아낸다. n = int(input()) ns = list(map(int,input().split())) m = int(input()) ms = list(map(int,input().split())) ns.sort() # 이분탐색 함수 def bin_search(target, arr): start = 0 end = len(arr)-1 while start target: end = mid-1 else: start = mid+1 return None for i in ms: idx = bin_search(i,ns) if.. 2022. 9. 15.
A → B - 16953번 그리디 문제로 인식하고 풀었다. 처음 숫자부터 목표숫자까지 커지게 만들지 말고, 목표숫자부터 처음숫자로 작아지게 만들면 쉽게 해결할 수 있다. n,m = map(int,input().split()) res = 1 while m>n: res+=1 if m%2 == 0: m = int(m/2) elif m%10 == 1: m = m//10 else: res=-1 break if m != n: res = -1 print(res) 2022. 9. 14.
AC - 5430번 입력받는 배열을 파싱한 후 deque로 변환하여 다루면 빠른 속도로 해결할 수 있다. deque의 속도는 O(1) 이고, 리스트의 속도는 O(n)이기 때문이다. 하지만 deque의 reverse(deque.reverse())는 속도가 리스트의 reverse와 비슷하게 느리다. 따라서 deque로 구현하되 reverse를 최대한 적게 사용하는 방법으로 코드를 짜야한다. 문제에서 입력받는 수행할 함수 p에서 R이 나올 때 마다 reverse를 하지말고, 상황에 따라서 deque.pop()과 deque.popleft()를 적절하게 사용해주면 된다. 그리고 deque.reverse()는 가장 마지막에 검사하여 적용해주면 된다. from collections import deque import sys n = in.. 2022. 9. 13.
주유소 - 13305 기름값이 가장 적은 도시가 어디인지 먼저 알아내야한다. 그 도시가 처음 출발하는 도시면 간단하고, 아닐 경우, 처음 도시에서 기름값이 가장 싼 도시까지 가는 도중에 그나마 기름값이 싼곳을 거쳐가면 최소비용을 구할 수 있다. 그리고 가장 마지막 도시의 기름값을 알 필요가 없어서 저장하지 않거나 입력받고 삭제하는 것을 추천한다. n = int(input()) distance = list(map(int, input().split())) cost = list(map(int, input().split())) cost.pop() first_cost = cost[0] min_cost = min(cost) min_cost_loc = cost.index(min_cost) pay = 0 p_cost = first_cost.. 2022. 9. 12.
부동소수점 컴퓨터는 0 과 1로만 모든 것들을 구현한다. 그 중 실수의 소수점을 컴퓨터로 표현할 때 무한히 계속되는 부분을 용량문제로 '버림'하여 사용하기 때문이다. 예를들어 5.125를 컴퓨터에 저장한다고 가정하자. 컴퓨터 메모리에 넉넉하게 32칸을 준비한다. (32 bit) 메모리의 첫번째 칸은 양수인지 음수인지를 구분하는 칸이고, 나머지 부분은 8칸의 지수부분과 23칸의 가수수분으로 이루어져있다. 가수부분은 2진법으로 표현한 수의 정수부분을 2진수로 나타낸 결과가 들어가고 지수부분은 2진법으로 표현한 수의 소수부분을 2진수로 나타낸 결과가 들어간다. 5.125는 2진수로 101.001 이다. 이 수를 컴퓨터에 표현하기위해 소수점을 왼쪽 끝까지 이동시켜서 1.01001 * 2^2 로 표현해준다. 부호부분에는 양.. 2022. 9. 11.

티스토리툴바