Problem Solving 썸네일형 리스트형 BOJ 11066 - 파일 합치기 문제 링크https://www.acmicpc.net/problem/11066 문제 해결 1. dp[i][j] = i번 장에서 j번 장까지 합치는 데 드는 최소값. 주의할 점 || 생각해볼 점 1. 부분 합으로 미리 구간의 합을 구해놓으면 시간을 절약할 수 있다. 참고 - 부분 합 : http://terms.naver.com/entry.nhn?docId=849492&cid=50376&categoryId=50376 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1254 - 팰린드롬 만들기 문제 링크https://www.acmicpc.net/problem/1254 문제 해결 1. 팰린드롬 확인하는 최대 횟수 : 1,000 만들 수 있는 문자열의 최대 길이 : 1,999 → 2,000,000 이하 이므로 Brute force 가능 ( 왜 DP로 분류되는 이유를 모르겠다...) 주의할 점 || 생각해볼 점 1. 0개 이상 붙이는 것이므로, 이미 팰린드롬이면 그냥 길이를 출력해야한다. 참고 - 팰린드롬 (회문) : https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8 - brute force : https://namu.wiki/w/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 3943 - 헤일스톤 수열 문제 링크https://www.acmicpc.net/problem/3943 문제 해결 1. 문제 그대로 짝수와 홀수일 경우를 나눠서 재귀 형식으로 구현 2. DP[i] = i로 시작하는 헤일스톤 수열이 가질 수 있는 가장 큰 수 주의할 점 || 생각해볼 점 1. N의 범위가 100,000까지라고 해도 계산 시 100,000을 넘어갈 수 있다. ex) 99,999같은 경우 2. 100,000이 넘어가는 경우는 배열에 저장하지 않고 계산한다. 참고 - 콜라츠 추측 (우박 수열 or 헤일스톤 수열) : https://namu.wiki/w/%EC%BD%9C%EB%9D%BC%EC%B8%A0%20%EC%B6%94%EC%B8%A1 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 13171 - A 문제 링크 https://www.acmicpc.net/problem/13171 문제 해결 1. Successive Squaring Method를 이용해서 문제를 해결해야한다. ( A와 X 모두 10^18이므로) 2. 문제에 해결 방법이 나와있는 쉬운 문제 주의할 점 || 생각해볼 점 1. 반드시 A도 나머지 연산을 해야한다. ( 곱하는 단계에서 오버플로우가 생길 수 있다.) 2. 곱하기 연산을 할 수도 있지만, 이진수로 표현함을 이용해서 비트 연산을 하는 것이 더욱 효율적이다. 참고 Successive Squaring Method : http://mathworld.wolfram.com/SuccessiveSquareMethod.html ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2602 - 돌다리 건너기 문제 링크https://www.acmicpc.net/problem/2602 문제 해결1. " 한 방향으로 이동 + 모든 경우의 수 " 에서 Dynamic Programming으로 해결 2. dp[i][j][k] = i (천사 또는 악마) 행, j (돌다리) 열을 밟았을 때 두루마리 속 k번째 문자를 밟은 경우의 수. 3. Top-down 형태로 풀려고 애썼다. 주의할 점 || 생각해볼 점1. Dp 배열을 만드는 것이 어려웠다. 완전 탐색 하면서 놓치지 않아야 할 정보를 담아야한다. 2. 기저 조건을 설정하는 것이 익숙하지가 않았다. 가령 최대 인덱스가 k라면, k+1에서 기저 조건을 수행. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2436 - 공약수 문제 링크https://www.acmicpc.net/problem/2436 문제 해결1. 구하려는 두 수를 a, b로 놓는다. 2. a == (GCD*x), b == (GCD*y) 이므로, measure = x*y (x*y == LCM/GCD) 3. measure의 (x,y)쌍을 찾되 합이 가장 작은 것을 찾아야하므로 시간을 단축하기 위해, sqrt(measure)부터 찾는다. 주의할 점1. LCM == GCD*x*y가 성립하기 위해선 반드시 x와 y가 서로소임을 보여야한다. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1194 - 달이 차오른다, 가자. 문제 링크https://www.acmicpc.net/problem/1194 문제 해결1. 기본적인 BFS에 비트마스크를 추가한 형태로 해결. visit[row][column][key_bitmask] 주의할 점1. 같은 시간대를 구현하기 위해서 큐의 크기를 이용. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2002 - 추월 문제 링크https://www.acmicpc.net/problem/2002 문제 해결1. 터널에 들어갈 때와 터널에서 나올 때의 차량의 순서를 각 Queue1, 2에 저장한다. 2. Queue1, 2의 front()에 있는 값이 같으면, 둘다 pop() 해준다. 3. Queue1, 2의 front()에 있는 값이 다르면, Queue1의 front() 값을 push()해주고 다시 처음 값이 나올 때까지 pop() & push()를 해준다. 그런 와중에 Queue2의 front()값과 같은 값이 나오면 pop()만 해준다. 즉, Queue1에서 Queue2의 front()와 같은 값을 찾아서 pop()해준다. 4. N번만 확인하면 추월한 차량의 수를 알 수 있다. 주의할 점1. 비교적 간단한 문제지만, 순서.. 더보기 BOJ 10546 - 배부른 마라토너 문제 링크https://www.acmicpc.net/problem/10546 문제 해결1. N만큼 이름을 문자열로 받는다. 2. N-1만큼 완주자의 이름을 문자열로 받는다. 단, 동명이인이 있을 수 있다. 3. STL map을 사용해서 이름을 저장한다. 저장할 때, 같은 이름이 나오면, 그 이름의 value값을 올려준다. 4. N-1번 완주자의 이름을 받을 때, value값을 하나씩 내린다. 5. 출력할 때, value 값이 0이 아닌 key만 출력한다. 주의할 점1. 동명이인이 있을 수 있으므로, 이미 key값이 존재할 때와 존재하지 않을 때를 나눠서 처리해줘야한다. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1947 - 신입 사원 문제 링크https://www.acmicpc.net/problem/1946 문제 해결1. 지원자들은 서류 점수 등수(A)와 면접 점수 등수(B)를 받는다. 2. 신입 사원이 되기 위해선, 모든 지원자들과 비교했을 때 A와 B가 모두 모자라지 않아야한다. 즉, A와 B와 모두 다른 지원자들과 비교했을 때, 같거나 작아야한다. 왜냐하면 A와 B는 점수가 아니라 등수이기 때문이다. 3. 우선 A에 대해서 오름차순 정렬을 한다. 4. 0번째 지원자는 모든 지원자 중에서 A 등수가 가장 높으므로 1번째 지원자부터 N번째 지원자까지 비교한다. 5. i번째 지원자는 0번째 지원자부터 i-1번째 지원자까지의 B 등수 중 가장 높아야한다. 즉, 0번째 지원자부터 i-1번째 지원자까지의 B등수 중 가장 높은 등수(temp.. 더보기 이전 1 ··· 4 5 6 7 8 9 다음