메이쁘

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net *** 정골에서 코드를 돌려보며 틀린 테스트케이스를 확인할 수 있습니다. www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2383&sca=99&sfl=wr_subject&stx=%EB%AC%BC%ED%86%B5 JUNGOL www.jungol.co.kr 안녕하세요. 난이도 골드2 의 BFS 문제 입니다. 저..

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 안녕하세요. 이 문제는 LIS 알고리즘 응용 문제로, 여러 가능한 부분 수열 중 내부합이 가장 큰 경우의 내부합을 찾는 문제입니다. 즉, 부분 수열의 값을 다 더했을 경우의 최댓값을 구하면 됩니다. 여기서는 2중 for문을 사용해서 해결했는데요. 좀 더 시간을 줄이기 위해, 하나하나 입력 받을 때 마다 배열에 저장하고, 부분 순열을 만들어나갔습니다. ..

www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 안녕하세요. 거두절미하고, 위 문제 풀이 방식은 아래 포스팅(백준 12015번 문제)과 똑같습니다. maivve.tistory.com/234 (JAVA) 백준 12015번 : 가장 긴 증가하는 부분 수열 2 --- [이분탐색, DP, LIS] www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 ..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 안녕하세요. LIS 알고리즘을 사용하는 문제입니다. (+ DP도) 그런데 더욱 시간을 줄이기 위해 이분탐색 알고리즘까지 겸비합니다. N개의 배열이 있을 때, 이분탐색 알고리즘은 시간복잡도가 O(logN) 인데요. 여기에 한 번 배열을 순회하기 때문에 총 O(NlogN) 의 시간복잡도가 생기는 매커니즘으로 해결했습니다. 만약, 2중 for문으로 수행했다면 O(N^2) 이 소모되겠죠 ? 그럼 이분탐색을 어디에 사용..

www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 모든 수를 별도로 저장해둔 다음, 파악해야 합니다. - 정확히 두 개의 수를 더해야 합니다. 1개의 수만 가지고 개수..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 안녕하세요. 플로이드 - 와샬 알고리즘을 사용하라했지만 BFS 로 접근하여 해결했습니다. 바로 매커니즘을 짚어보기 전에 유의할 부분을 체크하겠습니다. - 1개당 50미터, 최대 20개 => 즉, 한 지점에서 다른 한 지점으로 넘어갈 때 마다 최대 1000미터까지만 이동할 수 있다. - 두 좌표 사이의 거리 = x좌표 값의 차이 + y좌표 값의 차이 - 종료 조건 : 상근이네 ----> 패스티..

https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 안녕하세요. 문자열 문제로서, 저는 해시 맵을 사용해서 해결했습니다. 음.. 특별히 문제 푸는 매커니즘에 대해서는 크게 설명할 부분이 없는 것 같아요. 주의할 점은 출력할 때, 소수점 4째 자리까지 출력하는 것입니다. 백분율을 구하기 위해 각 종의 전체 개수를 별도로 파악해서 저장해놓아야 합니다. 자바에서는 간단하게 소수점 N번 째 짜리까지 출력할 수 있는데요. 바로, double pe..

https://www.acmicpc.net/problem/2224 2224번: 명제 증명 첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으� www.acmicpc.net 안녕하세요. 플로이드 - 와샬 문제입니다. 이 문제와 비슷하게 해결하면 될 것 같습니다. https://maivve.tistory.com/228 (JAVA) 백준 1613번 : 역사 --- [벨만포드] https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 ..

https://www.acmicpc.net/problem/2033 2033번: 반올림 정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고.. (� www.acmicpc.net 안녕하세요. 구현인 줄 알았다가 수학까지 하게된 문제입니다. 이 문제는 간단해서 소스코드만 참고해도 이해하실 수 있다고 생각합니다. 아! 저는 정수형으로 풀지 않고 문자형으로 변환해서 숫자 하나하나 접근하는 방식을 사용했습니다. 그런데 여기서는 시간이 더 걸리더라구요. 이렇게 접근하는 방법은 아마 정수형으로 사용할 수 없는 문자열 길이에 사용하면 적합할 것 같습니다. 그렇기 때문..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. �� www.acmicpc.net 안녕하세요. 플로이드 - 와샬 알고리즘 사용하는 문제입니다. 정답률이 낮은 이유는 쉽게 헷갈릴 수 있는 부분이 있어서 인데요. 우선, 벨만포드 알고리즘에서 중요한 for문 부분을 보시면 맨 처음 for문은 경유 지점, 다음 for문은 출발 지점, 마지막 내부 for문은 도착 지점 을 가리킵니다. 그리고, A -> B , B -> C 이면 A -> C 라는 명제같은 논리를 반영해야 합니..