📚 알고리즘
[백준 2156 ] 포도주 시식 (Java) - 실버1
# 문제 2156번: 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net # 접근법 구하는것 마실 수 있는 Max의 포도주 양 조건 연속으로 3잔은 못먹음 ← 얘 때문에 애먹음 포도주 잔의 갯수의 범위는 1 ≤ n ≤ 10,000 임 ← 즉, 음의 정수는 X 포도주의 양은 순서대로 주어진다(순서 바꾸지 못함) DP문제임을 알고 접근했지만, 3개 연속으로 먹지 못한다는 것을 어떻게 해결하면 좋을지 고민을 많이했음. 일단 Top-down 방식으로 푼 블로그도 있던데, 재귀함수로는....지금 내 머리로는 도..
[백준 1717] 집합의 표현_union-find(c++)
[문제] https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net [문제풀이] n개의 수와 m개의 연산을 입력으로 받는다 m개의 줄에는 각각의 연산이 주어지는에 첫번째 숫자가 0 이면 union연산을 첫번째 숫자가 1이면 find연산을 하면된다 find연산을 할때, 두개의 숫자가 같은 부모노드를 가지고 있다면 YES를 아니라면 NO를 출력하면 된다 [전체코드] #include #include using namespa..
[백준 1976] 여행가자_union_find(C++)
유니온 파인드란? 그래프 알고리즘의 일종이다. 여러 노드가 존재할 때, 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은집합에 있는지 확인하는 알고리즘이다. 또한 여러 노드가 존재할 때, 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 있는지의 여부를 판별하는 알고리즘. find 연산 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 Union 연산 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 서로소 집합(disjoint Set)그리고 병합 찾기 집합(merge find set) 이라 고도 불리며 여러 서로소 집합의 정보를 저장하고 있는 자료구조 참고사이트 : https://brenden.tistory.com/33 [문제] https://www.acm..
[백준 16120] PPAP(c++)
[문제] https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net P는 PPAP이다 PPAP는 PPAP다 P(PPAP)AP 는 PPAP다 PPA(PPAP)는 PPAP다 PP는 NP다. 왜냐하면 PP중 하나를 PPAP문자열로 바꾸면 PPAPP가 되기때문에 이는 PPAP에 해당하지 않는다 ⇒ 입력으로 받은 문자열이 PPAP문자열이면 PPAP를 아니라면NP를 출력 [문제풀이] 처음에는 JAVA가지고 정규식으로 풀려고 노력했지만...틀렸습니다와 시간초과의 향연.. 결국 그냥 다른 방법으로 풀기로했다 문자열로 받..
[백준 12015] 가장 긴 증가하는 부분 수열_이분탐색(C++)
[문제] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열이 주어졌을때 가장 긴 증가하는 부분 수열 구하라 그것의 길이를 출력! [나의 문제 접근] 이미 이거슨....dp와 관련된 문제라는 것을 알고있다!! 하지만 어떻게 했더라...기억이 안난다 두달전쯤에 풀었던것으로 기억.. 일단 기억을 더듬어 똑같이 만들어 보기로 했다 10 20 10 30 20 50 👆🏻 dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] {10} / 1(..