https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 순열을 이용하여 각 상품의 적용할 수 있는 할인율을 모두 구하여 완전 탐색을 통해 원하는 결과를 얻을 수 있다. 할인율 4개, 이모티콘 갯수 최대 7개로 순열의 경우의 수는 4^7로 16384개가 나오고 이렇게 나온 모든 경우의 수에 대하여 각 유저가 구매할 수 있는지 체크해야 하므로 최대 유저 100명이니까 1,678,400의 연산이 수행된다. 비교적 적은 횟수로 완전 탐색을 진행하..

https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 알고리즘이 들어가지 않은 기본적인 구현 문제라 크게 어렵진 않았을 것이다. 문자열을 분리하여 년, 월, 일을 구분하고 두 날짜의 차이를 구할 수 있다면 쉽게 해결할 수 있다. 필자는 두 날짜의 차이를 구하기 위해 일(day)로 변환하는 작업을 진행했다. 기본적으로 today가 privacy의 날짜보다 더 크다. 또한 약관 terms는 Map에 저장하여 파기해야 하는 정보인지 비교할 때..

https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 단순 그래프 문제로 bfs를 통해 depth만 구할 수 있다면 쉽게 해결 가능하다. 처음 depth를 구할 때 지역변수로 관리하면 계산이 어렵기 때문에 각 노드별로 depth를 가지도록 구현하거나 dfs의 매개변수로 구하면 훨씬 간단하게 계산할 수 있다. 코드 import java.util.ArrayList; import java.util.LinkedList; import java.ut..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이분탐색 문제라고 나와있지만 막상 문제를 접하면 어떤 값을 탐색해야 할지 감을 잡기 힘들다. 구글링 해보니 전체 시간 범위를 지정하여 이분탐색 하고 해당 시간으로 n명에게 입국심사를 진행할 수 있는지 비교해나간다. 따라서 전체 시간의 범위는 0부터 가장 대기시간이 긴 시간*n명이 되므로 해당 범위를 이분탐색을 진행한다. 값의 범위 10억으로 곱셈을 하다보면 int의 범위를 금방 벗어나기..

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 그래프 문제로 union-find를 통해 부모노드를 설정하고 각 노드마다 같은 부모인지를 체크하여 같은 네트워크인지 체크할 수 있다. 하지만 위와 같인 로직을 적용시키기 위해 부모노드로 승격시키는 로직과 각 노드마다 부모노드로 거슬러 올라가야 되는 알고리즘을 모두 구현해야 해서 불편하다 더 간단한 방법으로 각 노드마다 연결된 간선이 있으면 네트워크를 증가시키고 해당 노드와 연결된 모든 ..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제의 경우 그래프로 풀 수 있는데 평소 트리나 그래프의 경우 노드의 방문여부를 체크했다면 이 문제는 간선의 방문 여부를 체크해야 한다. 왜냐면 A->B로 가도 B->A가 있다면 A가 다시 방문될 수 있고 해당 문제에서 모든 tickets을 사용해야 하기 때문에 모든 간선을 사용해야 한다는 뜻이다. tickets을 간선으로 생각하고 visited를 tickets 갯수만큼 생성하였고 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 런타임 에러가 많이 발생해서 고생했던 문제다. 격자 행렬과 집이 m,n 순서대로 주어지지만 [n,m] 좌표임을 주의하자. 사실 위 부분에서 오류가 발생하진 않았는데 puddle도 m,n으로 주어졌다. 문제에선 2,2를 예시로 줘서 확인하지 못했다. 혹시나 했는데 확인해 보니까 m,n 순서대로 주어지기 때문에 마찬가지로 [n,m]으로 적용해야 한다. map[][]에는 각 좌표에 도착할 수..

https://school.programmers.co.kr/learn/courses/30/lessons/43105#qna 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 바텀-업 방식으로 상위 값으로 올라갈 때 어떤 하위 노드를 거쳐야 최댓값이 되는지 비교하여 큰 값을 더하여 저장한다. 따라서 마지막에 triangle[0][0]을 리턴해주기만 하면 된다. class Solution { public int solution(int[][] triangle) { for (int i=triangle.length-1;i>0;i--) { for (int j=..

https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 가장 기본적인 dfs/bfs로 문제로 이렇게 최단 거리 문제는 dfs보다 bfs 효율이 좋다. dfs는 처음 도착지점에 도착했을 때 최소 경로인지 장담하지 못한다. 하지만 bfs는 처음 도착했을 때 최단 거리를 보장하므로 찾고나서 바로 종료하면 된다. 단, 이 문제처럼 각 경로의 비용이 모두 같은 경우에서만 가능한 이론이다 코드 import java.util.*; class Node{ i..

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 dfs를 통한 완전탐색 구현 모든 numbers에 대해 조사 후 그때 값이 같으면 갯수를 증가하도록 구현 코드 class Solution { static int answer = 0; public int solution(int[] numbers, int target) { dfs(numbers, target, 0, 0); return answer; } static void dfs(int[]..