전체 글
-
[백준 16472] 고냥이 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 5. 00:53
www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제풀이 N, S : 입력값 check : 알파벳 개수 left, right : 투 포인터 tmp : 인식한 문자 개수 q : 현재 인식한 문자열 투 포인터(Two-Pointer) 를 이용하여 새로 인식한 글자와 문자열의 길이를 계산해 문자열의 최대 길이를 구할 수 있다. 1. 투 포인터를 이용해 왼쪽부터 오른쪽 방향으로 하나씩 글자를 인식한다. - 인식한 문자 개수(tmp) 가 N 인데, 새로운 글자가 나타나면 ans..
-
[백준 2208] 보석 줍기 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2021. 1. 4. 23:39
www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1≤N≤100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득을 www.acmicpc.net 문제풀이 N, M, arr : 입력값 prefix_sum : 구간합 단순하면서도 어려운 구간 합(Prefix Sum) 문제였다. 머리로는 이해가 되는데, 설명하기가 굉장히 어려운 풀이이다.. 조금 더 풀이 해설 보완이 필요할 것 같다.. ㅠㅠ 1. arr 입력을 받으면서 구간 합을 구한다. 2. 인덱스 M - 1 부터 N 까지 최소 구간합을 구하고, 최소 구간합을 뺴주면서 최대 구간합을 구한다. - 인덱스..
-
[백준 5557] 1학년 (Python)Algorithm & Problem Solving/다이나믹 프로그래밍(Dynamic Programming) 2020. 12. 30. 18:22
www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제풀이 N, arr : 입력값 dp : 특정 인덱스에서 현재까지의 수가 나올 수 있는 경우의 수 => dp[idx번째][현재까지의 수] = 가능한 경우의 수 전형적인 다이나믹 프로그래밍 문제이다. N제한이 100인데, 처음에 이걸 안보고 그냥 재귀 프루트포스로 풀려했다가 바로 시간초과를 받았다.. ㅠㅠ 문제 꼼꼼히 보도록 해야한다..! 이 문제의 핵심은 가능한 수가 0이상 20이하 라는 것이다. 이를 ..
-
[백준 15565] 귀여운 라이언 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 30. 16:11
www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 문제풀이 N, K, arr : 입력값 left, right : 투 포인터 q : 집합을 담는 deque cnt : 1의 개수 ans : 1이 K개 일때의 집합의 최소 길이 기초 투 포인터(Two-Pointer) 문제였다. 쉬운 문제였는데, 처음에 left, right 만으로 집합의 길이 계산하려다가 계속 에러나서 문제 푸는데 오래걸려서, 그냥 deque 사용해서 해결하였다. 이 정도의 문제는 정말 빠르게 ..
-
[백준 14921] 용액 합성하기 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 30. 14:52
www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당 www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 ans : 결과값 입력 배열이 정렬되어 있기 때문에 따로 정렬이 필요하지 않고, 곧바로 투 포인터(Two-Pointer)를 진행해서 탐색하면 쉽게 해결할 수 있다. 1. left, right 를 통해 배열의 양쪽 끝에서부터 각 원소를 더해가며(tmp) 최소값을 찾는다. - tmp의 값이 음수이면 절대값을 줄이기 위해 ..
-
[백준 2842] 집배원 한상덕 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 29. 22:00
www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 문제풀이 N : 입력값 board : 입력값(마을을 나타내는 행렬) tiredness : 입력값(지역의 고도) houses : 전체 K의 개수 fatigue : 중복 제거 후 정렬된 tiredness left, right : 투 포인터 ans : 결과값(가장 작은 피로도) BFS와 투 포인터(Two-Pointer) 를 결합한 문제이다. 굉장히 까다롭고 어려운 문제라고 생각한다... 핵심은 입력..
-
[백준 1484] 다이어트 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 29. 18:02
www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 문제풀이 G : 입력값 P : 현재 몸무게 Q : 성원이가 기억하고 있던 몸무게 left, right : 투 포인터 변수 ans : 결과값 (가능한 현재 몸무게를 담고 있는 리스트) 처음에 투 포인터 탐색을 위한 제한(N, M) 을 1000으로 해서 틀렸습니다를 받았다. 이후 G 가 99999 일때 50000^2 - 49999^2 = 99999 이 가능하다는 것을 알게 되었고, N, M 을 100000 까지 늘렸더니 ..
-
[백준 14746] Closest Pair (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 29. 16:37
www.acmicpc.net/problem/14746 14746번: Closest Pair Your program is to read from standard input. The input consists of four lines. The first line contains two integers, n (1 ≤ n ≤ 500,000) and m (1 ≤ m ≤ 500,000), where n is the number of points in set P and m is the number of points in set Q. In th www.acmicpc.net 문제풀이 N, M : 입력값 c1, c2 : 입력값 => 두 점의 X 좌표 P, Q : 입력 배열 left, right : 투 포인터 변수 ans ..