본문 바로가기

파이썬35

SWEA - 두 개의 숫자열(1959) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 N 개의 숫자로 구성된 숫자열 Ai (i=1~N) 와 M 개의 숫자로 구성된 숫자열 Bj (j=1~M) 가 있다. 아래는 N =3 인 Ai 와 M = 5 인 Bj 의 예이다. Ai 나 Bj 를 자유롭게 움직여서 숫자들이 서로 마주보는 위치를 변경할 수 있다. 단, 더 긴 쪽의 양끝을 벗어나서는 안 된다. 서로 마주보는 숫자들을 곱한 뒤 모두 더할 때 최댓값을 구하라. 위 예제의 정답은 아래와 같이 30 이 된다. [제약 사항] N 과 M은 3 이상 20 이하이다. [입력] 가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주.. 2023. 10. 25.
SWEA - 패턴 마디의 길이(2007) 문제 패턴에서 반복되는 부분을 마디라고 부른다. 문자열을 입력 받아 마디의 길이를 출력하는 프로그램을 작성하라. [제약 사항] 각 문자열의 길이는 30이다. 마디의 최대 길이는 10이다. [입력] 가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 길이가 30인 문자열이 주어진다. 접근방식 입력되는 문자열을 words 변수에 받음 그리고 문자열을 한 문자씩 자르기 위해 list(words)를 listed_words라는 변수에 할당 빈 배열 arr를 선언해주고 listed_words길이만큼 j를 인자로 for문을 돌면서 j번째 문자가 arr에 없으면 arr에 할당해줌 만약 문자가 있으면 해당 문자가 문자열 반복이 끝나고 나오는 .. 2023. 10. 23.
그래프 탐색 알고리즘 - DFS/BFS 탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있음 스택 자료구조 선입후출(FILO): 먼저 들어온 데이터가 나중에 나가는 자료구조 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음(박스쌓기 - 먼저 쌓은 박스를 가장 마지막에 꺼낼 수 있음) append() - 삽입 pop() - 삭제 큐 자료구조 선입선출(FIFO): 먼저 들어온 데이터가 먼저 나가는 자료구조 입구와 출구가 모두 뚫려있는 터널로 스택을 시각화 할 수 있음 큐를 구현할 땐 파이썬에서 제공하는 리스트를 사용하는 것보다 deque 라이브러리를 사용하는 것이 더 시간적으로 효율적임! from collections import deque # 큐 구현을 위해 deque 라이브러리 사용.. 2023. 10. 23.
구현(Implementation) 구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 행렬 일반적으로 알고리즘 문제에서 2차원 공간은 행렬의 의미로 사용 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용 문제 1) 상하좌우 코드 N = int(input()) plans = input().split() x, y = 1, 1 # L, R, U, D로 이동 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] move_direction = ['L', 'R', 'U', 'D'] for plan in plans: for i in range(len(move_direction)): if plan == move_direction[i]: nx = x + dx[i] ny = y + dy[i] if nx < 1 o.. 2023. 10. 23.
그리디 알고리즘 그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶은 경우, 이때의 최적해는 무엇일까? 아래처럼 5 -> 7 -> 9로 거쳐가면 21이라는 최댓값이 나온다. 하지만 그리디 알고리즘은 어떻게 갈까? 놀랍게도 매순간 선택지 중 가장 최적의 해만 고른다. 루트 노드 5에서 시작해서 7, 10, 8 중에 가장 큰 10을 선택하고 4, 3중에 4를 선택한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 .. 2023. 10. 22.
코딩테스트 준비 - 파이썬 문법 정리 파이썬의 자료형 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 정수형 정수를 다루는 자료형 양의 정수, 0, 음의 정수가 포함 실수형 소수점 아래의 데이터를 포함하는 수 자료형 소수부가 0일 때 0 생략 가능 지수 표현 방식 파이썬에서는 e나 E를 이용한 지수 표현 방식 이용 e, E 다음에 오는 수는 10의 지수부를 의미 ex) 1e9 -> 10의 9제곱(1,000,000,000). 1 x 10^9 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대해 최단 거리를 무한(INF)로 설정하곤 함 이때 가능한 최댓값이 10억 미만이라면 무한(1NF)의 값으로 1e9를 이용할 수 있음 # 1,000,000,00의 지수 표현 방식 a = 1e9 print(a)// 1000000000.0 #752.5.. 2023. 10. 22.

티스토리툴바