코딩테스트
1.[코딩테스트] 하노이 탑 - 재귀
바킹독의 실전 알고리즘 강의를 참고하여 공부한 내용입니다. 참고 자료 바킹독의 실전 알고리즘 - 재귀 백준 11729번 : 하노이 탑 이동 순서 https://www.acmicpc.net/problem/16947 하노이 탑이란? 아래의 조건을 지키며 n개의 원판
2.[코딩테스트] [BOJ16947] 서울 지하철 2호선
https://www.acmicpc.net/problem/11729역은 노드, 역과 역을 연결하는 구간은 간선으로 표현한 그래프(이중벡터)를 생성차수(연결된 노드 수)를 표현한 벡터 생성사이클을 판별하기 위해 차수가 1인 노드 삭제 및 사이클에서 제외3-1.
3.[코딩테스트] [BOJ1260] DFS와 BFS
https://www.acmicpc.net/problem/1260이중벡터로 간선 정보를 포함한 그래프를 생성한다재귀함수로 dfs를 구현2-1. 시작 노드를 방문 체크해주고, 탐색한 순서를 저장하는 벡터에 넣어준다2-2. 인접한 노드를 순회하며, 방문하지 않은
4.[코딩테스트] [BOJ24090] 알고리즘 수업 - 퀵 정렬 1
https://www.acmicpc.net/problem/24090의사코드를 C++ 코드로 작성한다맨 끝 원소를 pivot으로 잡고, -1부터 index를 시작해서 작은 값을 왼쪽 정렬, 큰 값을 오른쪽 정렬한다1-1. 이때, n-1보다 작을때까지 index를
5.[코딩테스트] [BOJ1068] 트리
https://www.acmicpc.net/problem/1068연결된 자식 노드를 삭제해야하기 때문에 자식 노드 입장에서 연결된 부모 노드를 알 필요가 없다 => 부모 노드에 연결된 자식 노드만 표현한 그래프 만들기지워야 할 노드를 입력받고, 해당 노드로부터
6.[코딩테스트] [BOJ11724] 연결 요소의 개수
https://www.acmicpc.net/problem/11724간선 정보 포함한 무방향 그래프를 이중벡터로 만들어준다노드 방문 여부 확인용 벡터를 만들어준다순차적으로 노드를 방문하며 인접한 노드에 대해 bfs를 수행하고, 방문 체크를 해준다3-1. 해당 노
7.[코딩테스트] [BOJ1021] 회전하는 큐
https://www.acmicpc.net/problem/1021양방향 순환 큐기 때문에 deque로 구현해준다.입력받은 큐의 크기만큼 deque에 원소를 삽입한다.m번만큼 반복하며 현재 뽑아낼 수를 입력받는다.3-1. std::find로 deque를 순회하며
8.[코딩테스트] [BOJ11003] 최솟값 찾기
https://www.acmicpc.net/problem/11003숫자를 기록할 int형 벡터, index를 기록할 덱을 선언한다.n번만큼 반복문을 돌며 숫자를 입력받고, 덱이 비어있거나 조건을 통과하면 push_back 해준다.2-1. 현재 인덱스 - 탐색할
9.[코딩테스트] [BOJ11053] 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053algorithm 헤더의 std::lower_bound로 배열을 순회하며 요소가 value보다 크거나 같을 때, 해당 위치를 value값으로 바꿔준다.만약 end iterator을 반환하는 경우
10.[코딩테스트] [BOJ2003] 수들의 합 2
https://www.acmicpc.net/problem/2003반복문 두개 돌려서 값 다 더하는 방식으로, O(n^2)의 시간복잡도가 나옴문제 조건이 넉넉해서 넘어갔는데, 개선이 필요하다 느껴 지피티 도움받음left : 합에 포함되는 가장 왼쪽 인덱스 / r
11.[코딩테스트] [BOJ1927] 최소 힙
https://www.acmicpc.net/problem/1927priority_queue를 활용하여 최소 힙을 구현한다.입출력 연산 속도를 위해 아래 코드 추가
12.[코딩테스트] [BOJ1715] 카드 정렬하기
https://www.acmicpc.net/problem/1715우선순위 큐로 최소 힙을 생성하여 입력값을 관리한다.가장 작은 수 2개를 순차적으로 합쳐서 횟수를 계산해야 하기 때문에, 큐의 원소가 2개 이상일 때 반복한다.2-1. top에 있는 수와 그 다음
13.[코딩테스트] [BOJ1655] 가운데를 말해요
https://www.acmicpc.net/problem/1655중간 값을 top으로 하는 최대 힙(leftQueue)과 중간 값보다 큰 요소들로만 이루어진 최소 힙(rightQueue)을 활용한다.ex) 1, 5, 2, 10, -99, 7, 5 입력을 받았을
14.[코딩테스트] [프로그래머스] 완주하지 못한 선수
https://school.programmers.co.kr/learn/courses/30/lessons/42576삽입/탐색 시 O(1)의 시간복잡도로 풀이하기 위해 unordered_map을 사용했다. 해당 unordered_map은 key(선수 이름), va
15.[코딩테스트] [프로그래머스] 폰켓몬
https://school.programmers.co.kr/learn/courses/30/lessons/1845key(종류), value(빈도) 쌍을 관리하는 unordered_map을 생성한다.unordered_map 크기는 폰켓몬 종류 개수이므로 (nums
16.[코딩테스트] [프로그래머스] 전화번호 목록
https://school.programmers.co.kr/learn/courses/30/lessons/42577원소 탐색 시 O(1)의 시간이 걸리는 unordered_set을 사용한다. phone_number의 값을 모두 set에 넣어준다.phone_num
17.[코딩테스트] [프로그래머스] K번째 수
https://school.programmers.co.kr/learn/courses/30/lessons/42748일정 범위 내의 부분 배열을 저장하기 위해 새 벡터를 만들어 push_back 하고, 이를 algorithm 헤더의 sort 함수를 사용해서 정렬하
18.[코딩테스트] [프로그래머스] 가장 큰 수
https://school.programmers.co.kr/learn/courses/30/lessons/42746algorithm 헤더의 sort 함수에 compare 인자를 커스텀해서 넣어준다.1-1. 문자열끼리 더해서 더 큰 문자열이 앞에 오도록 정렬해준다
19.[코딩테스트] [프로그래머스] 올바른 괄호
https://school.programmers.co.kr/learn/courses/30/lessons/12909여는 괄호 '('를 스택에 넣는다.닫는 괄호 ')'가 나온다면, 스택의 top에 여는 괄호가 있는지 검사한다.2-1. top이 여는 괄호라면, 쌍이
20.[코딩테스트] [프로그래머스] 기능개발
https://school.programmers.co.kr/learn/courses/30/lessons/42586선입선출 구조의 큐를 사용해서 각 기능마다 완성까지 남은 날짜를 push한다.큐의 front를 최소 날짜로 잡고, 반환할 벡터(answer)에 1을
21.[코딩테스트] [프로그래머스] 타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165깊이 우선 탐색을 통해 각 원소에 + 또는 -를 붙였을 때의 합을 구한다. => 합이 target과 같다면, 1을 반환한다.재귀함수를 사용해서 현재
22.[코딩테스트] [프로그래머스] 네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162노드의 개수 n, 간선 정보 computers 벡터가 주어졌을 때 간선으로 이어진 덩어리의 개수를 세는 문제이다. => bfs로 풀이이중벡터로 간선
23.[코딩테스트] [프로그래머스] 게임 맵 최단거리
https://school.programmers.co.kr/learn/courses/30/lessons/1844bfs로 상하좌우 위치 탐색하며 방문 체크 및 distance 증가하는 방식으로 코드 짬=> 도착지로부터 멀어지는 경우의 수에도 distance가 증
24.[코딩테스트] [프로그래머스] 단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163source 문자열과 target 문자열을 비교한다고 가정하자. 1개의 문자 빼고 모두 같으며 한번도 확인하지 않은 문자열이라면 source 문자열
25.[코딩테스트] [해커랭크] Roads and Libraries
https://www.hackerrank.com/challenges/torque-and-development/problem?isFullScreen=true도시 개수(n), 도서관 건설비용(c_lib), 도로 건설비용(c_road), 건설 가능 도로 정보(cit
26.[코딩테스트] [프로그래머스] 최소직사각형
https://school.programmers.co.kr/learn/courses/30/lessons/86491가로와 세로 길이를 비교하며 더 큰 수를 가로로 swap가로 길이 중 제일 큰 수, 세로 길이 중 제일 큰 수 도출 후 곱하여 returnswap을
27.[코딩테스트] [프로그래머스] 모의고사
https://school.programmers.co.kr/learn/courses/30/lessons/42840찍는 패턴 순서대로 벡터 만들어두고, index % 각 벡터 size를 인덱스로 하여 answers 값과 비교한다.1-1. answers 값과 비교
28.[코딩테스트] [프로그래머스] 가장 먼 노드
https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=cpp간선 정보를 포함한 무방향 그래프를 이중 벡터로 구현한다. 이때, 노드 번호가 1부터 시작이므로 1씩 빼준다.1-1. 오름차
29.[코딩테스트] [프로그래머스] 가장 많이 받은 선물
https://school.programmers.co.kr/learn/courses/30/lessons/258712map<string, int>로 사람 이름별 인덱스를 저장한다.이중벡터 giftCount를 만들어 giftCounti = i가 j에게 준 선
30.[코딩테스트] [프로그래머스] 도넛과 막대 그래프
https://school.programmers.co.kr/learn/courses/30/lessons/258711단방향 그래프는 이중벡터, 각 노드별로 나가는 간선 수 / 들어오는 간선 수는 벡터로 저장한다.나가는 간선 수가 2개(최소 그래프 개수) 이상이고
31.[코딩테스트] [프로그래머스] 개인정보 수집 유효기간
https://school.programmers.co.kr/learn/courses/30/lessons/150370'.' 기준으로 오늘 날짜 문자열을 나눠 벡터에 저장해준다.1-1. 띄어쓰기 기준으로 문자열을 나눠 약관 종류를 key, 유효기간을 value로
32.[코딩테스트] [프로그래머스] 주사위 고르기
https://school.programmers.co.kr/learn/courses/30/lessons/258709n개의 주사위 중, A와 B가 n/2개씩 주사위를 나누어 갖는 조합을 구한다.1-1. 주사위 조합을 구하기 위해 n개의 크기를 가진 comb 벡터
33.[코딩테스트] [프로그래머스] n + 1 카드게임
https://school.programmers.co.kr/learn/courses/30/lessons/258707동전을 최대한 적게 소모하면서 라운드를 진행해야 하므로, 동전 소모 개수에 따라서 분기한다.0-1. 동전을 0개(zeroCoinPairs), 1개