devlog

[백준] 성냥개비 3687번 (java)

출처 : https://www.acmicpc.net/problem/3687풀이 방법각 수를 만드는데 필요한 성냥개비의 수를 알아보자1 = 2개2 = 5개3 = 5개4 = 4개5 = 5개6 = 6개7 = 3개8 = 7개9 = 6개0 = 6개 가장 큰 수를 만드는 것은 가장 자릿수가 많아야 한다.가장 자리수가 많기 위해선 가장 작게 성냥개비를 사용할 수 있는 수를 최대한 많이 추가해야 하는데필요한 성냥의 수를 보면 너무 좋게 2개를 사용해서 1, 3개를 사용해서 7을 만들 수 있어 그리디 하게 풀방법을 생각해 낼 수 있었다.만약 주어진 성냥개비수가 홀수이면 맨 앞을 7로 나머지 뒤는 모두 1로, 반대로 짝수이면 모든 수를 1로 채워 넣으면 가장 큰 자릿수를 만들 수 있고 이것이 가장 큰 수가 된다. 가장 작..

[백준] 횡단보도 24042번 (java)

출처 : https://www.acmicpc.net/problem/24042 풀이 방법주기마다 횡단보도의 신호가 들어온다는 것이 신기했던 문제이다. 현재 위치에서 이동할 수 있는 지역을 계산해 주기 위해 현재 위치에 해당하는 신호가 언제 들어오는지 시간을 체크해 주어야 한다.이를 시간적으로 빠르게 해 주기 위해 그래프의 인접 리스트에 저장할 때 불이 들어오는 시간도 저장해 주었다. (아니면 M시간을 계속 순회해야 함) 그리고 최단 시간 안에 이동해야 하므로 bfs와 우선순위 큐를 사용해서 가장 시간이 적은 것부터 방문해서 처리해 주었다. 다음 노드로 가기 위해 시간계산은 만약 (현재 시간 % m ) 보다 이동할 신호의 시간이 크다면 다음 시간을 cur.time + (next.time - (cur.time..

[백준] 로봇 조정하기 2169번 (c++) 3차원 dp

출처 : https://www.acmicpc.net/problem/2169 풀이 방법해당 문제에서 다른 dp문제와 다르게 고려해야 할 점은 음수 값을 가지는 칸이 있다는 것과 최단 거리가 아니라 가치의 합이 최대이기 때문에 빙 둘러서 오는 것이 답이 될 수 있다는 점이다. 우선 빙 둘러서 오는 것이 답이 될 수 도 있는데 여기서 고려해야 할 점은 한 번 방문한 점은 다시 방문하면 안 된다는 것이다.그렇기 때문에 backtracking을 사용해야함을 알 수 있다. 또한 같은 위치라도 어느 방향에서 오느냐에 따라 해당 위치에서의 최대 값이 달라지므로 3차원 dp를 사용해서 [y][x][dir] 즉 y, x를 dir 방향으로 방문했을 때 최대 값으로 메모리제이션을 했다. 여기서 음수 값이 존재하기 때문에 dp..

출처 : https://www.acmicpc.net/problem/1941 풀이 방법해당 문제를 보고 완전 탐색 문제인 것을 확인했다. 처음엔 단순히 dfs, bfs를 통해 임도연 파가 3명이 넘어가면 중단하며 인접한 7명의 사람을 선택하는 방법으로 풀이할까 했지만, 이렇게 한다면 아래 이미지와 같은 케이스는 탐색하지 못한다. 그렇기 때문에 각 위치의 인덱스를 이용해서 7명을 뽑고, 7명 중 임도연파 수를 세고, 인접한 지 검사하는 방법으로 완전탐색을 수행해야 한다.인덱스는 0부터 24까지 두었고 y좌표를 인덱스 / 5, x좌표를 인덱스 % 5로 설정해서 y, x좌표를 구했다.여기서 visited배열은 선택된 사람 adjVisited는 인접 검사를 진행하기 위한 bfs 수행 시 방문 여부이다. 7명 구하..

