from palette import colorful_colors

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/6248 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 언어: C++, 소요시간: 153 ms 내 혼자 힘으로 못 풀고 친구꺼 참고했다. 이걸 어떻게 생각해내는거지??? ㅠㅠㅠ 문제 핵심 집 -> 회사로 가는 경로, 회사 -> 집 가는 경로에서 공통되는 노드 개수 찾기. 집과 회사는 무조건 그래프를 타고 갈 수 있음이 보장됨. 출발 노드는 재방문이 가능하지만, 도착노드는 재방문이 불가능하다. 문제해결 모든 노드에서 방문할 수 있는 경우의 수를 확인할 수도 있지만, 그러면 시간초과난다. 따라서 dfs를 총 4번 돌리며 확인해서 해결한다. visited1. 출근길: 집에서 어딘가로 집 -> 방문할 수 있는 모든 노드를 visited1에..

https://softeer.ai/practice/6246 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 언어: C++, 시간: 05ms 격자 DFS연습하기 좋은 문제인 것 같다. (BFS로도 풀어도 된다.)맵, visited, 특정 위치의 순서를 알기 편하게 order 맵까지 만든 다음,dfs타면서 다음 순서로 이동할때마다 level+1을 해준다. #define _CRT_SECURE_NO_WARNINGS#include using namespace std;struct Node { int y; int x;};int MAP[5][5];int visited[5][5];int order[5][5];int dy[4] = { -1, 1, 0, 0 };int dx[4] = { 0, ..

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈 1. 그래프 표현 방법 - 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프 관계 표현 - 인접 리스트(Adjacency List): 리스트로 그래프 관계 표현 2. DFS 구현 # DFS 함수 정의하기 def dfs(graph, v, visited): # 1. 현재 노드 방문 처리하기. visited[v] = True print("visited node:",v) # 2. 현재 노드와 연결된 다른 노드 재귀적으로 방문하기. for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 확인용 코드 (이 밑의 코드는 없어도 무방) # 3. 모두 방문했다면 해당 dfs..