본문 바로가기

전체 글140

까먹는 코테 문법2 1. 컴퓨터는 2진수 체계이기 때문에 실수 덧셈을 정확히 하지 못한다. 보통 5째 자리에서 반올림 하면된다. a = 0.3 + 0.6 print(rount(a,4)) 2. 거듭 연산자 a ** b # a의 b승 3. 자료형 변환 char ch = 'a'+1; # 자바 ch = chr(ord('a')+1) # 파이썬 4. 입력 # N개의 정수를 한 줄로 입력 받아 List에 저장할 경우 data = list(map(int, input().split())) # N개의 정수를 여러 줄에 걸쳐 입력 받아 List에 저장할 경우 N = int(input()) data = [int(input()) for _ in range(N)] # N개의 문자열을 여러 줄에 걸쳐 입력 받아 List에 저장할 경우 리스트 변환 s.. 2023. 2. 16.
Coroutine 완벽 정리 면접 공부를 하면서 Coroutine을 정말 어설프게 써왔던 내 자신을 반성하며 다시한번 잘 정리해보도록 해보자. Coroutine이란 쓰레드가 아니고 쓰레드와 비교하면 메모리를 덜쓰고오버핸드가 적은 비동기 프로그램을 실행 할 수 있는 모듈 코루틴은 AsyncTask라는 비동기 프로그래밍이 메모리 누수등 어려 문제가 생겨 API 30부터 deprecated 되었다. 이후, 구글에서는 코루틴을 원장하게 되었다. 먼저 코루틴을 알아 보기전에 루틴이란 개념에 대해 알아보도록 하자. 프로그램은 메인루틴, 서브 루틴 흐름의 루틴이 존재한다. 메인루틴은 프로그램에서 메인함수 main() 에 진입했을때 위에서 부터 아래로 순차적으로 실행되는 전체적인 흐름이고 서브 루틴은 메인 루틴이 실행되다 개별 함수를 만나면 잠시.. 2023. 2. 14.
[백준] 개미 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 아......나는 뭔가 이런거는 잘 못푸는거 같다.... 그래도 tmp 대신 아래 풀이와 같이 푸는방법을 알게 되어서 다행이다. import sys input = sys.stdin.readline n1,n2 = map(int,input().split()) A = list(input().rstrip()) B = list(input().rstrip()) time = int(input()) A = A[::-1] sumAnt = A + B for _ in range(time): # 반복문을 통해 두 개미 그룹을 확인 for i in.. 2023. 2. 13.
k진수에서 소수 개수 구하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 내가 왜 틀렸는지 솔직히 모르겠다.... (알려줄 사람....) 내가 푼 풀이는 에라토스테네스 체를 이용한 풀이이여서 이것이 더 빠른걸로 알고 있지만... 흐음,,,,내생객에는 소수범위를 어디까지 구해야 하는지 몰라서 그러는거 같다. 내가 푼 풀이 def sol1(number): for i in range(2,len(number)): if number[i] != 0: for j in range(2*i,len(number),i): number[j] = 0 def solution(n, k): str1 .. 2023. 2. 8.
[프로그래머스] 캐시 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 한줄 정리 : 조건부 스택 이문제를 풀기 위해서는 먼저 LRU알고리즘을 알아야 한다. LRU알고리즘이란 페이지 교체 알고리즘이라고 하는데 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다. 이 알고리즘이 사용되는 시기는 페이지 부재가 발생해 새로운 페이지를 적재 해야하나 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용된다. 페이지 교체 알고리즘의 종류로 페이지 부재가 발생했을 경우 가장 오랫동안 사용되.. 2023. 2. 6.
[프로그래머스] 점프와 순간 이동 이 문제를 처음 보고 그냥 아무 생각없이 dp를 떠올렸다... (근데 옛날에는 분명 dp였던 기억이.....?!!??!!!) dp로 풀 수 없는 이유는 아래와 같이 10억이라면 dp로 하더라도 10번은 가봐야 아는 문제이다.... 내가 푼 잘못 푼 풀이 def solution(n): dp = [0]*(n+1) dp[1] = 1 for i in range(2,n+1): if i%2 == 0: dp[i] = min(dp[i//2],dp[i-1]) else: dp[i] = dp[i-1]+1 return dp[n] 문재 풀이는 다음과 같다. 거꾸로 2로 나눠가면서 구하면 된다. 2로 안 나눠지면 점프가 필요한 거니까 건전지 사용 +1 def solution(N): result = 0 while N > 0: re.. 2023. 2. 6.
[프로그래머스] 예상 대진표 내가 푼 정답 def solution(n,a,b): count = 0 while True: a= a//2 b= b//2 count += 1 if a == b: break return count+1 위와 같이 할 시 1, 2 의 경우 2를 나누면 0, 1 이런식으로 결국에는 0과 1로 나뉠 수 있다는것을 깜박했다. 그러니 +1을 해주어 자리수를 맞춰주자. def solution(n,a,b): count = 0 while True: a= (a+1)//2 b= (b+1)//2 count += 1 if a == b: break return count 2023. 2. 6.
[프로그래머스] N개의 최소공배수 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 최소공배수(lcm)을 만드는 문제이다. 최소 공배수를 만들기 위해서는 먼저 최대공약수(gcd)를 알고 있어야 한다. 그리고 최대공약수는 아래와 같이 라이브러리를 이용하여 할 수도 혹은 직접 만들 수 있다. import math def gcd(a, b): # 최대공약수 while b > 0: a, b = b, a % b return a a,b =12,20 math.gcd(a, b) gcd(a,b) 이제 위의 최대공약수를 이용한 최소공배수를 만들어 보자 import math def lcm(a, b): .. 2023. 2. 6.
[백준] 수들의 합 2 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 이 문제는 투포인터 같이가기의 전형적인 문제이다. 먼저 문제는 A[i] + A[i+1] + … + A[j-1] + A[j] 처럼 합을 구하는 형식이기 떄문에 같이 가야한다. 아래의 풀이 방식은 시작은 left만 더한 상태로 sum 의상태를 보고 미리 가르키고 있는 right를 더한 후 right를 +1 인덱스 추가 시켜주는 방식이다. 이 방식은 sum 이 m 보다 큰데 가르키고 있던 right가 n을 초과하면 더이상 없다.. 2023. 2. 3.
[프로그래머스] 징검다리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제에서 기준은 n개의 돌을 징검다리에서 제거했을 때 최소 거리이다. 먼저 범위를 생각해보면 최소값은 징검다리에 돌이 겹쳐있는 경우는 없기 때문에 1이다. 최대 값은 시작지점과 도착지점사이의 거리인 distance이다. 이 값을 기준으로 중간값(mid)가 n개의 돌을 제거했을 때 돌 사이의 거리중 최소값이라고 가정해보자. 이 가정하에 돌을 제거했을 때 이 값(mid)보다 작은 거리는 없어야 한다. 즉 돌 사이의 거리를 구했을 때 이 mid 값보다 작으면 제거하고 크면 두는 방식의 전략을 사용해야한다. 돌.. 2023. 2. 2.
이분 탐색 & 매개변수 탐색 & 투 포인터 탐색 이분 탐색 vs 매개변수 탐색 vs 투 포인터 이분 탐색 : 정렬된 배열에서 중앙값(mid)이 가리키는 값이 내가 찾는 값인지가 중요 (대표 문제) 매개변수 탐색 : 배열에서 목표(target)가 원하는 조건에 만족할 때까지 최대한 찾는 것이 중요 (대표 문제) 투 포인터 : 배열에서 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리 (대표 문제) 이분 탐색 매개변수 탐색 투 포인터 시간 복잡도 O(logN) O(logN) O(N) 가정 데이터 정렬 x x 방식 mid를 활용 하여 매 연산마다 탐색의 범위를 절반으로 좁혀 나감 target과 일치하는 값을 찾아도 더욱 최적의 해가 있을때까지 찾아나감 양끝 혹은 모두 왼쪽에서 한칸씩 이동하며 알맞은 값 을 찾아나감 이분 탐색 이분 탐색이란 데이.. 2023. 2. 2.
[백준] 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 먼저 이문제가 이분 탐색인 이유에 대해 생각해보자 우리의 조건은 거리가 얼마나 최대한 멀게끔 하는것이다. 알아봐야 할 부분은 중요한 것은 집들이 수직선상에 위치하고 있다는 것을 생각해야 한다는 점이다. 풀이 1. array라는 리스트에 집들의 좌표를 입력받은 후에 정렬. 2. start = 1, end = array[-1] - array[0] 으로 설정. ( 시작값은 최소 거리, 끝 값은 최대 거리 ) 3. 앞.. 2023. 2. 2.
[백준]평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 유명한 냅색 알고리즘 이다. 냅색(Knapsack: 배낭) 알고리즘이란 담을 수 있는 물건이 나눌수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g등) : 분할 가능 배낭문제 담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제이다. 냅색 알고리즘은 문제를 보면 생각나는 방법은 두가지정도이다. 1. 모든 경우의 수를 넣어본다. -.. 2023. 2. 2.
[프로그래머스] 표 병합 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 잘 알려진 유니온 파인드 문제 -> 두개의 집합을 공통 부모를 찾는 문제 1. 50 X 50 이중 리스트 2. 상위 셀은 (r, c)가 작은 순서대로 정함 cell1(r1,c1), cell(r2,c2)에 대해서 -> r1 r1 == r2, c1 < c2 cell2가 부모 2023. 2. 1.
[프로그래머스] 이모티콘 할인행사 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 이모티콘 플러스를 최대한 늘리는 것 2. 이모티콘 플러스 가입자가 같다면 이모티콘 구매 비용이 높을 수록 좋다 1. 탐색문제 2. 탐색 시간 -> 어떻게 줄일 수 있을까? 이분 탐색, dp, greedy 같은 알고리즘을 적용해서 시간을 줄이는 문제 완전 탐색 -> 탐색시간을 어떻게 해도 줄알 수 없는 경우 / 혹은 완전 탐색을 써도 될때 3. 탐색 시간 계산 완전탐색을 한다면 시간은 얼마나 걸리지? -> 대략 1억 미만이면 가능이라고 판단 from itertools import product def so.. 2023. 2. 1.

티스토리툴바