jujucode

[프로그래머스/파이썬] 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약일렬로 놓인 징검다리가 있고, 각 디딤돌에는 숫자가 적혀있다. 밟을 때마다 숫자가 1씩 줄어들고, 0이 되면 더 이상 밟을 수 없다. 못 밟는 돌은 건너뛰어야 하는데, 이때 한 번에 최대 k칸까지만 뛸 수 있다.친구들이 한 명씩 순서대로 건너는데, 최대 몇 명까지 건널 수 있는지 구하는 문제. stones 배열 크기가 최대 20만, 값도 최대 2억까지 가능해서 완전탐색은 어림도 없다.알고리즘 / 핵심 아이디어처음엔 "그냥 시뮬레이션 돌리면 안되나..

[프로그래머스/파이썬] 양궁대회

https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약라이언이랑 어피치가 양궁 결승전 붙는 문제. 어피치가 먼저 화살 n발 다 쏘고, 그다음에 라이언이 n발을 쏨.점수는 10점부터 0점까지 있고, 각 점수마다 더 많이 맞힌 사람이 그 점수를 통째로 가져감 (같으면 어피치가 가져감, 둘 다 0발이면 아무도 안 가져감).라이언이 화살을 어떻게 배분해야 어피치를 가장 큰 점수차로 이길 수 있는지 구하는 문제. 못 이기면 [-1] 리턴.처음 보고 감이 하나도 안 왔음.. n발을 11개 칸에 어떻게 나눠..

[프로그래머스/파이썬] 숫자게임

https://school.programmers.co.kr/learn/courses/30/lessons/12987# 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제A팀은 이미 출전 순서를 다 정해서 공개해버렸고, B팀은 그걸 보고 자기네 팀원 순서를 자유롭게 짤 수 있음. 각 경기에서 더 큰 수를 낸 쪽이 1점 먹는 거고, 같으면 무승부. B팀이 최대로 얻을 수 있는 점수를 구하면 됨. 풀이1차 시도 - A랑 B를 각각 정렬해서 포인터 하나씩으로 그냥 순회하면서 "A보다 크면 카운트" 이런 식으로 접근했는데, 이러면 A의 원래 순서(승부 순서) 자체가 씹혀버림. 정렬한 순간 그건 이미 원래 매치업이 아니니까..

[프로그래머스/파이썬] 최솟값

https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제길이가 같은 두 배열에서 원소를 선택해 곱해서 누적합을 최소로 만드는 문제이다. 해결곱한 수의 총합을 최소로 만들려면 각 배열에서 아직 계산 하지 않은 최솟값과 최댓값을 구해서 곱해서 더해주면 된다.따라서 A정렬, B는 거꾸로 정렬 후 순서대로 곱해주면 답이된다.def solution(A,B): answer = 0 A.sort() B.sort(reverse=True) for i in range(len(A)): ..

[프로그래머스/파이썬] 최댓값과 최솟값

https://school.programmers.co.kr/learn/courses/30/lessons/12939 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제숫자 리스트가 문자열로 주어졌을때, 해당 리스트에서 최솟값과 최댓값을 순서대로 리턴하는 문제이다. 해결문자열을 공백을 기준으로 분리 후 정수 처리한 다음, 파이썬 리스트 함수의 max 와 min 함수를 이용하여 문자열로 만들면 되는 간단한 문제이다.def solution(s): answer = '' L = list(map(int, s.split())) #print(L) answer = str(min(L)) +' '+ str(ma..

https://school.programmers.co.kr/learn/courses/30/lessons/468373 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약n개의 배양체가 트리 형태로 연결되어 있고, 각 파이프는 A/B/C 세 종류 중 하나다. 하나의 배양체가 바이러스에 감염된 상태에서 시작하며, 같은 종류의 파이프를 한꺼번에 열었다가 닫는 행동을 최대 k번 반복해 감염을 최대한 퍼뜨려야 한다. 한 종류를 열면 그 종류로 연결된 경로를 타고 감염이 쭉 퍼진다. 최종적으로 감염될 수 있는 배양체 수의 최댓값을 구하면 된다.n ≤ 100, k ≤ 10이라는 제약이 핵심 힌트다. 처음엔 그래프 문제니..

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약집들이 원형으로 배치돼 있고, 인접한 두 집을 동시에 털면 경보 울림. 각 집에 있는 돈이 담긴 배열이 주어질 때 훔칠 수 있는 최댓값 구하는 문제. 일반적인 "집 도둑" DP 문제인데 원형이라는 게 함정.핵심 아이디어일렬로 늘어선 집이면 그냥 기본 DP로 풀림: dp[i] = max(dp[i-1], money[i] + dp[i-2]) i번째 집을 털거나 안 털거나 둘 중 큰 값 택하는 거.근데 이 문제는 원형이라 첫 집이랑 마지막 집이 서로..

https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약숫자랑 +, -가 섞인 배열이 주어지는데, 괄호를 어떻게 치느냐에 따라 계산 결과가 달라짐.. 가능한 모든 괄호 경우의 수 중에서 최댓값을 구하는 문제다.예를 들면 1 - 3 + 5 - 8 이거 괄호 위치 바꾸면 -15부터 1까지 결과가 막 달라짐. 이 중에 제일 큰 값 찾으면 됨. 핵심 아이디어포인트는 최댓값이랑 최솟값을 둘 다 저장해야 한다는 거.왜냐면 A - B 형태를 최대로 만들려면 A는 최대, B는 최소여야 하는데, B가 최소가 되려면 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약집에서 학교까지 가는 길이 m x n 격자로 되어있고, 오른쪽/아래쪽으로만 움직여서 집(1,1)에서 학교(m,n)까지 가는 최단경로의 개수를 구하는 문제다. 중간에 물에 잠긴 칸(puddles)은 지나갈 수 없음. 답은 1,000,000,007로 나눈 나머지.딱 보고 "어 이거 격자 탐색이네" 하면서 반사적으로 BFS 코드부터 짰다 (dp 카테고리인데 그래도 bfs도 되지 않을까 했음 ;;)시행착오 1 - BFSfrom collections ..

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약삼각형 모양으로 숫자가 배치되어 있고, 꼭대기에서 바닥까지 내려가면서 거쳐간 숫자의 합이 최대가 되는 경로를 찾는 문제다. 이동은 바로 아래 칸이 아니라 대각선으로 한 칸만 가능하다 (왼쪽 아래 또는 오른쪽 아래). 7 3 8 8 1 0 2 7 4 44 5 2 6 5이 예시에서 정답은 30이다.알고리즘 / 핵심 아이디어딱 봐도 완전탐색으로 풀면 경로 수가 지수적으로 늘어나서 큰 입력에서는 못 버틴다. 삼각형 높이가 최대 500이라 ..