프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Lv2. 리코쳇 로봇 접근한 방법 이런 유형의 최단 거리 문제는 대부분 BFS로 해결되는데 조건이 조금 특이합니다. 한번 이동 시 벽 또는 장애물이 있을 때까지 계속 들어가야 합니다. 벽이나 장애물을 만나면 그 이전 칸에서 멈춰야 하므로 이 부분에서 이동했던 한칸을 다시 되돌려줘야 합니다. 큐와 방문여부를 담은 배열을 만들어 BFS로 해결합니다. Python은 덱 라이브러리를 사용하면 되고 JavaScript에서는 별도의 라이브러리가 없어 배열로 풀이합니다. 큐에서 row, column 정보를 담은 원소를 꺼..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1149. RGB거리 무작정 1행부터 이전 색깔을 제외하고 가장 작은 값들만 찾아 더해가면 일부 케이스에서 틀리게 됩니다. 각 행마다 나올 수 있는 비용은 총 3가지 이기 때문에 매번 3가지 경우의 비용을 모두 계산해주어야 합니다. 매 행에 들어있는 값을 빨강(R), 초록(G), 파랑(B)이라고 할 때 각 열의 누적 비용은 다음과 같습니다. 현재 행의 R의 누적 비용 = 현재 행의 R의 비용 + 이전 행의 B의 누적 비용과 G의 누적 비용중..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1912. 연속합 풀이 문제해결 아이디어는 다음과 같습니다. 1. 주어진 수열의 값들을 하나씩 순회한다. 2. 순회하는 값들을 현재값으로 축적한다. 3. 현재값이 증가할 경우 현재까지의 최댓값을 갱신한다. 4. 현재까지의 최댓값보다 더 큰 값이 발견되면 그 값을 현재값과 최댓값으로 새로 갱신한다. 처음 풀이 시 DP를 사용하지는 않았지만 문제 유형이 DP이므로 DP를 이용한 풀이방식도 함께 올립니다. 접근 방식은 동일하며 DP를 사용했을 때 코드가 더 간결하고 속도가 미세..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 14002. 가장 긴 증가하는 부분 수열4 부분 수열 1 문제와 동일한 문제이지만 여기서는 길이 뿐만 아니라 구성되는 수열을 출력해야 합니다. 가장 긴 증가하는 부분 수열 1문제에 대한 풀이는 아래에 남겨놓았습니다. [백준] 11053. 가장 긴 증가하는 부분 수열 풀이 / Python, JavaScript 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 11053. 가장 긴 증가하는 부분 수열 기본적인 문제해결 아이디어는 다음과 같습니다. 현재 수가 V수일 때, 수열의 길이는 V보다 작은 정수들 중에서 가장 긴 수열을 가진 정수의 길이 + 1이다. 예시로 주어진 입력을 봅시다. 10 20 10 30 20 50 기본적으로 수열의 값을 하나씩 순회합니다. 그리고 매 순회의 결과를 담은 것을 테이블이라고 하겠습니다. 1. 현재 수는 10이고..

11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 구현 로직 (Dynamic Programming) 구매액이 최댓값이 될 수 있는 경우는 총 3가지입니다. 예를 들면 카드 10개를 구매하고자 할 때 구매액이 될 수 있는 케이스는 다음과 같습니다. 1. 10장 짜리 카드팩 1개 구매하기 2. i개 짜리 카드팩과 10 - i개 짜리 카드팩을 구매하기 (총 10번이지만 같은 방식이므로 1개 경우로 칩니다) 3. 10이 i로 나누어 떨어지는 경우 i개 짜리 카드팩을 10을 i로 나눈 몫의 수만큼 구매하기 (수에 따라 횟수가 다..

6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 작성 코드 (.py) import sys sys.stdin = open("input.txt", "r") # 제거 input = sys.stdin.readline n = 1000001 # 소수 아닌 모든 홀수 처리 table = [1] * n for i in range(3, int(n ** 0.5) + 1, 2): if table[i]: for j in range(i * 2, n, i): table[j] = 0 # k가 만들어지는 두 홀수인..

1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 작성 코드 (.py) import sys input = sys.stdin.readline n = int(input()) formula = list(input()) s = [] table = {} for v in formula: if v.isalpha() and v not in table: table[v] = int(input()) for i, v in enumerate(formula): if v.isalpha(): formula[i] = table[v..

17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 이 문제는 오큰수 문제와 크게 다른 것은 없고 조건식만 조금 바꿔주면 동일한 문제입니다. [백준] 17298. 오큰수 풀이 / Python, JavaScript 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 작성 코드 (.py) import sys input = sys.stdin.read y..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 작성 코드 (.py) import sys input = sys.stdin.readline n = int(input()) table = list(map(int, input().split())) s = [] result = [-1 for _ in range(n)] for i in range(len(table)): while s and s[-1][0] < table[i]: v, idx = s.pop() result[idx] = table[i] else: s.append((tabl..

1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 작성 코드 (.py) import sys input = sys.stdin.readline ls, rs = list(input())[:-1], [] n = int(input()) for _ in range(n): inp = list(input().split()) op = inp[0] if op == "L": ls and rs.append(ls.pop()) elif op == "D": rs and ls.append(rs.pop()) elif op == "B": ls ..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 작성 코드 (.py) import sys input = sys.stdin.readline n = int(input()) result, s, a = [], [], 1 for _ in range(n): now = int(input()) if s and s[-1] == now: s.pop() result.append("-") else: for i in range(a, now + 1): ..