목록알고리즘 (83)

레벨업 일지

[Java] 백준 ABCDE

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알아야 할 개념 dfs 백트래킹 코드 dfs 탐색시 주의점을 알려준 문제 예제에 사이클 그래프가 보여서 난이도가 높은줄 알고 당황했었다. 해당 문제는 모든 정점에서 dfs 를 돌리는것으로 간단히 풀이 가능하다. 풀이는 다음과 같다. 주어진 그래프를 무방향 인접 그래프로 구현한다. 모든 정점에대해 DFS 탐색을 한다. DFS 탐색 깊이가 4 ( 시작 = 0 ) 이상이면 탐색을 종료하고 1 리턴한다. 그렇지 않으면 0 리턴한다. 백트래킹을 연습하는 문제라고 생각한다. 플래그를 세워서 dfs 탐색 종료..
알고리즘/백준 2023. 2. 17. 02:20
[Java] 프로그래머스 유전법칙

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121685 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알아야 할 개념 재귀함수 호출 dfs 풀이 재귀 함수 dfs 탐색을 주어진 조건을 고려했을때, 탐색 레벨의 최대값은 16이다. bfs로 주어진 index까지 브르투 포스 하면 4억번 이상의 연산으로 tle 를 마주하게 된다 특정 위치만 찾는법은 없을까? 라는 생각이 들었다. 풀이는 다음과 같다. 우선 주어진 조건을 재귀함수로 받는다. Level이 1이면 "Rr" 리턴. Level이 2..
알고리즘/프로그래머스 2023. 2. 16. 00:27
[Java] 프로그래머스 올바른 괄호

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알아야 할 개념 스택 풀이 링크드 리스트로 풀이하였다. (자바의 스택은 링크드 리스트의 일종이다. ) 풀이 알고리즘은 다음과 같다. 주어진 문자를 문자 배열로 바꿔서 탐색한다. 현재 문자가 ( 이면 리스트에 담는다. 현재 문자가 ) 일때 비어있는 리스트일 경우 false 리턴 탐색을 마치고 리스트가 비어있는지 여부를 리턴한다. 단순하게 , 문자를 탐색하면서, '(' 문자를 계속 추가하다가, ..
알고리즘/프로그래머스 2023. 2. 14. 00:54
[Java] 백준 15686 치킨 배달

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 알아야 할 개념 DFS 백트래킹 풀이 핵심은 치킨집을 (Math.min (M, 치킨집 개수 ) ) 만큼 뽑았을 때 도시 치킨 거리의 수를 모두 구하면 되는 문제. 나이브한 브루트포스 풀이 알고리즘은 다음과 같다. 일정 개수 (min(주어진 M, 치킨집 개수 )) 만큼 치킨집을 뽑는다. 모든 집의 치킨 거리를 계산한다. 도시 치킨 거리를 계산한다. 알고리즘 (1,2,3) ..
알고리즘/백준 2023. 2. 14. 00:37
[Java] leetcode 1523. Count Odd Numbers in an Interval Range

문제 https://leetcode.com/problems/count-odd-numbers-in-an-interval-range/description/ Count Odd Numbers in an Interval Range - LeetCode Can you solve this real interview question? Count Odd Numbers in an Interval Range - Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive). Example 1: Input: low = 3, high = 7 Output: 3 Explanati leetcode.c..
알고리즘/leetcode 2023. 2. 13. 23:04
[Java] leetcode 1626. Best Team With No Conflicts

문제 https://leetcode.com/problems/best-team-with-no-conflicts/description/ Best Team With No Conflicts - LeetCode Can you solve this real interview question? Best Team With No Conflicts - You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum of scores of all t leetcode.com 알아야 할 개념 DFS + ..
알고리즘/leetcode 2023. 2. 12. 23:54
[Java] 프로그래머스 이모티콘 할인

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=java# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최적화를 해서 풀까? 싶다가 나이브하게 brute force로 충분히 패스 가능한 시간복잡도를 가졌다. 로직은 다음과 같다. dfs 재귀 탐색으로 완탐한다. 각 레벨마다 4가지 할인율의 정보를 disInfo 배열에 담는다. 리프 노드에서 조건에 따른 사용자의 경우의 수를 따져 list에 추가한다. 모든 경우의 수 ( 가입자 수 , 판매액 ) 를 담은 배열을 ..
알고리즘/프로그래머스 2023. 2. 8. 23:09
[Java] 백준 2839. 설탕 배달

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 알아야 할 개념 다이나믹 프로그래밍 풀이 풀이는 다음과 같다. dp 배열을 하나 만들고 최대 값 10001로 채운다. dp 배열에 (idx == 3의 배수)를 3으로 나눈 몫으로 채운다. dp 배열을 순회 하면서, dp[i-5] (이전에 최소값 봉지의 개수) + 1 , dp[i] (현재 개수 ) 두 값의 최솟값으로 업데이트한다. dp[ 주어진 숫자 ] 를 리턴한다. 참고 dp[i-5] + 1 을 한 이..
알고리즘/백준 2023. 2. 3. 00:17
이전 Prev 1 ··· 3 4 5 6 7 8 9 ··· 11 Next 다음