본문 바로가기

Algorithm

 (55)
[Programmers] 모두 0으로 만들기 안녕하세요. 이번 포스팅에서는 프로그래머스 모두 0으로 만들기라는 문제를 풀어보도록 하겠습니다. 해당 문제는 https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 위 링크에서 확인하실 수 있습니다. 이 문제를 해결하는데, 중요한 키는 트리 구조라는 것입니다. root를 아무 노드나 설정하셔서, 트리를 탐색하시면서 문제의 요구사항을 구현하는 것이 중요합니다. 예시를 자세히 보시면, 결국 루트로부터 ..
[BeakJoon 19942] 다이어트 안녕하세요. 오늘은 백준 19942 다이어트 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 저는 다음의 알고리즘으로 이 문제를 해결하였습니다. 1. 각 함수마다 두 개의 재귀 함수를 호출하였습니다. 해당 idx의 item을 선택한 경우, 선택하지 않은 경우를 나누어 호출하였습니다. 2. idx가 n까지 진행되었다면, 다음 두 가지의 경우로 결과를 초기화 해 주었습..
[BeakJoon 17471] 게리맨더링 안녕하세요. 오늘은 백준 17471 게리맨더링 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 저는 다음과 같은 순서로 이 문제를 해결하였습니다. 1. 정해진 N의 개수만큼 두 집단으로 분리 2. 분리되었다면 각각 연결되어 있는지 확인 3. 올바르게 분리 되었다면, 결과 갱신 1을 위해 저는 각 함수마다 두 개의 재귀 함수를 호출하여 주었습니다. 각각 group을 A, B라 한다면 현재 ..
[Programmers] 튜플 안녕하세요. 이번 포스팅에서는 Programmers 튜플 문제를 해결해보도록 하겠습니다. 해당 문제는 https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 위 링크에서 확인하실 수 있습니다. 문자열 단순 구현 문제입니다. 문제의 요구조건을 다음의 과정을 통해 해결하였습니다. "{{1,2,3},{2,1},{1,2,4,3},{2}}" 이러한 입력이 주어졌을 때 두 번..
[Programmers] 위클리 챌린지 7 안녕하세요. 이번 포스팅에서는 위클리 챌린지 7 입실 퇴실에 대한 포스팅을 진행해 보겠습니다. https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 해당 문제는 위 링크에서 확인하실 수 있습니다. 생각보다 처음 조건을 찾는 것에 애를 먹은 문제입니다. enter : [1, 3, 2] leave : [1, 2, 3] 위의 예시를 한번 살펴보면, 3이 2보다 먼저 들어왔고, 2보다 늦게 나갔기 때문에 2와 3은 필연적으..
[Programmers] 보석 쇼핑 안녕하세요. 이번 포스팅에서는 프로그래머스 보석 쇼핑이라는 문제를 풀어보도록 하겠습니다. https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 해당 문제는 투 포인터 알고리즘으로 해결하시면 됩니다. 우선 Set과 Map을 하나씩 각각 만들어 주고, 처음에 Set에 보석의 종류를 다 담아놓습니다. ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 라면 DIA, RUBY, EMERALD, SAPP..
[BeakJoon 2293] 동전 1 안녕하세요. 이번 포스팅에서는 저번 포스팅에 이어 동전 1을 풀어보도록 하겠습니다. (저번 포스팅) https://chanho0912.tistory.com/78?category=870985 [BeakJoon 2204] 동전 2 안녕하세요. 이번 포스팅에서는 백준 2204 동전 2 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,.. chanho0912.tistory.com 이번에 풀어 볼 문제는 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k..
[BeakJoon 2204] 동전 2 안녕하세요. 이번 포스팅에서는 백준 2204 동전 2 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 동전의 조합을 사용하여 만들 수 있는 가치의 최솟값을 묻는 문제입니다. 이러한 류의 문제는 보통 Dynamic Programming으로 접근이 가능합니다. 2중 루프를 돌며, 첫 번째 루프에서는 동전의 가치를 두 번째 루프에서는 0부터 ..

티스토리툴바