알고리즘/programmers 258

[Programmers] 양과 늑대

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 비트마스킹과 백트래킹을 통해 풀 수 있는 문제였습니다. 사실 모든 가능한 상태에 대해 시뮬레이션을 진행하고 이 중 양 개수가 가장 높은 케이스를 찾는 방법이라 별도로 설명할 알고리즘은 없고 비트마스킹을 어떻게 활용할지 간단하게 설명하겠습니다. 노드 개수가 최대치인 17개라고 가정했을 때 처음 상태는 루트 노드만 방문한 상태인 00,000,000,000,000,001 루트 노드와 ..

[Programmers] 산 모양 타일링

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오 테크 홈페이지 해설집을 참고하여 푼 문제였습니다 아래 방향을 향하는 삼각형을 기준을 삼아 점화식을 세우는 DP 문제였습니다. 알고리즘은 아래와 같습니다. 1. 아래 방향을 향하는 삼각형을 채우는 방법은 아래와 같이 네 가지입니다. 위아래 모두 채우는 마름모 (1번) 일반적인 정삼각형 (2번) 자신과 왼쪽 삼각형을 채우는 마름모 (3번) 자신과 오른쪽 삼각형을 채우는 마름..

[Programmers] n + 1 카드게임

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제의 핵심은 두 개의 카드를 뽑았을 때 합이 N + 1인 경우는 각각의 카드에 대해서 하나뿐이라는 것입니다. ex) N = 10일 때 [1, 9], [2, 8], [3, 7], ... 알고리즘은 아래와 같습니다. 1. 처음에 뽑은 카드는 모두 hands에 저장하고 라운드를 진행하며 뽑은 카드들은 모두 draw에 저장합니다. 2. 라운드마다 draw에 신규 카드를 순차적으로..

[Programmers] 주사위 고르기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 순열과 이분 탐색을 통해 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. A와 B가 주사위를 나누어 가지는 모든 경우의 수를 next_permutation 메서드를 통해 구현합니다. 1.1 여기서 주의할 점은 next_permutation 사용 시 [{1, 2}, {3, 4}], [{1, 2}, {4, 3}], [{2, 1}, {3, 4}], 그리고 [{2, 1},..

[Programmers] 도넛과 막대 그래프

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr edges, a, b 모두 최대 100만이기 때문에 브루트포스로 풀기보다는 규칙을 찾아 풀어야 하는 문제였습니다. 규칙은 아래와 같습니다. 1. 모든 그래프는 생성한 정점으로부터 파생됩니다. 문제 조건에서 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다 라고 명시했으므로 해당 정점을 향하는 간선은 0개, 해당 정점으로부터 다른 정점으로 나가는 ..

[Programmers] 가장 많이 받은 선물

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258712 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr map을 이용하여 이름과 인덱스를 적절히 매핑하면 쉽게 풀 수 있는 문제였습니다. 개발환경: Programmers IDE 지적, 조언, 질문 환영합니다! 질문 남겨주세요~

[Programmers] 연속 펄스 부분 수열의 합

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 비교적 접근하기 쉬웠던 DP 문제였습니다. 알고리즘은 아래와 같습니다. 1. 펄스 수열은 1로 시작하는 경우와 -1로 시작하는 경우 두 가지입니다. 1.1 따라서 주어진 sequence에 대해 두 가지 펄스 수열을 구하고 이들의 부분 수열 합 중 최대 값을 구하면 됩니다. 2. cache[i]를 i번째 인덱스까지 탐색했을 때 최댓값을 저장하는 dp 배열로 정의했을 때 점화식은 ..

[Programmers] 표 병합

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 유니온 파인드를 이용하는 문제였으며 지문에서 주어진 대로 구현하면 되는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 우선 board 이차원 배열을 모두 "EMPTY"로 초기화하고 coord2coord key-value를 모두 각 좌표로 초기화합니다. 1.1 여기서 coord2coord가 유니온 파인드에 사용되는 map이며 key는 좌표 value는 집합의 루트 좌표입니다. ..

[Programmers] PCCE 기출문제 모음

1. [PCCE 기출문제] 1번 / 출력 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/250133 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. [PCCE 기출문제] 2번 / 피타고라스의 정리 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/250132 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세..

[Programmers] 등대

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/133500 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 노드 수는 N개이고 간선 수는 N - 1개이므로 트리를 연상할 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 우선, 리프 노드에 속하는 등대를 점등하는 것보다 해당 등대에 연결된 등대를 점등하는 것이 낫다고 그리디 하게 접근했습니다. 1.1 정리하자면 리프 노드에 속하는 등대는 점등되는 일이 없습니다. 2. 이에 따라 리프 노드를 제외한 노드들 즉, 두 개 이상 등대..