본문 바로가기

알고리즘24

[ SWEA ] D2 - 1940, 1928, 1288, 1284, 1204 - python 문제풀이 1940 가랏 RC카 접근법 : 커맨드가 0이 아닐 경우에만 뭔가 계산을 해주고, 0일때는 바로 현재 속도만 더해주면 된다 for tc in range(int(input())): commands = int(input()) distance = 0 current_speed = 0 for _ in range(commands): info = input() if info != "0": #앞에서 1인지2인지도 비교안하고 빠질수있음 command = info.split(" ")[0] acceleration = int(info.split(" ")[1]) if command == "2" and current_speed < acceleration: current_speed = 0 elif command == "2": cu.. 2021. 6. 28.
[ SWEA ] D2 - 1954, 1948, 1946, 1945 - python 문제풀이 1954 달팽이 숫자 달팽이처럼 돌기 위해서는 오른쪽, 아래, 왼쪽, 위쪽 방향을 반복적으로 돌아가면서 이동해 들어가고, 그 빈도는 위 그림에서 볼 수 있듯이 각 n번에서 1번 순서대로, 처음을 제외하면 각각 2번씩 반복적이라는 규칙을 찾을 수 있다. for tc in range(int(input())): N = int(input()) snail = [[0]*N for _ in range(N)] number = 1 jump_cnt = N direction = 'right' # 'right','down','left','up'순으로 바뀔 것 row_idx,col_idx = 0,0 while number 2021. 6. 27.
[ SWEA ] D2 - 1983, 1979, 1976, 1974 - python 문제풀이 1983 조교의 성적매기기 scores = ["A+","A0","A-","B+","B0","B-","C+","C0","C-","D"] for tc in range(int(input())): N,K = map(int, input().split()) # i번째 점수는 (i+1)번 학생의 점수 info = [list(map(int, input().split())) for _ in range(N)] student_scores = [] for i in range(N): total = info[i][0]*0.35 + info[i][1]*0.45 + info[i][2]*0.2 student_scores.append([total, (i+1)]) student_scores.sort(key=lambda x:x[0],rev.. 2021. 6. 24.
[ SWEA ] D2 - 2001, 1989, 1986, 1984 - python 문제풀이 2001 파리퇴치 퇴치할 파리 정사각형이 어디까지 이동할 수 있을 지 파악해서 갈 수 있는 곳 까지만 for문을 도는게 그나마 시간을 조금이라도 줄이는 방법 for tc in range(int(input())): N,M = map(int, input().split()) fly = [list(map(int, input().split())) for _ in range(N)] max_value = 0 for i in range(N-M+1): for j in range(N-M+1): row_idx = i col_idx = j tmp = 0 for k in range(M): tmp += sum(fly[row_idx+k][col_idx:col_idx+M]) if tmp > max_value: max_value = .. 2021. 6. 24.
[ SWEA ] D2 - 1859, 1926, 2007, 2005 - python 문제풀이 1859 백만장자프로젝트 문제를 먼저 잘 이해하고 생각한 뒤 풀면 생각보다 쉽게 풀리는 문제 Idea 1. 일단, 최대의 이익을 내려면 계속 사다가 가장 비싸게 팔 수 있는 시점에 팔아야 한다. Idea 2. 배열을 뒤에서 부터 순회하면서, 특정 시점에서 얼마에 파는게 가장 최대일지 구하면 된다 - 제일 마지막 순간에 팔 수 있는 가격을 초기값으로 설정 - 뒤에서부터 오면서, 더 비싸게 팔 수 있는 순간이 올 경우(t2) 최대값으로 가격을 갱신해주기 - 더 비싸게 팔 수 있는 순간이 아니라면, 사는게 무조건 이득임 for tc in range(int(input())): N = int(input()) data = list(map(int, input().split())) max_value = 0 curmax.. 2021. 6. 24.
[ SQL 고득점 kit ] SELECT - mysql 01 모든 레코드 조회하기 SELECT * FROM ANIMAL_INS ORDER BY ANIMAL_ID; 02 역순 정렬하기 : 정렬은 ORDER BY, 순서는 DESC(내림차순-큰값부터) or ASC(오름차순-기본값) SELECT NAME, DATETIME FROM ANIMAL_INS ORDER BY ANIMAL_ID DESC; 03 아픈 동물 찾기 SELECT ANIMAL_ID, NAME FROM ANIMAL_INS WHERE INTAKE_CONDITION = 'Sick' ORDER BY ANIMAL_ID; 04 어린 동물 찾기 : 같지 않다 (NOT, !=, ) SELECT ANIMAL_ID, NAME FROM ANIMAL_INS WHERE NOT INTAKE_CONDITION='Aged' ORD.. 2021. 6. 21.
[ Codility ] MaxProductOfThree - python 개념 Lesson 6. Sorting 두 번째 문제 문제요약 입력으로 주어진 정수 배열에서 숫자 3개를 곱한 값 중 최대를 리턴하라 첫번째 접근(효율성 고려X) 문제에 충실히 만들수 있는 모든 인덱스 조합을 만들고, 그 조합대로 값을 곱한 뒤 최대일 경우 max-value값을 갱신해주는 코드(3개니까 당연히 3중 for문을 돌고, 시간복잡도는 O(N**3)이상) def solution(A): max_v = A[0]*A[1]*A[2] for i in range(len(A)-2): for j in range(i+1, len(A)-1): for k in range(j+1,len(A)): if A[i]*A[j]*A[k]>max_v: max_v = A[i]*A[j]*A[k] return max_v 두번째 접근(통.. 2021. 6. 18.
[ Codility ] Distinct - python 개념 Lesson 6. Sorting 첫 번째 문제 문제요약 N개의 정수를 원소로 갖는 배열A가 입력으로 주어질 때, 원소들의 중복을 제외한 총 개수를 리턴하라 첫 번째 접근 (효율성 고려X, 통과는 O) 파이썬 내장함수를 이용한 풀이(set로 중복 제거한뒤 그 개수만 리턴하는 코드) # 방법 1 def solution(A): return len(list(set(A))) # 방법 2 - 굳이 list를 안해도 돼 ㅎㅁㅎ def solution(A): return len(set(A)) 생각보다 너무 빨리 대충 푼 것 같은 느낌에 set 쓰지 않고 푸는 다양한 방식을 찾아보기로 했다 두 번째 접근 (효율성X) 처음 파이썬을 배웠다면 썼을 것 같은 코드로 문제에 충실하게 짠 코드. A를 쭉 돌다가 지금까지 나.. 2021. 6. 18.
[ Codility ] PassingCars - python 개념 Lesson 5. Prefix Sums 네 번째 문제 문제요약 0,1로만 이루어진 배열A가 입력으로 주어짐. 0은 동쪽으로 가는 차, 1은 서쪽으로 가는 차일때 서로 마주칠 수 있는 케이스는 얼마나 되는지 리턴하는 문제. 예시) [0,1,0,1,1] => (0,1),(0,3),(0,4),(2,3),(2,4) 5개 => 5리턴 첫번째 접근( 효율성 고려X ) 문제에 충실하게, 앞에서부터 순회하다가 0이 나오면 그 뒤에 있는 1의 개수를 구해 더해나가는 방식 def solution(A): cnt = 0 for i in range(len(A)-1): tmp = 0 if A[i] == 0: tmp += A[i+1:].count(1) cnt += tmp return cnt 답은 맞지만 역시 타임아웃. for.. 2021. 6. 17.
[ Codility ] MinAvgTwoSlice - python 개념 Lesson 5. Prefix Sums 세 번째 문제 문제요약 n개의 원소를 갖는 리스트가 주어지면, 0부터 n-1사이에서 두 수를 뽑아 작은 값(P)를 시작인덱스, 큰 값(Q)를 끝인덱스로 정해 A[P:Q+1]에 해당하는 리스트를 슬라이스라고 한다. 만들 수 있는 모든 슬라이스 중 슬라이스 내부 원소들의 평균이 가장 낮을때의 P값(시작인덱스)를 리턴. 첫 번째 접근(효율성 고려X) def solution(A): n = len(A) min_v = sum(A)/n r = 0 comb = [(i,j) for i in range(n-1) for j in range(i+1,n)] for pair in comb: new_v = sum(A[pair[0]:(pair[1]+1)])/(pair[1]-pair[0]+.. 2021. 6. 16.
[ Codility ] CountDiv - python 개념 Lesson 5. Prefix Sums 첫 번째 문제 문제요약 입력으로 정수 A, B, K가 주어졌을 때 정수 A부터 정수 B(를 포함해서) 사이에 있는 정수들 중 K로 나누어 떨어지는 수들의 총 개수를 리턴하라 첫번째 접근(효율성 고려X) 문제에서 풀이한 방식 그대로 코드 구현 def solution(A, B, K): sn = A # 01 starting number를 A로 설정 cnt = 0 while sn 2021. 6. 15.
[ Codility ] GenomicRangeQuery - python 개념 Lesson 5. Prefix Sums 두 번째 문제 문제요약 A,C,G,T 네 종류의 dna 시퀀스가 있고, 각각 1,2,3,4 의 impact factors를 갖고 있음. 네 알파벳이 섞인 문자열 S와 시작 인덱스 범위를 원소로 갖는 리스트 P, 마지막 인덱스 범위를 원소로 갖는 리스트 Q가 입력으로 주어짐. P와 Q의 동일 인덱스 값이 각각 문자열에서 확인할 인덱스의 시작범위와 끝 범위를 의미함. 처음 주어진 문자열에서 P,Q에 주어진 범위 인덱스만을 볼 때 가장 impact factor가 작은 값을 리스트에 담아 리턴하면 됨. ( 결과적으로 리스트에는 P 또는 Q의 원소 개수 만큼 값이 들어있음 ) 첫번째 접근(효율성 고려X) 문제에서 풀이한 방식 그대로 코드 구현 def solution(S.. 2021. 6. 15.

티스토리툴바