어흥

문제 링크: https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 1. 주의할 점 - 자식이 많은 부모의 경우, Leaf를 찍고 돌아왔을 때 다음 Node가 자신의 자식인지 어떻게 판별할 것인가? - 브루트포스는 절대로 하지 않는다 (하면 안되는거 알잖아요..) - TLE를 어떤 방식으로 해결할 것인가? 2. 구현 - 제목 그대로 DFS로 접근한다 - 모든 간선에 대한 정보는 Li[] 리스트 배열에 담는다 - Ar..

문제 링크: https://www.acmicpc.net/problem/15997 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번 www.acmicpc.net 1. 주의할 점 - 브루트포스를 통해 구하지만, 3^6 전부를 돌리지 않아도 된다 - 독립 사건 → 확률을 곱하면서 진행 2. 구현 - Map을 통해 각 문자열에 매칭되는 번호를 저장한다 - Matches[idx]를 통해 idx번째 경기에 누가 참가하는지 저장핟나 - WinRate[idx][]를 통해 idx번째 경기의 승무패 확률을 저장한다 - DFS를 수행하여 최대 6번의 경기를 치..

문제 링크: https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 1. 주의할 점 - 전체 학생에 대해 DFS를 돌리지 않도록 한다 2. 구현 - Arr[][] 배열을 통해 학생간 친구관계를 저장한다 - 각 학생에 대해 친구가 N-1명 이상인 경우에만 DFS를 수행하도록 하기 위해 Avail에 친구가 N-1명 이상인 학생만 담는다 - DFS()를 통해 N명을 골랐을때 모두 친구면 Fin을 True로 설정하여 더 이상 검사하지 않도록 한다 - 만족하는 경우..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 1. 주의할 점 - 사이클 여부를 판단해야 한다 - 4방향 탐색을 거친다 2. 구현 - Check[y][x][dir] 배열을 통해 각 (y,x)에 dir방향에서 들어온 적이 있는지 확인한다 - Check[][][] 값이 false면 Dfs()를 통해 해당 지점과 방향에서 시작하여 만드는 사이클을 구한다 - Dfs() 내부..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 1. 주의할 점 - 최소 피로도 ≥ 소모 피로도 2. 구현 - 최소 피로도를 needEnergy[] 배열에 담는다 - 소모 피로도를 useEnergy[] 배열에 담는다 - check[] 배열을 통해 던전 탐험 유무를 체크한다 - DFS()를 수행하며 남은 피로도가 최소 피로도 이상이며, 탐험하지 않은 던전인 경우, 탐험을 한다 #include..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 11주차 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 1. 주의할 점 - 직사각형을 어떤 방식으로 표현할 것인가? - 좌표를 어떻게 나타낼 것인가? - 경계를 어떻게 찾을것인가? 2. 구현 - 직사각형을 Arr[][] 배열에 담으며, 경계뿐만 아니라 내부도 1로 채워넣는다. 이때, 좌표를 표현해야하기 때문에 가로 세로를 2..

문제 링크: https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 1. 주의할 점 - 트리 탐색시 방문 검사를 하지 않으면 TLE가 날 수 있다 2. 구현 - 간선에 대한 정보를 Li[] 배열에 담는다 - Root부터 idx Node까지의 거리를 Dist[idx]에 저장한다 - 트리 탐색을 하며, Leaf Node인 경우, Sum에 Dist[] 값을 추가한다 - 성원이가 게임을 이기기 위해서는 홀수번째 움직임에 게임이 끝나야 한다. 즉, Leaf N..

문제 링크: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=540 Softeer 제한시간 : C/C++(1초), Java/Python(2초) | 메모리 제한 : 256MB 자율주행 기술의 발전과 함께 차량 내 인포테인먼트 기술 또한 많은 주목을 받고 있다. 최근 자동차 실내에는 디스플레이의 대형화를 비 softeer.ai 1. 주의할 점 - 시뮬레이션을 통해 구현한다 - 최대한 최적화를 진행해야 겨우 통과한다 - 같은 색의 차량 1대도 사라질 수 있다 2. 구현 - 3번의 DFS() 함수를 수행한다 - DFS() 함수내에는 다음과 같은 기능을 순차적으로 수행한다 - 현재 차량의 상태를 나타내는 Arr[][] 배열을 Dup[][] 배열에 저장한다 ..