devlog

[백준] 좋다 1253번 (c++) Map

출처 : 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 가지 ..

출처 : https://www.acmicpc.net/problem/2531 풀이 방법 완전 탐색으로 풀이했다.완전 탐색으로 풀이하려면 원형 배열이기 때문에 끝에 가서 인덱스의 처리하기가 애매해질 수 있기 때문에, 배열 길이를 n+k로 설정하고, 뒤에 남은 것을 추가해 주었다. 시뮬레이션을 진행할 때, 다음 음식이 새로운 음식인지 판별하기 위해 visited배열을 두어 선택한 k개에 있는 음식인지 판별했다.다음 것을 선택하고 visited배열을 초기화하고, 제일 처음 선택한 것을 제거해 주는 방법으로 시뮬레이션을 진행했다. // ConsoleApplication3.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.//#include #include using..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법order, orders의 크기가 작으므로 완전탐색 + 조합의 문제인 것을 확인할 수 있다. 이제 조합을 어떻게 구현할지에 대해 생각을 해보아야 한다. course마다 돌아가며 모든 조합을 딕셔너리에 보관하는 방법으로 풀이했다. 여기서 중요한 점은 map의 초기값은 자동으로 0으로 할당이 된다는 것이다. 즉 combination [temp]++ 를 수행하기 위해 temp키 값이 초기화되어 있으면 +1, 초기화 되어 있지 않으면 ..

출처 : https://www.acmicpc.net/problem/20055 풀이 방법 단순 시뮬레이션 문제이다.배열의 범위만 잘 고려하면 풀이할 수 있다. (중간에 -1을 하는 과정에서 다시 시작 위치로 초기화하기, 음수가 안되게 +2n을 한 후 % 2n연산하기)문제에 한 칸에 로봇이 2개 이상 올라갈 수 없다는 조건이 없어 애매했지만, 한 칸에는 로봇이 1개만 올라갈 수 있다. 핵심 아이디어 1. 벨트 회전(rotate) • 실제로 배열을 돌리는 대신, “시작 인덱스(startIndex)”를 조정하는 방법을 쓴다. • 예: startIndex를 1 감소(startIndex = (startIndex - 1 + 2N) % (2N))시키면, 컨베이어 벨트가 시계 방향으로 한 칸 돌아간 것과 같은 효과를 낼..

출처 : https://www.acmicpc.net/problem/10775 풀이 방법처음에는 그리디한 방법으로 자신이 연결 가능한 가장 큰 게이트부터 차례대로 1씩 줄이며 가능한 곳에 연결하는 방법을 생각했지만, 이는 계산해 보니 시간초과가 난다.그러므로 다른 방법이 있어야 하는데 도저히 생각하지 못했다. 다른 사람의 풀이를 보니 유니온파인드를 사용해서 풀이하고 있었다.자신의 부모와 자신의 부모 -1한 값을 유니온 하는 방식으로 풀이하면 된다. 그러다 자신의 부모가 0이 되는 값이 발생하면 종료를 해주면 된다.  #include using namespace std;int g, p;int gate[100001];int parents[100001];int find(int a) { if (a == paren..

출처 : https://www.acmicpc.net/problem/23291풀이 방법 구현 문제이다. 각 step에 따라서 함수를 나누고 구현을 했다. 먼저 문제를 풀이하기 전에 고려해야 할 자료구조를 생각해 보자어항을 관리해야 한다. 어항에서 step을 보면, 물고기를 한 칸 올린 후 90도 또는 180도를 돌리는 과정이 있다.이를 구현하기 위해 2차원 배열을 선택했고, 90도, 180도 돌린 후 기존 어항 위에 올려놓아야 하므로 처음 시작을 y = n-1에서 시작했다. 각 step에 대해 살펴보자 step1가장 작은 물고기의 인덱스를 찾아 +1을 해주면 된다.void step1() { // 가장 작은 물고기 인덱스에 +1 해주는 함수 int min_v = 987654321; vector m..