본문 바로가기

algorithm53

[백준/1991] 트리 순회 (재귀, 트리) https://www.acmicpc.net/problem/1991 #include using namespace std;pair node[26];int n;void preorder(char cur) { if(cur=='.') return; cout > n; for(int i=0; i> parent >> left >> right; node[parent-'A'].first = left; node[parent-'A'].second = right; } preorder('A'); cout node 라는 pair형 배열에 first는 왼쪽자식, second는 오른쪽 자식을 담음전위 순회 : 현재 노드 출력 -> 왼쪽 자식 출력 -> 오른쪽 자식 출력중위 순회 .. 2025. 10. 14.
[코딩테스트] 2025년 빈출 유형 시간 복잡도1초에 약 1억(10⁸)번 연산 가능하다고 가정입력값 ≤ 500 이하: O(n³) -> 완전탐색, DFS/BFS, 백트래킹입력값 ≤ 2,000 이하: O(n²) -> DP, 그래프 Floyd-Warshall입력값 ≤ 100,000 이하: O(n log n)이하 -> 정렬, 우선순위큐, 투포인터, 다익스트라입력값 ≤ 1,000,000 -> 슬라이딩 윈도우, 해시, 스택 입력값 ≤ 10,000,000 이상: O(n) 코딩테스트 빈출 유형1. 구현 (시뮬레이션, 문자열)2. 완전탐색 (BFS, DFS, 백트래킹)3. 완전탐색 (순열과 조합)4. 자료구조 (배열, 스택, 큐, 힙, 해시)5. DP6. 슬라이딩 윈도우7. 투 포인터8. 이분 탐색9. 최단 경로 알고리즘 (Dijkstra, Bellm.. 2025. 10. 5.
[백준/20437] 문자열 게임 2 (슬라이딩 윈도우, C++) https://www.acmicpc.net/problem/20437아이디어1. 입력받은 문자열 알파벳마다 등장 위치 저장2. 알파벳이 k번 이상 나오면 k개 연속으로 잡음3. 부분 문자열의 길이를 구해 최소/최대 갱신4. 모든 알파벳 검사 후 출력 1. 완전탐색, 슬라이딩 윈도우#include using namespace std;int t, k;string w;int main() { cin >> t; for(int test=0; test> w; cin >> k; int minNum = INT_MAX; int maxNum = -1; for(int i=0; i시간 초과 발생 2. 투포인터, 슬라이딩 윈도우#include using namespac.. 2025. 10. 4.
[프로그래머스 level3] - 베스트앨범 (Java), 해시(hash)에 대한 모든 것(코딩테스트를 위한 해시, CS를 위한 해시) https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 방법1. 장르별 재생 횟수 저장2. 각 장르에 속한 노래의 저장3. 장르별 재생 횟수를 저장4. 곡 수대로 내림차순 정렬5. 정렬된 num의 순서대로 상위 2곡의 고유번호를 ArrayList에 저장import java.util.*;class Solution { public int[] solution(String[] genres, int[] plays) { ArrayList answer = new Array.. 2025. 1. 27.
[프로그래머스/SQL] 흉부외과 또는 일반외과 의사 목록 출력하기 DATE_FORMATDATE_FORMAT을 잘 쓰는지 물어보는 문제였다.DATE_FORMAT(테이블명, ‘%y-%m-%d’) 처럼 출력 형식을 써주면 잘 출력 된다. SELECT DR_NAME, DR_ID, MCDP_CD, DATE_FORMAT(HIRE_YMD, '%Y-%m-%d') AS HIRE_YMDFROM DOCTORWHERE MCDP_CD IN ('CS', 'GS')ORDER BY HIRE_YMD DESC, DR_NAME ASC;%Y : 4자리 연도%y : 2자리 연도%m : 2자리 월 (01-12)%d : 2자리 일 (01-31)%H : 24시간 형식 (00-23)%i : 분 (00-59)%s : 초 (00-59) 2024. 8. 20.
백트래킹 부수기 N과 M 시리즈 백트래킹불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법.가지치기라고도 하는데, 특정한 조건을 만족하는 경우만 살펴보는 것 입니다. DFSDFS는 가능한 모든 경로를 탐색합니다. 그래서 불필요한 행동들이 발생합니다. 2024. 8. 19.

티스토리툴바