프로그래밍 이야기/파이썬 코딩 테스트 스터디 40

파이썬 코딩테스트 스터디 5주차 #1 추가 - 두 개의 수로 특정갑 만들기(몸풀기 문제)

n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때,이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True, 없으면 False 를 반환하는 solution() 함수를 작성하세요 제약 조건n은 2 이상 10,000 이하의 자연수입니다.arr의 각 원소는 1 이상 10,000이하의 자연수입니다.arr의 원소 중 중복되는 원소는 없다.target은 1 이상, 20,000 이하의 자연수  방법1. 무작정 더하며 찾기 : 시간복잡도 : O(N^2)2중 for문으로 돌면서 찾는다 방법2. 해시 활용해서 찾기 개념은 이렇다위 예시 arr=[1,2,3,4,8], target=6인경우를 보자hashtable=[0] * (target+1)이렇게 되면 아래와 같은 배열이 생성..

파이썬 코딩테스트 스터디 3주차 #3 - 괄호 회전하기

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. (), [], {} 는 모두 올바른 괄호 문자열입니다.만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다.이 s를 왼쪽으로 x (0 ≤ x s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.  로직1. 왼쪽으..

파이썬 코딩테스트 스터디 2주차 #9 - 배열 추천 문제

누가 문제 3번 설명좀....   문제01. 배열의 평균값  https://school.programmers.co.kr/learn/courses/30/lessons/120817 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr def solution(numbers): answer = sum(numbers)/len(numbers) return answer   문제02. 배열 뒤집기https://school.programmers.co.kr/learn/courses/30/lessons/120821 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매..

파이썬 코딩테스트 스터디 3주차 #7 - 추천 문제 - 스택

추천 문제 1. 같은 숫자는 싫어https://school.programmers.co.kr/learn/courses/30/lessons/12906 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  내 풀이def solution(arr): answer = [] # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다. print('Hello Python') for i in range(len(arr)): if i!=0 : if arr[i]!=arr[i-1]: answer.append(a..

파이썬 코딩테스트 스터디 8주차 #4 - 그래프 최단 경로 구하기

최단 경로는 그래프의 종류에 따라 그 진의가 다르게 해석 가중치가 없는 그래프 : 간선 개수가 가장 적은 경로가중치가 있는 그래프 : 간선의 가충치의 총합이 최소 노드 1에서 5까지 최단 경로 구할 때, 간선 개수 기준 : 1개가 최소가중치 기준 : 1 → 2 → 5  (24)  최단 경로 대표 알고리즘 : 다익스트라 , 벨만-포드 다익스트라 알고리즘 시작 노드 설정하고 시작 노드로부터 특정 노드까지의 최소 비용 저장할 공간, 직전 노드 저장할 공간 마련최소 비용을 저장할 공간은 모두 매우 큰 값으로 초기화. 여기선 무한대(INF)로 표시, 직전 노드 저장도 INF시작 노드의 최소비용:0, 직전 노드는 자기 자기 자신아직 방문하지 않은 노드 중 현재까지 구한 최소 비용이 가장 적은 노드 선택해당 노드를 ..

파이썬 코딩테스트 스터디 8주차 #3 - 그래프 탐색 : 너비 우선 탐색

너비 우선 탐색   큐가 비어있는지 확인. 비었다면 방문할 수 있는 모든 노드를 방문했다는 의미비어있지 않으면, 큐에서 노드 팝팝한 노드와 인접한 모드 노드 확인, 아직 방문 안한 노드를 큐에 푸시  큐를 활용한 너비 우선 탐색 \  너비우선 탐색은 가중치가 없는 그래프에서 최단 경로 보장. 즉, 최단 경로 찾는 경우는 너비 우선 탐색아니면 깊이 우선 탐색. 너비우선 탐색 예제 : 미로 찾기, 최단 경로, 네트워크 분석   깊이 우선 탐색은 스택에서 팝할 때 방문처리너비 우선 탐색은 큐에 푸시할 때 방문처리  ♬ 자료 출처 - 책코딩 테스트 합격자 되기 - 파이썬 편   이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다. 감사합니다.

파이썬 코딩테스트 스터디 8주차 #2 - 그래프 탐색 : 깊이 우선 탐색

깊이 우선 탐색시작 노드부터 탐색을 시작해, 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문.최대 깊이 노드까지 방문 후이전 방문한 노드를 거슬러 올라가 연결된 노드에서 방문하지 않은 노드부터 다시 최대 깊이까지 차례대로 방문! 스택 활용 방법시작 노드 정한다.스택에 시작노드 푸시스택이 비었는 지 확인 → 비었다면, 모든 노드 방문했음 → 탐색 종료스택에서 노드 팝한다. (팝한 노드는 최근에 푸시한 노드)팝한 노드의 방문 여부 확인 →  방문 처리방문한 노드와 인접한 노드 확인  →  비 방문 노드 푸시 깊이 우선 탐색의 핵심  : 가장 깊은 노드까지 방문 후, 더 이상 방문할 노드 없으면, 최근 방문한 노드로 돌아온 다음,해당 노드에서 방문할 노드가 있는지 확인. 스택을 활용한 깊이 우선 탐색선..

파이썬 코딩테스트 스터디 8주차 #1 - 그래프 개념

그래프의 개념그래프 용어 정리  동그라미 : 노드화살표 : 간선간선 위 숫자 : 가중 그래프의 특징과 종류방향성, 가중치, 순환 특성에 따라 종류 구분 흐름을 표현하는 방향성간선은 방향이 있는 것도(방향 그래프), 없는 것도 있다.(무방향 그래프) 흐름의 정도를 표현하는 가중치 시작과 끝의 연결 여부 순환 그래프, 비순환 그래프  그래프 구현서울에서 부산으로 유동 인구 8,000명 발생.그래프의 노드, 간선, 방향, 가중치로 연결해보기데이터 담고 있는 노드 : 서울, 부산노드 잇는 간선 : 서울과 부산 연결 유무간선의 방향 : 서울 → 부산 간선의 가중치 : 8,000명 그래프의 구현 방식 1. 인접 행렬2. 인접 리스트 인접 행렬 그래프 표현: 배열을 활용하는 경우가 많음. 배열의 인덱스: 노드배열의 ..

파이썬 코딩테스트 스터디 7주차 #5 - 전화번호 목록

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.  구조대 : 119박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다.각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. 입출력 예 phone_book..

파이썬 코딩테스트 스터디 7주차 #4 - 영어 끝말 잇기

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.이전에 등장했던 단어는 사용할 수 없습니다.한 글자인 단어는 인정되지 않습니다. 다음은 3명이 끝말잇기를 하는 상황을 나타냅니다. tank → kick → know → wheel → land → dream → mother → robot → tank 위 끝말잇기는 다음과 같이 진행됩니다.1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.3..