알고리즘63 SWEA 1983 조교의 성적 매기기 (핵심 : 순서와 값 함께 저장하는 방법) 💡문제 분석 요약주어진 학생들의 중간, 기말, 과제점수를 비율별로 종합하여 등급을 매긴다.등급은 총 10개 등급이 있고, 각 등급마다 10% 학생들이 차지하게 된다. (ex. A+ 10%, A0 10% ...)이때, 특정 순서에 있는 학생의 학점을 출력한다.💡알고리즘 설계처음엔 dictionary를 생각했다. 왜냐면 학생의 "순서"와 value를 함께 저장하는 방법이라고 생각했기 때문.그래서 student[순서] = A+ 이런느낌으로 저장하려 했는데, 정렬 부분에서 잘 안됐다.따라서 우린 students에 튜플 자체를 append하는 방식을 사용한다. (순서, 학점) 형식으로 튜플을 통째로 append해준다.💡코드t = int(input())for test_case in range(t): n,.. 2024. 10. 4. SWEA 2001 파리 퇴치 (핵심 : i+x, j+y) 💡문제 분석 요약N*N 파리 box에서 파리를 딱 내리치면 M*M만큼의 칸을 내리칠 수 있어서 해당 칸의 파리를 잡을 수 있다.이때, 잡을 수 있는 파리의 최대 수를 구한다.💡알고리즘 설계보자마자 4중 for문은 아닐거고 ...... 라고 시작했는데 결국 다른 풀이를 생각해내진 못했다.물론 4중 for문이 될 것이라는 확신은 있었다. N의 크기가 15고, M의 크기는 2~N 이었기 때문에 최대 O(225)일 것이라고 생각해서 될 거라고 봤는데 사실 크기가 커지면 쓸모 없는 코드니까 .... 4중 for문은 피하려고 했다.사실 M*M 박스는 움직이면서 이전과 겹치는 부분이 있으니까 그 부분만 빼고 나머지 새로운 열 혹은 행에 대해서 더해주면 더 효율적일 것이라고 생각했는데 코드를 생각해내진 못했다.💡.. 2024. 10. 1. SWEA 2007 패턴 마디의 길이 (핵심 : startswith) 💡문제 분석 요약주어진 문자열에 대해서 반복되는 패턴의 길이를 출력한다.문자열은 30글자가 주어지고, 패턴은 최대 10글자이다.💡알고리즘 설계한글자씩 슬라이싱 하면서 슬라이싱된 패턴이 반복되는지 확인한다.이때 "반복된다"라는 것은 이어붙였을 때, 이게 들어있는지 확인하면 된다.예를들어 sam이 패턴이 되려면 samsamsam이렇게 되어야하는거지, sam1sam2sam3 이건 패턴이 아니다.💡코드T = int(input())for t in range(T): lst = input() # 문자열 길이는 30 고정 for i in range(1, 11): # 1부터 10까지 마디 잘라봄 (마디 최대 길이가 10) pattern = lst[:i] # 이 패턴이 "연속으로" 반복되느냐?.. 2024. 9. 30. SWEA 1859 백만 장자 프로젝트 (핵심 : 맨 뒤에서부터 계산하기) 💡문제 분석 요약사재기를 하기 위해서 사야할 때랑 팔아야할 때를 알아야함.쉽게 말해서, 내가 지금 샀을 때보다 나중에 비싸게 팔 수만 있다면 무조건 사는 게 이득. 즉, 오늘보다 비싼 날이 뒤에 있기만 하면 구입.💡알고리즘 설계맨 뒤에서부터 max값을 업데이트해가면서 이익을 계산한다.만약 .... max1 .... max2 이런식으로 있다고 해보자. max1 > max2라고 하면, 앞에서 산건 max1때 털어내겠고, 그럼 뒤에서 산건 max2때 털어낸다. 만약 max1 따라서 max2에 깃발 꽂고, 뒤에서부터 앞으로 계산해간다. max2부터 max1까지 있는 모든 물건 다사고 max2때 털어내면 되니까 이익 = max2 - element 이런식으로 차익을 계산하면 된다.💡코드T = int(input.. 2024. 9. 29. 프로그래머스 - 괄호 회전 (핵심 : 회전코드 이해) 💡문제 분석 요약괄호를 맞추는데, 소 중 대괄호를 다 맞춰야한다.또한 괄호가 안맞는 문자열이 있더라도 회전시켜서 괄호 짝이 맞으면 맞는 것으로 간주하고 이렇게 회전포함해서 알맞은 경우가 몇개인지 구한다.💡알고리즘 설계괄호 짝 맞추는 것은 stack으로 구현한다.💡코드def check(s): # ( { [ 다 체크해야함. stack = [] for c in s: if c == "(" or c == "{" or c == "[": stack.append(c) # 여는 괄호는 다 넣어줌 else: # 닫는 괄호 체크하기 if len(stack) == 0: # 처음 오는 닫는괄호일 땐 바로 컷 retu.. 2024. 9. 20. 프로그래머스 - 방문 길이 (핵심 : line 체크) 💡문제 분석 요약위 아래 왼쪽 오른쪽 명령어가 들어오면 해당 좌표로 이동한다.이동하지 못하는 위치라면, 즉 벗어났다면 해당 명령은 무시한다.이때 새로운 길에 대해서 체크한다. 갔던 길을 다시 가는 것은 count하지 않는다.💡알고리즘 설계처음엔 전형적인 DFS인줄 알았으나, 이미 주어진 명령어와 범위가 있어서 DFS까지는 안써도 되는 거로 인식했다.다만 왔던 길인지 알아야하므로 visited같은 역할을 하는 자료구조가 필요했고, 이는 set()을 사용했다.💡코드def operation(x, y, op): if op == "U": y += 1 elif op == "D": y -= 1 elif op == "R": x += 1 elif op ==.. 2024. 9. 11. 1303 전쟁 💡문제 분석 요약구역별로 병사들이 몇명 있는지 구한다. 해당 구역 내에 병사들의 power는 병사들 수의 제곱이다.white, blue 각각의 power를 구한다.💡알고리즘 설계DFS, BFS 둘 다 가능하다.상하좌우 체크와, 병사들 수 체크만 잘 하면 된다. 병사들 총 수는 DFS 실행횟수와 같다.💡코드import syssys.setrecursionlimit(10**6)# 가로, 세로 "길이"가 n, m임. 즉 행:m , 열:nn, m = map(int, input().split()) # 가로가 열 개수, 세로가 행 개수라는 것을 헷갈리면 안됨 !!!!!!!!!!!!!!!!!!!!!!!!!!war = [list(input()) for _ in range(m)] # 여기서도 range(n)이 아니.. 2024. 8. 13. 1789 수들의 합 💡문제 분석 요약서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까 ?이때 중요한 건, 이 자연수 합의 최대값이 아니라 최대 "개수"를 구하는 것이다. 이거 잘못 읽어서 살짝 헤맸다.💡알고리즘 설계최대 "개수"라는 것에 주목해보자. 숫자가 많이 들어갈수록 이득이다. 그러므로 가장 작은 수부터 채워넣는 것이 이득이라는 소리.💡코드n = int(input())i = 0# 핵심 : 숫자들 합이 n을 만족시키는 최대 개수를 구하는 것# 따라서, 가장 작은 수부터 채워나가는 것이 유리함 -> 0부터 한개씩 채워나감# ex) 200이라는 값에 최대 몇개의 수가 들어가느냐? 200부터 0, 1, 2, ... 차례로 빼보면 됨.while True: if n 💡시간복잡.. 2024. 8. 13. 12845 모두의 마블 💡문제 분석 요약카드 합성시 합쳐진 카드의 레벨만큼 돈을 받고, 이 돈이 최대가 되는 경우를 구한다.레벨이 높은 카드는 합쳐져도 레벨이 변하지 않는다. = 즉, 계속 사용된다💡알고리즘 설계인덱스를 신경써야하는 것으로 이해해서, enumerate나 dictionary를 생각했다. 근데 enumerate는 인덱스 값을 변경할 수가 없었다.그러나 카드의 위치가 고정이 아니라는 것을 알고, 정렬 후 최대 레벨의 카드를 기준으로 합치면 된다고 생각했다.💡코드n = int(input())cards = sorted(list(map(int, input().split())))print(cards[-1]*(n-1) + sum(cards[:n-1]))"""1. 일단 정렬해서 가장 큰 레벨을 뒤로 빼줌. (최대 레벨이 .. 2024. 8. 3. 이전 1 2 3 4 ··· 7 다음 반응형
