메이쁘

www.acmicpc.net/problem/16934 16934번: 게임 닉네임 첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, �� www.acmicpc.net 안녕하세요. 트라이 알고리즘 문제입니다. 트라이 알고리즘의 구조와 원리를 알면 쉽게 접근하실 수 있습니다. 몇 가지 유의할 점이 있다면, - 새로운 단어를 삽입할 때 이전 삽입한 단어들과 비교하면서 같은 접두사의 최대 길이를 파악해야합니다. - 완전히 같은 단어가 존재하는지 안하는지 체크해야합니다. 이를 위해 TrieNode 내에 count 라는 int 변수를 만들어 이를 활용합니다. - 위..

www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 안녕하세요. 이 문제는 수학 + 조합 + 정렬 입니다. 그리고, solved.ac 기준 골드1 문제입니다. 처음 시간 초과가 발생했었는데, 정렬(O(n)) -> 두 지점을 잡고(O(n^2)) -> 각 지점 내의 원소로 만들 수 있는 조합 개수(DP로 미리 구해둠.) * (높은 지점 - 낮은지점) 대충 이런 매커니즘으로 작성했었고, 당연히 1초 시간제한인 이 문제에서는 통과를 못했었습니다. 결국, 몇 번 풀이를 참고해서 이해했습니다. 아직 제대로 푸는 문제가 별로 없네요..ㅎㅎ 이 문제는 결..

www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 안녕하세요. 이 문제는 BFS 알고리즘 문제입니다. solved.ac 에서 골드1 문제 입니다. 오랜 시간 고민하고 풀었습니다. 처음에 작성한 매커니즘은 시간 초과가 발생해서, 한참을 줄이려고 고민했습니다. 그러다 BFS 알고리즘 두 번을 사용해서 해결하는 솔루션을 찾아냈고, 이를 통해 문제를 해결했습니다. 다른 풀이를 참고해보니 BFS + 우선순위큐, Disjoint-Set 알고리즘 등의 방법이 있었..

www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, �� www.acmicpc.net 안녕하세요. 이 문제는 백트래킹 알고리즘을 사용하여 해결했습니다. 특히, 버튼은 총 10회를 넘지 않는다는 조건과 네 방향으로 이동할 수 있다는 조건, 동전이 하나라도 밖으로 나가게 하는 최소 회수 를 찾아야 하는 것 을 통해 백트래킹을 사용한다는 것을 알았습니다. BFS 알고리즘을 사용해도 되지만, 조건이 여러모로 까다롭고 방문 체크 파악하기도 어렵기 때문에 백트래킹 알고리즘을 사용했습니다. 그렇기 때..

www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1

www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 �� www.acmicpc.net 안녕하세요. BFS와 투 포인터를 사용하여 문제를 해결했습니다. 사실 풀다가 도저히 모르겠어서 해설을 참고했습니다... 물론, 투포인터 사용하지 않고 DFS와 이분탐색으로 해결하신 분들도 있더라구요. 그치만 제가 풀어본 방법으로 포스팅하겠습니다! 짚어볼 사항 - 상덕이가 느낀 피로도 = 방문 지점 중 피로도 최댓값 - 최솟값. 이 값이 최소가 되는 경우의 최소값을 구해야 합니다. 즉, 전..

www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 안녕하세요. Disjoint-Set 중 Union-Find 알고리즘을 사용한 문제입니다. 이 문제는 기본적인 문제입니다. (저는 한 번 틀렸죠.. 실수해서) 크게 어려울 건 없습니다. 입력받을 때 - 맨 앞 숫자가 0이면 : union(a, b) - 맨 앞 숫자가 1이면 : isSameParent(a, b) -> 부모가 같으면 YES /// 다르면 NO 이 때, 메모리 효율..

www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 � www.acmicpc.net 안녕하세요. 이 문제는 그리디가 핵심이고, 백트래킹 방식을 활용했습니다. 추가로, 시간초과를 방지하기 위해 DP를 곁들였습니다. 처음부터 끝까지 연결할 수 있는 파이프의 최대 개수 를 구하는 문제입니다. 대신, 한 칸에 하나의 파이프만 설치할 수 있습니다. 이는 곧, 파이프 위치를 맵에 추가하며 파이프를 설치해야 한다는 것이죠. 처음에는 가중치가 없기 때문에 BFS와 Boolean 배열을 사용해서 풀 수 있지 않을까? 했지..

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 �� www.acmicpc.net 안녕하세요. 문자열 탐색을 위한 알고리즘으로 트라이 알고리즘을 사용했습니다. 트라이 알고리즘은 노드로 이루어진 트리를 사용하는 방법인데요. 가장 긴 문자열의 길이가 L, 총 문자열들의 수를 M개 라고 할 때 - 삽입 : 1개 넣을 시 O(L) /// M개 넣을 시 : O(M*L) - 탐색 : 1개 탐색 시 O(L) /// M개 탐색 시 : O(M*L) O(NlogN) 이 소모되는 이..

www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 난이도 극악.. 다익스트라 알고리즘 문제 중 거의 상급 문제.. 주말 하루를 날리게 만든 문제입니다. 시간 제한이 1초이기 때문에 정말 어려운데요. 하.. 아무튼 두 지점 사이에 가중치가 1이 아니기 때문에 BFS/DFS 는 사용할 수 없기 때문에 다익스트라 두 가지를 사용하면 되는데, 하나는 달빛 여우가 각 지점 별 최소 이동 시간을 구하기 위한 다익스..