어흥

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1837?language=java 코딩테스트 연습 - GPS edge_list [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] programmers.co.kr 1. 주의할 점 - BFS/DFS로 시도하면 TLE 혹은 '틀렸습니다'라는 문구가 출력된다 - DP로 접근한다 2. 구현 - 단순하게 그래프 문제라고 생각하고 DFS/BFS로 접근했다가 TLE와 '틀렸습니다'의 연속..(다만 이때, 1개의 채점에 여러개의 TC가 존재하여 1개라도 TLE 또는 메모리초과 발생시 틀렸습니다로 나타난다는 사람들의 의견이 존..

문제 링크: 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://www.acmicpc.net/problem/9007 9007번: 카누 선수 이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그 www.acmicpc.net 1. 주의할 점 - 시간복잡도를 줄이려고 노력한다 - TestCase를 시작하기 전, 연산에 사용되는 모든 벡터 및 값을 초기화한다 2. 구현 - 4개의 집합(V[])을 2개씩 묶어서 각 집합의 모든 원소의 합을 twoSum[]에 저장한다 - 두 집합의 합을 구할때: O(N^2) - twoSum을 통해 Weight과 비교할 때(twoSum[0]의 길이를 A(=N^..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42898?language=cpp# 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 1. 주의할 점 - 1열과 1행 전부가 도달 가능하지 않을 수 있다 - 연산 이후 값을 저장할 때 MOD를 활용한다 2. 구현 - Arr[M][N] 배열에 (M,N)까지 도착 가능한 방법의 수를 MOD로 나눈 값을 저장한다 - Set을 이용하여 웅덩이의 위치를 저장한다 - [1,1]에 시작하여 1열과 1행에 1을 ..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 1. 주의할 점 - 스택을 활용하여 해결한다 - 짝지어 제거한 이후, 문자열을 새로 저장할 필요가 없다 2. 구현 - 문자열을 전부 비교하며, 스택이 빈 경우에는 문자를 그대로 넣는다 - 만약 스택이 비지 않았다면, 스택의 Top과 현재 문자를 비교하여 같으면 Pop, 다르면 Push를 수행한다 - 모든 문자열에 대해 검사를 한 후, 스..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42584?language=cpp 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 1. 주의할 점 - Stack을 이용하여 해결한다 2. 구현 - Stack에 Prices의 인덱스를 담는 방식으로 진행한다 - Stack의 Top의 원소에 해당하는 Prices보다 현재 Prices(val)가 크거나 같으면 Stack에 추가한다 - 아니라면 Stack의 원소를 뽑아내여 ..

문제 링크: https://www.acmicpc.net/problem/3107 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 1. 주의할 점 - : 를 기준으로 어떻게 나눌것인가 - ::를 어떻게 처리할 것인가 2. 구현 - C++의 경우에는 sstream을 통해, Java의 경우에는 split을 통해 세미콜론을 처리했다. 다만, Java의 경우 끝에 ::가 있을 때 처리를 못해서 추가 코딩이 필요하다 - 세미콜론을 기준으로 문자열을 잘랐을 때, 해당 문자의 길이에 따라 조건을 처리하고 V 벡터 or Li 리스트에 추가한다 - 길이가 4면 그대로..