우당탕탕 토이 프로젝트

문제링크https://school.programmers.co.kr/learn/courses/30/lessons/135807 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방식최대공약수를 구한 후, 상대방 배열을 나눠보면 된다.난 내장함수에 최대공약수 구하는 것이 있을 지 모르고 쌩으로 풀었지만보통 reduce + gcd 를 조합해서 푸는 것 같다  답import mathdef findDivisor(arr): common_divisor = set() min_arr = min(arr) max_check = int(math.sqrt(min_arr)) for i in ..

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  조건을 만족하는 케이스를 기준으로 탐색을 해가며 최소로 만족하는 step 을 되는 문제이다.최단거리랑 같은 개념으로 주로 BFS 를 사용한다면, 최소 step 에 return 을 하면 되기 때문에 BFS 방식을 추천한다.아래 풀이 코드에선 BFS, DFS 두가지 방식으로 풀이를 했다. def check(a, b): max_diff = 1 for i in range(len(a)): if a[i] != b[i..

코딩테스트 문제를 보고 공부 차 재귀를 이용하여 풀고자 했다.잘 생각이 나지 않았던 아이디어지만, 퀵정렬과 같은 방식으로 풀었고, 정리하고자 한다.  퀵정렬이란?아래 그림과 같이 pivot을 선택하고 분할 정복 방식을 사용하는 정렬 알고리즘이다.시간복잡도는 평균 O(nlogn)을 갖는다. 쉽게 말해 Pivot을 하나 정하여 좌측은 큰값, 우측은 작은값을 두는 방식이다. 그림출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html    장점은 평균적으론 빠르다는 것이고, 단점은 최악의 경우 O(n^2) 으로 느릴 수 있다는 것이다.참고로 선택정렬이나, 버블  정렬이 평균 O(n^2) 로 느린편이다. 내장 Sort 알고리즘은 뭘까?적다보니..

최근에 본 문제 중 정말 쉬운 난이도라고 느껴지지만, 시간을 진짜 많이 들어 풀었기 때문에기록 남긴다. 두가지 정도 풀이 방식을 기록하는데, 아직도 이걸 왜 못풀었을까 이해가 안된다.참회하고자 기록을 남긴다. input_data = "[[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15]" 로 주어질때 1, 2, 6, 11, 7, 3, 4, 8, 12 ,13, 9, 5, 10, 14, 15 로 출력하시오 1 2 3 4 56 7 8 9 1011 12 13 14 15 input_data = "[[1,2,3,4,5] [6,7,8,9,10] [11,12,13,14,15]]"def solution(s): arr = [word.replace('[','').replace(']','') fo..

"""최단거리 -> 다익스트라, BFS다익스트라 -> 간선에 가중치가 있을때BFS -> 가중치가 모두 1일때 효율적가중치가 음수일땐 벨만-포드 고려동서남북 중 갈수 있는 곳 Q에 넣어줌 최소로 도착한다는게 결국 모든 경로를 탐색할 필요가 없는것가다 막히는 경로는 알아서 pop 되며 소실 될거고많이 뻣어나가는 경로중 가장 일찍 도착하는 하나만 보면 되는거임 """from collections import dequedef bfs(maps): pos = [0,0] goal = [len(maps)-1,len(maps[0])-1] path = deque([(pos,1)]) visited = [[False for _ in range(len(maps[0]))] for _ in range(len(..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr시간복잡도 Olog(n)"""최소 힙의 0 index 가 key 이상일때까지heapq 는 정렬 되어있지 않고 그냥 최솟값을 찾는 알고리즘임"""import heapqdef solution(scoville, K): heap = scoville heapq.heapify(heap) answer = 0 while heap[0]

아이디어는 어렵지 않았지만, 구현하기 꽤 까다로웠다.소수를 일일이 판별할 생각은 했지만 찾다 보니 에라토스테네스의 채라는 개념을 보고 아이디어를 얻어 풀었다.해당 포스트는 아래 첨부한다.  일단 직관적으로 풀었지만, 애초에 2 미만은 제거한다던지 하면 한번 필터하는 작업을 없앨 수 있을 것 같다.그리고 순열을 구하는 것에 머리가 아팠지만 permutation 라는 걸 쓰면 순열도 쉽게 만들 수 있다더라~~ """여러개의 수가 소수인지 아닌지 -> 에라토스테네스의 체 이 수가 소수인지 아닌지 -> 제곱근 까지 나누기소수 중엔 2빼곤 짝수가 없다.numbers 의 가능한 모든 조합을 만듬 -> 짝수 제외가장 큰 수의 에라토스테네스 체를 통해 소수들 구함교집합"""import mathdef allCombi(n..

처음 문제를 보고, 삭제와 추가가 빈번하니 연결리스트를 사용해야 한다는 생각이 들었지만댓글들을 보니 스택으로도 최적화하여 구현하면 충분히 구현 가능하다고 하여 연결리스트를 사용하지 않고 구현했다. 효율성 테스트를 통과하지 못했던 첫 코드와 개선 코드 두가지를 작성해보겠다  정확성만 통과한 초기버전 코드다.dict 의 start,end 를 관리했고 이동할때 마다 이동할 행의 상태를 검사하며 이동했다.초기 선언을 dict으로 하여 검색 간의 복잡도는 O(1) 이지만, 이동할때마다 반복이 돌며 행 상태를 검사해야하기 떄문에그 부분에 시간을 많이 소요했다. 그래서 그 부분을 고치려고 생각해봤다.def solution(n, k, cmd): q = {i: 'O' for i in range(n)} ..

https://school.programmers.co.kr/learn/courses/30/lessons/76502 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr """x 만큼 회전 -> 즉 첫번째를 마지막 원소로 보내기한번씩 회전했을때 올바른 괄호인가 판별하는것올바른 괄호닫힘을 스택으로 쌓음열림이 나왔을떄 스택 pop 이랑 비교해서 맞으면 패스 아니면 outfor x 만큼: popleft 후 append 마지막 for len(deque): """from collections import dequedef solution(s): s = ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/64061 """각 열의 데이터를 큐로 만들어서 관리, 0은 필터해버림 빈 공간이니result스택에 move 로 옮김만약 열 큐가 비면(다 옮긴 열이면) passif 큐의 top == 추가원소: stack pop answer += 2else: append 큐.pop"""from collections import dequedef solution(board, moves): # 행,열 치환 new_board = [deque(filter(lambda x: x != 0, row)) for row in zip(*board)] result = [-1] an..