출처 : https://www.acmicpc.net/problem/1943 풀이 방법 이 문제는 냅색 문제 유형에 속한다. 주어진 동전의 종류와 각 동전의 개수를 사용해 두 사람이 같은 금액을 만들 수 있는지 확인해야 한다. 이를 해결하기 위해 DP(동적 계획법)을 사용한다.  1. 총금액 확인 • 먼저 주어진 모든 동전의 금액을 계산하여 총합 sum을 구한다. • 만약 총금액이 홀수라면 두 사람이 같은 금액을 가질 수 없으므로, 바로 0을 출력한다. 이는 두 사람이 나눠가질 금액이 정확히 sum / 2가 되어야 하기 때문이다. 한 사람이 sum/2 금액을 만들 수 있으면 나머지 사람은 남은 돈을 다 가져가면 sum/2가 되므로 자연스럽게 문제가 해결된다. 그러므로 sum/2를 구하는 경우만 생각하면 된..

출처 : https://www.acmicpc.net/problem/1253풀이 방법문제의 설명이 모호해서 시간이 들었다.헷갈린 부분 명확하게 정리같은 수가 입력으로 여러 개 들어올 수 있다.같은 수의 위치가 다르면 좋은 수를 카운팅 할 때 같은 수만큼 추가해 주어야 한다.음수가 들어올 수 있다.0이 들어올 때 주의해야 한다.Map을 이용해서 두 수의 합이 입력으로 들어온 수인지, 입력으로 해당 수가 몇 개 있는지 확인해서 answer에 더해주었다.또한 한 번 좋은 수로 선택된 수를 중복으로 더하지 않기 위해 더해진 수의 Map값을 0으로 설정했다. #include #include #include #include using namespace std;vector numbers;map frequency;int..

출처 : https://www.acmicpc.net/problem/5972풀이 방법평범한 다익스트라로 풀이 했다. #include #include #include #include using namespace std;int n, m;vector > > graph;int visited[50001];int cost[50001];const int INF = 987654321;struct Node { int idx; int distance; Node (int idx, int distance): idx(idx), distance(distance) {} bool operator n.distance) return true; else return false; }};void di..

출처 : https://www.acmicpc.net/problem/14658 풀이 방법 완전 탐색의 기본 아이디어 • 이 문제는 완전 탐색으로 해결해야 한다. • 다만, 보드를 전체적으로 탐색하면 시간 초과가 발생하므로 별똥별 좌표를 기준으로 탐색을 진행한다.  사각형(트램펄린) 위치 설정 시 주의점 • 별똥별을 기준으로 탐색하더라도, 어떻게 트램펄린 사각형을 위치시키는지가 핵심이다. • 특정 별똥별을 사각형의 꼭짓점에만 맞추는 방식으로는 최적해를 놓칠 수 있음을 주의한다.  그러므로 위의 예시에서도 힌트가 되었지만, 정답은 최소 2점이 각 변이나 꼭짓점에 있는 경우가 정답이 된다.이게 왜 그런지 증명을 해보도록 하겠다.예를 아래와 같이 점 세개가 트램펄린 안에 있는 경우 아래와 같은 사각형도 정답이 될..

출처 : https://www.acmicpc.net/problem/22866 풀이 방법접근 방식 1. 완전 탐색: • 모든 건물을 순회하며 비교하는 방식은 시간 초과가 발생한다. • 시간 복잡도:  O(n^2)  2. DP(동적 프로그래밍) 접근 시도: • 오른쪽에서 자신보다 크면서 가장 가까운 건물을 선택하여 해당 건물이 볼 수 있는 건물을 자신도 볼 수 있게 한다. • 하지만, 건물 높이가 계속 감소하는 최악의 경우에는 여전히  O(n^2) 이 되어 효율적이지 않다.효율적인 풀이 방식 스택(Stack)을 사용하여 두 번의 순회로 문제를 해결한다. • 왼쪽 → 오른쪽 순회 • 오른쪽 → 왼쪽 순회 두 과정은 동일하므로 왼쪽 → 오른쪽 순회 과정을 살펴보자 알고리즘 동작 방식 1. 스택이 비어있지 않고,..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법문제 핵심 요약 1. 4가지 조건(언어, 직군, 경력, 음식)에 대해 각각 세부 조건이 존재한다. 2. 각 조건은 ‘-’(상관없음)이라는 wildcard로 대체될 수도 있다. 3. 주어진 조건(혹은 wildcard)을 모두 만족하는 지원자들 중, 점수가 특정 기준값 이상인 지원자의 수를 빠르게 구해야 한다. 해결 전략 1. 모든 조건 조합에 대한 점수 저장 • 4가지 조건 각각에 -이 들어갈 수 있으므로, 2^4 = 16 가지 ..