마스터링

https://programmers.co.kr/learn/courses/30/lessons/72412

[문제] 디딤돌의 내구도와 한번에 건널 수 있는 디딤돌의 갯수가 주어졌을 때 최대 몇명이 건널 수 있는지 계산하는 문제 입니다. 입출력 예시 : stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k = 3 [풀이] 1. 아주 간단한 방법: 한명씩 건넌다고 치고 stones의 모든 원소값을 1씩 빼고 다시한번 0이하의 값이 연속되는지 확인합니다. 하지만 이 방법은 2중 for문으로 n^2의 시간복잡도가 소요됩니다. 원소의 최대값은 2억이고, 배열의 크기의 최대값은 20만이므로 n^2의 방법으로는 1초안에 풀이가 불가능합니다. 2. 이진탐색법의 LogN의 시간복잡도를 활용 몇명이 건널 수 있는지가 문제이기때문에 몇명인지를 이진탐색으로 탐색해서 구해보면 빠르게 구할 수 있을거 같습니다...

https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 유저들의 id_list가 있고, 이 유저들의 신고한 내역인 report가 주어집니다. report를 기반으로 딕셔너리에 신고당한 유저 : 신고한 유저 형태로 저장한다음 신고한 유저의 수가 k가 넘는 신고당한 유저를 신고한 유저를 기준으로 다시한번 메일을 수신하는 딕셔너리에 넣어줍니다. 그리고 마지막에 id_list 순서대로 for문을 돌며 result값을..

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 기본적인 DP(Dynamic Programming)문제 입니다. 어떤 경로로 가는것이 최고의 합이 나오는지 궁금한 문제 입니다. 예시 풀이 첫번째줄에서 두번째줄로 갈때 7 에서 3 또는 8 을 고를때 8을 고르는게 좋을 수 있지만 8을 선택하면 세번째줄의 8을 고르지 못할 수 있습니다. 만약 세번째줄의 8이 100이었으면 그때그때 최선의 숫자를 고르는것은 좋지 않은 선택이 될 수 있습니다. 따라서 가능한 경..

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 풀이 방법 : 간단하게 앞에 있는 숫자(큰 자릿수)가 뒤에 있는 숫자(작은 자릿수)보다 작으면 앞에 있는 숫자를 지워주는 방식으로 풀었습니다. k개 만큼을 이러한 방식으로 지운 후 남은 number는 큰수가 앞, 작은수가 뒤로 정렬이 되어 있는 상태 이므로 뒤에서 부터 k개 만큼 줄인 후 return..

https://programmers.co.kr/learn/courses/30/lessons/17679?language=python3 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 애니팡처럼 2x2 같은 모양의 캐릭터가 있으면 블록을 지우는 게임 입니다. 알고리즘은 다음과 같습니다. 모양이 같은 블록을 지우고 위에 있던 블록들이 아래로 떨어져야 하는데 이부분을 구현하기 위해서는 리스트를 회전 시켜 주는게 좋습니다. list(map(list,zip(*board))) 코드를 쓰면 리스트를 ..

https://programmers.co.kr/learn/courses/30/lessons/12953?language=go 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr func gcd(x int, y int) int { if x % y == 0 { return y } else { return gcd(y, x % y) } } func lcm(x int, y int) int { return (x * y) / gcd(x,y) } func solution(arr []in..

0,0 에서 시작해서 mapsize, mapsize 까지 가기 위한 최단거리를 구하는 문제이다. BFS는 공식과도 같다 하여 BFS알고리즘을 검색하여 참고하여 코드를 구현 하였다. # https://programmers.co.kr/learn/courses/30/lessons/1844 # BFS를 써야 풀 수 있는 문제 from collections import deque def nextXY(n, maps, sizeY, sizeX) : y = n[0] x = n[1] depth = n[2] nextque = [] if y - 1>= 0 and maps[y - 1][x] != 0 : #up nextque.append([y - 1, x, depth + 1]) if y + 1 < sizeY and maps[y ..