하나씩 배워나가는 개발일지

문제 패턴에서 반복되는 부분을 마디라고 부른다. 문자열을 입력 받아 마디의 길이를 출력하는 프로그램을 작성하라. [제약 사항] 각 문자열의 길이는 30이다. 마디의 최대 길이는 10이다. [입력] 가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 길이가 30인 문자열이 주어진다. 접근방식 입력되는 문자열을 words 변수에 받음 그리고 문자열을 한 문자씩 자르기 위해 list(words)를 listed_words라는 변수에 할당 빈 배열 arr를 선언해주고 listed_words길이만큼 j를 인자로 for문을 돌면서 j번째 문자가 arr에 없으면 arr에 할당해줌 만약 문자가 있으면 해당 문자가 문자열 반복이 끝나고 나오는 ..

탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있음 스택 자료구조 선입후출(FILO): 먼저 들어온 데이터가 나중에 나가는 자료구조 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음(박스쌓기 - 먼저 쌓은 박스를 가장 마지막에 꺼낼 수 있음) append() - 삽입 pop() - 삭제 큐 자료구조 선입선출(FIFO): 먼저 들어온 데이터가 먼저 나가는 자료구조 입구와 출구가 모두 뚫려있는 터널로 스택을 시각화 할 수 있음 큐를 구현할 땐 파이썬에서 제공하는 리스트를 사용하는 것보다 deque 라이브러리를 사용하는 것이 더 시간적으로 효율적임! from collections import deque # 큐 구현을 위해 deque 라이브러리 사용..

구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 행렬 일반적으로 알고리즘 문제에서 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..

그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶은 경우, 이때의 최적해는 무엇일까? 아래처럼 5 -> 7 -> 9로 거쳐가면 21이라는 최댓값이 나온다. 하지만 그리디 알고리즘은 어떻게 갈까? 놀랍게도 매순간 선택지 중 가장 최적의 해만 고른다. 루트 노드 5에서 시작해서 7, 10, 8 중에 가장 큰 10을 선택하고 4, 3중에 4를 선택한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 ..

파이썬의 자료형 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 정수형 정수를 다루는 자료형 양의 정수, 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..

복잡도란? 시간 복잡도: 특정 크기의 입력에 대해 알고리즘의 수행 시간 분석 공간 복잡도: 특정 크기의 입력에 대해 알고리즘의 메모리 사용량 분석 시간 복잡도가 높다 -> 알고리즘 실행에 오랜 시간이 걸린다 공간 복잡도가 높다 -> 알고리즘 실행에 많은 메모리가 사용된다 빅오 표기법 가장 빠르게 증가하는 항만 고려하는 표기법 ex) 연산 횟수가 3N^3 + 5N^2 + 1,000,000 이면 시간 복잡도는 O(N^3) 알고리즘 설계 팁 연산 횟수가 5억을 넘어가는 경우: - C언어: 1~3초 가량 시간 소요 - Python: 5~15초 가량 시간 소요 코딩테스트 문제에서 시간제한은 통상 1~5초 가량 수행 시간 측정 소스코드 예제 import time start_time = time.time() # 측정..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 스도쿠는 숫자퍼즐로, 가로 9칸 세로 9칸으로 이루어져 있는 표에 1 부터 9 까지의 숫자를 채워넣는 퍼즐이다. 같은 줄에 1 에서 9 까지의 숫자를 한번씩만 넣고, 3 x 3 크기의 작은 격자 또한, 1 에서 9 까지의 숫자가 겹치지 않아야 한다. 입력으로 9 X 9 크기의 스도쿠 퍼즐의 숫자들이 주어졌을 때, 위와 같이 겹치는 숫자가 없을 경우, 1을 정답으로 출력하고 그렇지 않을 경우 0 을 출력한다. [제약 사항] 1. 퍼즐은 모두 숫자로 채워진 상태로 주어진다. 2. 입력으로 주어지는 퍼즐의 모든 숫자는 1 이상 9 이하의 정수이다. 접근방식 arr..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 N X N 크기의 단어 퍼즐을 만들려고 한다. 입력으로 단어 퍼즐의 모양이 주어진다. 주어진 퍼즐 모양에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 작성하라. [예제] N = 5, K = 3 이고, 퍼즐의 모양이 아래 그림과 같이 주어졌을 때 길이가 3 인 단어가 들어갈 수 있는 자리는 2 곳(가로 1번, 가로 4번)이 된다. [제약 사항] 1. N은 5 이상 15 이하의 정수이다. (5 ≤ N ≤ 15) 2. K는 2 이상 N 이하의 정수이다. (2 ≤ K ≤ N) 접근방식 0과 1로 이뤄진 NxN 배열이 주어지면 연속된..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 1부터 N까지의 숫자에서 홀수는 더하고 짝수는 뺐을 때 최종 누적된 값을 구해보자. [예제 풀이] N이 5일 경우, 1 – 2 + 3 – 4 + 5 = 3 N이 6일 경우, 1 – 2 + 3 – 4 + 5 – 6 = -3 [제약사항] N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10) 접근 방식 N이 주어지면 1~N까지의 숫자 중 홀수는 그대로 더해주고 짝수는 그 짝수값에 -를 붙여서 전체를 더하는 문제 N을 입력받으면 arr에 1~N까지의 숫자를 넣어줌 그리고 arr를 돌면서 각 인덱스의 값이 2로 나눠지면(짝수) ans_arr에 (해당 값-2*해..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 3 6 9 게임을 프로그램으로 제작중이다. 게임 규칙은 다음과 같다. 1. 숫자 1부터 순서대로 차례대로 말하되, “3” “6” “9” 가 들어가 있는 수는 말하지 않는다. 1 2 3 4 5 6 7 8 9… 2. "3" "6" "9"가 들어가 있는 수를 말하지 않는대신, 박수를 친다. 이 때, 박수는 해당 숫자가 들어간 개수만큼 쳐야 한다. 예를 들어 숫자 35의 경우 박수 한 번, 숫자 36의 경우 박수를 두번 쳐야 한다. 입력으로 정수 N 이 주어졌을 때, 1~N 까지의 숫자를 게임 규칙에 맞게 출력하는 프로그램을 작성하라. 박수를 치는 부분은 숫자 대신..