hotamul의 개발 이야기

트라이(Trie)란? 트라이(Trie)의 형태 대해서 Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다. DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있습니다. 트라이(Trie)의 예시 직접 그린 Trie이며 주황색으로 된 노드들이 입력된 문자열들입니다. 현재 be, bee, can, cat, cd가 들어가 있습니다. 사용목적 목적 사용하..

url: https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 핵심 1. 완전 탐색 문제 2. 제한 시간 초과를 피하기 위해 cache[50][50][4] 배열을 만들어 두는 것이 필요하다. MAXN (50) * MAXN + 1 로 cache 배열을 초기화 하고 최초 방문일 경우 현재 r, c (행, 열), dir (방향)인 cache[r][c][dir]에 현재까지의 파이프 길이를 저장한다. 중복 방문 했을 경우 현재의 길이가 저장 된 길이보다 크다면 return 하는 방식으로 가지치지 한다. 3. ..

url: https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 핵심 1. Back Tracking, Bruth Force 문제 (완전 탐색) D_C_x (Combination, D개의 행 중 x개 선택) 2^x (x개가 A 또는 B로 약물 투입하는 경우) D*W (W개의 열에서 연속된 수 찾는 경우) D_C_x * 2^x * D * W ~= 대략 4억 (완전 탐색 가능) 2. struct Film을 만들고 성능을 검사하는 (check) 함수와 약물 투입 함수 (dosage) 를 만든다. - check..

url: https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 핵심 1. Back Tracking 문제 2. home, chicken 백터 생성 (1일 경우 r, c home에 저장 / 2일 경우 r, c chicken에 저장) 3. solve 재귀 함수 구현 (전달 인자: 선택한 치킨집 개수 - cnt, 넣을 chicken집 인덱스 - idx) idx 가 chicken.size() 보다 크면 종료 cnt가 M 일 때 (선..

url: https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 핵심 1. Bruth Force + 시뮬레이션 / 구현 문제 2. shark라는 struct를 만들어 문제를 해결한다. shark struct는 다음과 같은 변수, 함수로 구성된다. 현재 상어의 위치 (R, C), 방향 (D), 먹은 물고기 번호의 합 (cnt) 물고기의 ID를 저장하는 map[4][4] 배열 물고기의 위치, 방향, ID를 저장하는 fish 배열 (..

url: https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 풀이 핵심 1. Bruth Force 문제 2. for 문으로 완전 탐색 진행 3. calPop 함수를 통해 인구수의 최대 최소 차 계산 4중 for 문으로 기준 점 (x, y), d1, d2를 변경 시켜 가며 체크한다. 이 때 다음과 같은 조건을 만족한 경우에만 calPop 함수가 실행 될 수 있도록 한다 (OutOfBound 가 발생하지 않게 하기 위해) (d1, d2 ≥ 1, 1 ≤ x ..

url: https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 핵심 1. dfs 문제 (회귀 함수로 구현) 2. 전달 인자는 현재 날짜, 이전에 추가한 날짜, 현재 돈 총합 void dfs(int day, int post, int sum); 3. schedule 배열 생성 (상담에 걸리는 시간, 받을 수 있는 돈 정보 저장) 4. 다음과 같이 회귀 함수 구현 ... for (int i = day; i N + 1) { int m_day = day - schedule[post].t; if (m_day

url: https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 핵심 1. Bruth Force && Back Tracking 알고리즘 문제로 보인다. (추가한 사다리 수가 3보다 크다면 더 이상 탐색할 필요 없으므로 모두 탐색 할 수 있다) 2. DFS 이용 - check(DFS) 함수 탈출 조건 현재 사용한 사다리 수가 ans 보다 크거나 같다면 return 현재 사다리의 각 번호들이 맨 밑까지 내려왔을 때 동일 한지 확인 (맞다면 정답에 ..

url: https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 핵심 1. BFS, DFS 활용 2. 로봇 청소기 위치 ('o'), 쓰레기 위치 ('*') 를 deque에 저장한다. (로봇 청소기의 위치가 가장 맨 앞[0]에 오게 하기 위해) 3. deque저장된 위치들을 배열에 저장 한다 (로봇 청소기 + 쓰레기 수 파악) 4. bfs를 이용해 로봇 청소기와 쓰레기, 각 쓰레기 사이의 최단 거리를 check 배열에 저장한다. 5. dfs를 이용해 최단 ..

url: https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 풀이 핵심 1. 방문 여부 체크 하지 않는다 (중복 해서 방문 할 수 있으므로) 2. 다음 2가지 조건 중 하나라도 만족하면 가장 오른쪽 윗 칸에 도달할 수 있다고 판단한다 현재 위치가 가장 오른쪽 윗 칸이라면 남아있는 벽이 없다면 코드 #define _CRT_SECURE_NO_WARNINGS #include #define N (8) int sr = 7, sc = 0, er =..