꾸준한 연습장

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   풀이 각 이모티콘의 할인율을 적절하게 정하여 최대의 이모티콘 플러스 가입자를 유치하고, 그 때 최대의 이익을 출력해야 한다.  알고리즘이 필요하다기 보다는 단순무식한 구현 문제였다. 완전탐색으로 문제를 해결하려고 할 때, 제한 사항이 시간복잡도를 만족하는지 확인해보자.  이모티콘의 총 길이는 7이고 할인율은 10, 20, 30, 40 총 4개이다. 그리고 최대 유저는 100명이다. 이 때 생각할 수 있는 완전탐색 알고리즘은 다음과 같다. 존재할 수 있는 모든 할인율의 조합을 이모티콘의 길이만큼 구한다.할인율의..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   풀이 대표적인 스택 문제이다. 알고리즘은 다음과 같다. 괄호를 순회하며 다음의 규칙을 수행한다.현재 순회하는 괄호가 ( 라면 스택에 넣는다현재 순회하는 괄호가 ) 라면 다음의 규칙을 수행한다.스택에 ( 괄호가 없다면 올바르게 짝지을 수 없으므로 False를 반환한다.스택에서 ( 괄호를 꺼내 짝지어준다(없앤다)순회가 끝났다면 다음의 규칙을 수행한다.스택에 남아있는 괄호가 없다면 모든 괄호가 올바르게 짝지어진 것이므로 True를 반환한다.스택에 괄호가 남아있다면 짝을 지어주지 못한 괄호가 있는 것이므로 False..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   풀이 2 x n 의 공간이 주어질 때 2 x 1 의 타일을 놓는 경우의 수를 구해야 하는 동적 계획법 문제이다.n이 1 증가할 때 타일을 놓는 방법은 다음과 같다. dp[n]일 때의 경우에 세로로 타일을 놓는다dp[n-1]의 경우에 가로로 2칸짜리 타일을 놓는다 따라서 점화식은 dp[n] = dp[-1] + dp[-2] 이다. def solution(n): dp = [0, 1, 2] for i in range(n - len(dp) + 1): dp.append((dp[-1] + dp[-2..

3109번: 빵집유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던www.acmicpc.net 문제유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 ..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr    풀이 알파벳마다 자판 상관 없이 가장 빨리 누를 수 있는 자판을 선택하는 것이 최선의 선택일 것이다.따라서 주어진 자판을 순회하며 알파벳마다 가장 빨리 누를 수 있는 횟수를 딕셔너리에 기록한다. 이후, targets의 문자열을 순회하며 딕셔너리를 이용해 문자열을 입력할 수 있는 가장 짧은 입력 횟수를 구한다. def solution(keymap, targets): # 알파벳별 가장 빨리 입력할 수 있는 횟수 계산 d = dict() for keys in keymap: for ke..

https://www.acmicpc.net/problem/17103  문제골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. 입력첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2  출력각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.  예제 입력5 6 8 10 12 100 예제 출력1 1 2 1 6  풀이 에라토스테네스의 체로 N의 최대값 만큼 소수 목록을 구한 뒤 테스트 케이스별로 순회하며 골드바흐 파티션..

5555번: 반지 당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 www.acmicpc.net 문제 당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 거꾸로 읽는 걱정은 없다. 찾고자하는 문자열이 주어졌을 때 그 문자열을 포함하는 반지가 몇 개인지를 발견하는 프로그램을 작성하라. 입력 입력은 총 2 + N 줄 이다. 첫 번째 줄에는 1 자 이상 10 자 이하의 대문자로 구성된 찾고자 하는 문자열이 적혀있다. 두 번째 줄에는 반지..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 딕셔너리를 이용하여 주고받은 선물의 히스토리를 기록한다. 나중에 선물 지수를 계산할 때 필요하므로 자신이 선물을 몇 개 받았는지 기록하는 received 딕셔너리도 함께 기록해준다. 이후 친구 목록을 순회하며 두 사람의 선물 기록 및 선물 지수를 바탕으로 선물을 받을 개수를 계산하고 반환한다. def solution(friends, gifts): # 선물 기록을 저장할 딕셔너리 생성 history = dict() # 2depth, a = {b: 1}; a가 b에게 1개 줌 received = dict()..

2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 문제 직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다. 편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 ..

4108번: 지뢰찾기 C개의 문자들이 포함된 R개의 줄을 출력한다. 단, 모든 '.' 대신 인접한 칸에 위치한 지뢰의 수로 변경해 출력한다. '*' 칸은 그대로 출력한다. 문자 사이에 공백이나 줄 사이에 공백 줄이 있어선 www.acmicpc.net 문제 07년 개봉한 영화 '지뢰찾기'는 지뢰의 수를 조사해야하는 요원 예슬의 이야기를 다룬 영화다. 정보기관의 요원이었던 예슬은 심심해서 컴퓨터로 지뢰찾기를 켰다가 인사팀에 걸려 지뢰제거팀으로 좌천된다. 좌천된 예슬에게 처음 부여된 임무는 지뢰 제거도 아닌 지뢰 수 조사! 예슬의 첫 임무에서 교육요원으로 배정된 다민은 "처음 건 무조건 안 터져." 라고 말하며 거침없이 땅을 팠지만 지뢰가 터져 얄짤없이 사망하고 만다. 지뢰 밭에 혼자 남겨진 예슬! 과연 임무..