from palette import colorful_colors

https://www.acmicpc.net/problem/20920 언어: C++, 시간: 160ms 💡문제 아이디어Hash와 PQ에서의 구조체 정렬을 연습하기 좋은 문제.Hash를 이용해 시간복잡도를 O(1)로 빈도수를 저장하고, PQ와 구조체를 이용해 문제의 조건으로 정렬한다. 💡문제 코드#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include using namespace std;// pq에 사용할 구조체struct word{ int wordFreq; int wordLen; string wordName;};// pq용 정렬 구조체 - 1. 빈도 내림차순, 2. 길이 내림차순, 3.ASCHII오름차순struct compa..

https://www.acmicpc.net/problem/1707  💡문제 아이디어이분그래프 판별 문제.같은 그룹(색깔)끼리는 이어져 있으면 안된다.탐색하면서 빈 노드가 있으면 다른 색깔로 칠하고, 같은 색깔이었으면 이분그래프 조건이 아니므로 0을 return한다   💡문제 코드// 백준 1707 이분 그래프#define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std;int K, V, E;vector alis[20001];int visited[20001];// 테스트케이스 전 그래프 초기화void init() { memset(alis, 0, sizeof(alis)); memset(visited, 0, sizeof(visi..

접근방법1. 조합짜기먼저 주사위 중 A가 굴릴 주사위를 정할 조합을 짠다. 그러면 B가 굴릴 주사위도 자동으로 정해진다.A가 선택한 주사위는 aSelected가 1이고, B가 선택한 주사위는 aSelected가 0이다.  → 재귀 이용, makePath 함수 2. 해당 조합마다 굴리는 경우 구하기A가 굴리는 주사위의 합, B가 굴리는 주사위 합만 알면 되므로, (6^N) 이 아닌 (6^N/2) 를 두 번 구해주면 된다.굴리는 주사위의 합들을 각각의 DAT에 저장하고, 나중에 비교를 위해 합이 나오는 경우의 수를 aCase, bCase에 저장한다. →   재귀 이용, roll함수 3. 해당 조합에서 A가 이기는 경우의 수 구하기 비교시 시간복잡도를 줄이기 위해 aCase, bCase를 오름차순 정렬, 중복..

https://softeer.ai/practice/6252 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai언어: C++, 시간: 36ms 접근방법N이 크기 때문에 시간 최적화가 필요하다. 난 이진탐색의 업그레이드 버전인 Parametric search(매개변수 탐색)을 이용했다. 1. 문제에서 가능한 정답의 범위(최선의 최소 컴퓨팅 성능):  성능이 가장 낮은 컴퓨터 ~ 성능이 가장 높은 컴퓨터 + B의 루트 값 2. 최선의 최소 컴퓨팅 성능이 num일 때 예산 안에서 업그레이드가 가능한지 판별하는 함수 isPossible을 만들어준다!이후 가능한 정답 범위에서 이진탐색을 한다! → isPossible이 true면 start = mid + 1, false면 end = mid -1로 ..

https://www.acmicpc.net/problem/1149언어: C++, 시간: 0ms 접근방법대표적인 dp를 이용하는 문제. 먼저 입력을 행이 N이고 열이 3인 맵에 담고 난 후, 0행부터 N-1행까지 dp로 최솟값의 합을 저장한다: i 번째 행의 R칸에는 i-1번째의 G칸과 B칸 중 min을 저장한다.i 번째 행의 G칸에는 i-1번째의 R칸과 B칸 중 min을 저장한다.i 번째 행의 R칸에는 i-1번째의 R칸과 G칸 중 min을 저장한다....이런식으로 저장하게 되면, i번째 행의 각 열에는 i번째 집에 해당 색깔로 색칠했을때 + 그 이전 행들에 색칠하는 총 최소 비용이 저장된다.dp를 다 구하고 난 후, 정답은 N-1 행의 각 열에 담긴 숫자 중 최솟값이다. 1000 x 1000은 int 범..

https://www.acmicpc.net/problem/1715언어: C++, 시간: 36ms 접근방법정렬을 계속 반복하는 그리디 문제!가장 작은 숫자가 top에 오는 pq를 만들고 난 후,숫자들 중 가장 작은 숫자와 그 다음 숫자를 더하고, 이걸 정답 변수에 더해주고 난 후 다시 pq에 넣는다. ....→  이걸 pq 크기가 1이 될 때까지 반복하기 고려사항이 문제는 모두 int로 풀이해도 된다.문제에서 N은 10만, 카드묶음의 최대 숫자는 1000인데,정답 변수에는 1000x10만 + 2000x5만 + 4000x2만5천 + 8000x만2500, ... 이런식으로 1억이 계속 더해진다.이 때 log100000 = 16.609... 이므로, 1억이 16.609... 번 더해지는 셈이다.약 16.6억  ..

https://www.codetree.ai/training-field/frequent-problems/problems/artistry/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 언어: C++, 소요시간: 10ms 접근방법 그룹별 인접한 변의 개수를 찾기 위해 bfs(flood fill)을 2번 돌렸다. 첫 번째 bfs: 각 그룹의 시작 좌표(y, x), 그룹넘버를 groupMAP에 저장, 각 그룹별 칸의 개수 파악 두 번째 bfs: 각 그룹마다 인접한 그룹의 개수, 즉 변의 개수를 adjac..

https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 언어: C++, 소요시간: 18ms 접근방법 최근 삼성 기출의 구현문제는, 맵에 적은것과 별개로 또다른 리스트를 만들어서 접근하는 문제 스타일이 출제되고 있다. 쌓여가는 골렘을 표시하는 MAP 배열과 별개로, 골렘의 번호만 알면 바로 골렘의 중심위치, 출구위치, 출구방향을 알 수 있는 ..