본문 바로가기

알고리즘204

[백준] 1972번 - 놀라운 문자열 (C++) 문제 및 풀이 문제) 백준 - Set, HashMap - 놀라운 문자열 -> https://www.acmicpc.net/problem/1972 1972번: 놀라운 문자열 대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문 www.acmicpc.net 입력으로 주어지는 문자열의 길이가 80을 넘지 않고 입력의 줄 수가 101줄을 넘지 않으므로 Set을 이용하여 D-쌍들을 하나씩 탐색하여 놀라운 문자열인지 판별할 수 있다. C++ 소스코드) 2021. 9. 23.
[백준] 2631번 - 줄세우기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 줄세우기 -> https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 이미 정렬되어 있는 아이들 제외하고 정렬되지 않는 아이들을 옮긴다. 이때 옮겨지는 아이의 최소 수를 구해야 되므로 정렬되어 있는 아이들의 최대 수(Lis)를 구하여 전체 아이들의 수(n)에서 빼준다. C++ 소스코드) 2021. 9. 3.
[프로그래머스] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기 -> https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 2칸내.. 2021. 8. 4.
[프로그래머스] 2021 카카오 채용연계형 인턴십 - 숫자 문자열과 영단어 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2021 카카오 채용연계형 인턴십 - 숫자 문자열과 영단어 -> https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 문자열과 관련된 간단한 구현 문제. 문자열 길이만큼 탐색하면서 숫자 영단어일 경우와 숫자 문자일 경우를 각각 처리해주면 된다. 파이썬 소스코드) 다른 사람 풀이) 딕셔너리의 key, value를 이용하여 s 문자열 속의 모든 영단어(key)를 숫자(value)로 바.. 2021. 8. 3.
[백준] 5557번 - 1학년 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 1학년 -> https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net F (Idx, PartialSum) : 0번째 수부터 Idx까지의 합의 개수 DP에 적용할 점화식을 다음과 같다고 하자. 그럼 점화식을 F(Idx + 1, PartialSum + number[Idx + 1]) + F(Idx + 1, PartialSum - number[Idx + 1])로 통해 올바른 등식의 .. 2021. 7. 27.
[백준] 2186번 - 문자판 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 문자판 -> https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net F(x, y, index): 점 (x, y)에서 index이후의 부분 문자열을 만들 수 있는 경로의 개수 점화식을 다음과 같이 설정 후, 모든 문자판을 순회하면서 F(x, y, index)의 값을 더한다. C++ 소스코드) 2021. 7. 27.
[백준] 1448번 - 삼각형 만들기 (C++) 문제 및 풀이 문제) 백준 - 그리디 (Greedy) - 삼각형 만들기 -> https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 세 변으로 만들 수 있는 삼각형 중 세 변의 합의 최대를 구하는 문제. N이 100만이므로 O(nC3)으로 완전 탐색이 불가능한다. 최대만 구하면 되므로 모든 변을 내림차순으로 정렬한 뒤, 삼각형을 이룰 수 있는 변 3개가 존재하면 답을 출력한다. C++ 소스코드) 2021. 7. 27.
[백준] 1188번 - 음식 평론가 (C++) 문제 및 풀이 문제) 백준 - 수학 - 음식 평론가 -> https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 예제와 n과 m의 경우의 수를 관찰하며 해결했다. 소시지를 하나로 이어 붙인다. n개의 소시지를 무조건 m명의 평론가한테 주려면 소시지를 최대 m-1번 잘라 m개의 배수개로 토막 낸다. n과 m이 서로소일 때는 m - 1번 자르는 것이 답임을 알 수 있고, 서로소가 아닐 경우에는 m - 1번에서 n-1번 잘린 위치와 m - 1번 잘린 위치의 공통 위치만큼 제외해준다. 이 수는 최대공약수임을 알 수 있다. C++ 소스코드) 2021. 7. 27.
[백준] 9934번 - 완전 이진 트리 (C++) 문제 및 풀이 문제) 백준 - 트리(Tree) - 완전 이진 트리 -> https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위 순회(In-Order)가 주어졌을 때, 트리의 개형을 복원하는 문제. 트리의 Root -> Sub Left Tree -> Sub Right Tree 순으로 재귀적으로 탐색하면 해결 C++ 소스코드) 2021. 7. 14.
반응형

티스토리툴바