Super Kawaii Cute Cat Kaoani

본문 바로가기

Algorithm/Python

(10)

[Python] 프로그래머스 - 튜플 https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 아이디어 문자열 처리하기 },{ 기준으로 슬라이싱하기 , 기준으로 슬라이싱하기 리스트 길이 기준으로 오름차순 정렬 정답 배열에 하나씩 추가하기 테스트 케이스 s = "{{4,2,3},{3},{2,3,4,1},{2,3}}" result = [3, 2, 4, 1] 🔎 풀이 def solution(s): answer = [] ### 문자열 처리하기 ### s1 = s.lstrip('{').rstri..

[Python] DFS 깊이 우선 탐색 🔎 DFS (Depth-First Search) 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 그래프의 기본 구조 노드(node)와 간선(edge)로 표현 그래프 탐색 하나의 노드를 시작으로 다수의 노드를 방문하는 것 두 노드가 간선으로 연결되어 있다면 ➡ 두 노드는 인접하다 그래프를 표현하는 2가지 방식 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프 연결 관계 표현 인접 리스트 (Adjacency List) : 리스트로 그래프 연결 관계 표현 인접 행렬 방식 2차원 리스트로 구현 연결되어 있지 않는 노드끼리는 무한의 비용 (999999999 등의 큰 값으로 초기화) INF = 99999999 graph = [ [0, 7, 5], [7, 0, INF], [5..

[Python] 재귀함수 💡 재귀함수란? 자기 자신을 다시 호출하는 함수 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() '재귀 함수를 호출합니다' 라는 문자열을 무한히 호출한다. ✔️ 재귀함수의 종료 조건 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날 지, 종료 조건을 꼭 명시해야 한다. def recursive_function(i): if i == 100 : return print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.') recursive_function(i + 1) print(i, '번째 재귀 함수를 종료합니다.') recursive_function(1) 컴..

[Python] 자료구조 - 스택, 큐 💡 자료구조란? 데이터를 표현하고 처리하기 위한 구조. 그 중 스택과 큐는 자료구조의 개념으로 다음의 두 핵심적인 함수로 구성된다. ✅ 삽입 (Push) : 데이터를 삽입한다. ✅ 삭제 (Pop) : 데이터를 삭제한다. ✏️ 스택 Stack ✔️ 선입후출 (First In Last Out) ✔️ 박스 쌓기 ➡️ 아래에 있는 박스를 치우기 위해서 위에 있는 박스를 먼저 내려야 한다. 초기단계 삽입 (5) 5 삽입 (2) 5 2 삽입 (3) 5 2 3 삭제 5 2 삽입 (7) 5 2 7 삭제 5 2 파이썬 코드 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.pop() stack.append(7) stack.pop() print(stack)..

[Python] BFS 알고리즘 💡 BFS BFS(Breadth First Search : 너비 우선 탐색) 알고리즘은 쉽게 말해 가까운 노드부터 탐색 큐 자료구조를 이용하는 것이 정석 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색 진행 💡 동작 방식 탐색 시작 노드를 큐에 삽입하고 방문 처리 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 2번의 과정을 더 이상 수행할 수 없을 때까지 반복 💡 파이썬 코드 from collections import deque # BFS 알고리즘 구현 def bfs(graph, start, visited): queue = deque([start]) # 시작 노드 큐에 넣고 ..

[Python] 이진 탐색 알고리즘 💡 이진 탐색 알고리즘 순차 탐색 : 앞에서부터 하나씩 확인. 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위 절반씩 좁혀가면서 탐색. 시작점, 끝점, 중간점 이용. ✔️예시 [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]에서 4 찾기 1. 시작점[0], 끝점[9], 중간점[4] (소수점 이하 제거) 0 2 4 6 8 10 12 14 16 18 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 중간점 기준으로 왼쪽을 탐색할지, 오른쪽을 탐색할지 고르기 : 찾는 값 4가 8보다 작기 때문에 왼쪽으로 2. 시작점[0], 끝점[3], 중간점[1] 0 2 4 6 [0] [1] [2] [3] 찾는 값 4가 중간값 2보다 크기 때문에 오른쪽으로 3. 시작점[2], 끝점[3],..

[Python] 성적 평균 - 코딩테스트 문제 Softeer 연습문제 : https://softeer.ai/practice/6294 🧷 문제 N명의 학생들의 성적이 학번순서대로 주어졌다. 학번 구간 [A, B]가 주어졌을 때 이 학생들 성적의 평균을 구하는 프로그램을 작성하라. 🧷 제약조건 1 ≤ N < 10^6 인 정수 1≤K < 10^4 인 정수 1 ≤Si < 100 인 정수 1 ≤ Ai ≤ Bi < N 🧷 입력형식 첫 번째 줄에 학생 수 N과 구간 수 K가 주어진다. 두 번째 줄에는 학생의 성적 Si(1≤i≤N)가 주어진다. i + 2 (1≤i≤K)번째 줄에는 1번 째 구간 Ai, Bi가 주어진다. 🧷 출력형식 i번째 줄에 i번째 구간의 성적평균(소수셋째자리에서 반올림)을 출력한다. 차이가 0.01이하이면 정답으로..

[Python] 정렬 알고리즘 - 선택, 삽입, 퀵, 계수 💡 선택 정렬 (Selection Sort) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 데이터와 바꾼다. 처리되지 않은 데이터 중 가장 작은 데이터를 맨 앞 데이터와 바꿈 이러한 과정 반복 (마지막 경우에는 처리하지 않아도 된다) 탐색 범위는 점점 줄어든다. 매번 선형 탐색한다. 복잡도 O(N^2) : n번 만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다. n + (n-1) + (n-2) = (n^2 +n - 2) / 2 🧷 구현 과정 array = [리스트] for : 리스트 길이만큼 for : i부터 0까지 1씩 줄면서 if : 현재 원소가 앞의 원소보다 작다면 : 서로 바꿈 else : break print(리스트) 🧷 파이썬 코드 array = [7, 5, 9, 0, 3, 1,..

[Python] DFS 알고리즘 💡 DFS DFS(깊이우선탐색)는 그래프의 모든 정점을 방문하는 알고리즘 한 정점에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방식 💡 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다. 💡 파이썬 코드 # DFS 함수 구현 def dfs(graph, v, visited): visited[v] = True # 현재 노드를 방문 처리 print(v, end = ' ') # 방문한 노드 출력 # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for..

[Python] 1이 될 때까지 (그리디 알고리즘) 💡 문제 설명. • 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다. N에서 1을 뺍니다. N을 K로 나눕니다. • 예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니 다. 이는 N을 1로 만드는 최소 횟수입니다. • N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요. 💡 문제 조건. 난이도 🟢⚪️⚪️ | 풀이 시간 15분 | 시간제한 2초 | 메..

이전 1 다음

728x90

티스토리툴바