본문 바로가기

분류 전체보기

 (58)
백준 9470 Strahler 순서 (C++) https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 간단해보여서 bfs로 풀어볼라했는데 복잡해지길래 위상정렬을 쓰면 훨씬 쉬울것 같아서 위상정렬을 사용했습니다. 현재 노드의 Strahler순서를 기록하는것에 유의하면서 풀면 됩니다. 저는 pair배열을 사용했습니다. #include #include #include #include #include #include #include #include #include #include #include us..
백준 15910 바나나나빠나나 (C++) https://www.acmicpc.net/problem/15910 15910번: 바나나나빠나나 입력에서 주어진 문자열을 '유사 바나나 문자열'로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 출력한다. '유사 바나나 문자열'로 바꿀 수 없는 경우는 존재하지 않는다. www.acmicpc.net 생소한 dfa때문에 풀기 어려웠던 문제였습니다. dfa를 통해 문자열에서 패턴을 찾을 수 있습니다. 문자열에서 어떤 위치를 상태로 가정하고 이에 따라 다음은 패턴에 따라 어디로 전이되야하는지(어떤 문자가 나와야하는지)를 알 수 있습니다. 우리는 이를 문제에 어떻게 적용할 수 있을까요. 원래대로 라면 dfa로 패턴을 매칭할때 나와야 하는 문자가 나오지 않을경우 초기상태부터 시작하지만 문제에 적용하면 우리는 문자가 나..
백준 3114 사과와 바나나 (C++) https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 누적합과 dp를 사용하는 문제였습니다. 시간복잡도가 엄청 빡빡하지 않아서 좀 안좋게 짠거같은데도 ac받아서 다행입니다. 먼저 경계선은 각 열마다 어떤 행을 고르는 걸로 생각할 수 있습니다. 열마다 선택한 행 아래 A개수 위의 B개수를 생각하면 됩니다. 각 열마다 열의 A개수와 B개수는 독립적이니까요. 말을 어렵고 이상하게 했는데 경계선을 예시로 그려보시면 어떤 얘기인지 알것 같습니다. 움직일 수..
백준 23044 트리 조각하기 (C++) https://www.acmicpc.net/problem/23044 23044번: 트리 조각하기 타고난 트리 조각가 온조는 오늘도 완벽한 작품을 만들기 위해서 트리 $T$를 준비하였다. 온조는 뛰어난 예술적 직관을 통해 조각할 작품을 머릿속으로 구상하였고, 먼저 조각상의 전체적인 틀 www.acmicpc.net bfs와 파라메트릭 서치(이분탐색)을 이용하는 문제였습니다. 폭탄을 터뜨릴 정점을 선택하는 것과 최대 거리를 둘 다 구하는것은 매우 어렵습니다. N이 20만으로 매우크기때문이죠. 따라서 우리는 둘 중 하나를 고정해서 풀어야 합니다. 이럴때 우리가 사용할 수 있는게 파라메트릭 서치입니다. 우리는 최대거리를 구하고 싶습니다. 답이 되는 최대거리+1 이후로는 당연하게도 전부 최대거리 후보가 되지 못합니..
백준 1786 찾기 (C++) 문자열 탐색 알고리즘을 사용하라는 문제입니다. kmp나 라빈 카프 둘 중 아무거나 사용하면 됩니다. 보이어무어 알고리즘 같은경우 최악의 경우 (N*M)이므로 시간복잡도를 넘게됩니다. 저는 라빈카프를 사용해서 풀었습니다. 영어소문자와 띄어쓰기로 이루어져있으므로 사용되는 문자가 61개정도되는데 충분히 큰 radix와 mod를 사용하셔야 합니다. #include #include #include #include #include #include #include #include #include #include using namespace std; void fast_io() { cin.tie(0)->sync_with_stdio(0); } long long MOD=1000000007; long long mod(long..
백준 4817 괄호 (C++) https://www.acmicpc.net/problem/4817 4817번: 괄호 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 문제 설명의 문법을 만족하는 식이며, 한 줄로 이루어져 있다. 식의 길이는 최대 1000이다. www.acmicpc.net 재귀함수나 스택을 사용하는 문제였습니다. 저같은 경우 스택을 잘 못써서 재귀를 사용해 풀었습니다. 손으로 예제를 들어서 풀어보시면 괄호를 못없애는 경우는 괄호 안에 덧셈이 들어가있으며 괄호 앞 뒤로 곱하기가 들어가있는경우 뿐인걸 아실 수 있습니다. 따라서 재귀적으로 가장 바깥에 있는 괄호부터 풀어가시면서 그 괄호안에 덧셈이 들어가있는 경우만 체크해서 앞뒤로 곱하기가 있는지만 확인하고 괄호를 없애면 됩니다. 또한 유의해야되는 경우는 ..
백준 23022 숙제 (C++) https://www.acmicpc.net/problem/23022 23022번: 숙제 Albert는 앞으로 n개의 숙제를 해야한다 (편의상 1번부터 n번까지 번호가 붙어있다). 현재 시각은 S 이고, i번째 숙제의 내용은 정해진 시각 t[i]에 공개 된다 (어떤 숙제는 이미 공개 되었지만 Albert www.acmicpc.net 우선순위 큐를 사용하는 문제였습니다. 시간순으로 숙제를 정렬 한후 앞에서부터 스위핑하면서 현재시간(초기에는 S) 기준으로 작으면 큐에 넣고 현재시간보다 뒤의 숙제가 나온다면 현재시간을 증가시켜가며 큐에서 빼면됩니다. 그러다가 증가시키면서 지금보고있는 숙제시간의 시간과 같아진다면 현재 숙제를 큐에넣고 다음 숙제로 넘어가면 됩니다. #include #include #include ..
백준 16882 카드게임 (C++) https://www.acmicpc.net/problem/16882 16882번: 카드 게임 예제 1의 경우에 구사과가 7을 고르면 모든 카드가 제거되기 때문에, 큐브러버가 이길 수 없다. 예제 2의 경우에는 어떤 카드를 제거해도 카드 한 장이 남는다. 따라서, 큐브러버가 이긴다. www.acmicpc.net 게임이론 문제입니다. 게임이론 문제들은 제 경험상 손으로 써가면서 경우의 수를 찾는게 가장 좋더라고요. 생각보다 직관적이어서 어렵지 않은 문제였습니다. 어떤 수를 가져가면 그보다 작은 수 들을 전부 없애고 마지막으로 카드를 전부 없앤 사람이 이기는 게임입니다. 직관적으로 가장 큰 수를 가져가게되면 큰 수를 제외한 모든 수를 가져갈 수 있게되고 따라서 가장 큰 수의 개수가 승리와 연관이 되있다는걸 알..

티스토리툴바