알고리즘
1.백준[17135] 캐슬 디펜스 C++ 풀이
시뮬레이션을 구현할 줄 안다적의 col,row값을 저장하되 pair.first로 row값을 사용한다맨 왼쪽이 우선순위 이기에, sort를 통해 row 값이 작은(왼쪽) 순서대로 정해준다3중포문을 통해 궁수들의 row를 선택(col값은 정해져있어서 필요없음), 함수를 실
2.백준[16637] 괄호 추가하기 C++ 풀이
문제의 요소들을 그대로 구현할 줄 안다연산을 string에 넣어준다DFS를 실행한다괄호를 치지 않는 경우, 해당 숫자와 저장한 숫자(왼쪽부터 연산)에 대한 연산을 진행 후 값을 저장, 다음 숫자에 대해 DFS를 진행한다괄호를 치는 경우, 해당 숫자와 그 다음 숫자에 대
3.백준[3190] 뱀 C++ 풀이
시뮬레이션을 구현할 줄 안다큐를 사용할 줄 안다뱀의 몸통의 처음과 끝을 저장해주기 위해 queue를 사용한다배열을 만들어 시간마다 배열을 채크하여, D 혹은 L일 경우 방향 회전을 한다while문을 이용하여 다음 뱀 머리의 위치를 저장하되, 보드의 크기를 넘으면 bre
4.백준[14226] 이모티콘 풀이 C++
BFS를 사용할 줄 안다DFS를 사용할 줄 안다DP를 사용할 줄 안다행은 클립보드에 있는 이모티콘 개수, 열은 현재 화면의 이모티콘 개수에 대한 시간을 저장하기 위해 이차원 배열을 생성한다배열을 최대 시간으로 모두 초기화 해준다우선 무조건 1번의 복사는 필요하기에, 배
5.백준[1890] 점프 C++ 풀이
DP를 사용할줄 안다점프 값을 저장하기 위한 2차배열, 각 위치에서의 dp를 저장하기 위한 2차배열을 만들되, dp는 long long으로 만든다(값이 int보다 커질 수 있음)0,0에서의 dp값은 1로 초기화 해준다2차원배열을 (0,0) ~ (n-1,n-1) 까지 조
6.백준[2293] 동전 1 C++ 풀이
DP를 다룰줄 안다동전의 값을 벡터에 저장해준다DP를 이용하되, 하나의 동전을 하나씩 사용하는 경우마다 단계적으로 조사한다.점화식은 '지금 계산하는 경우의수 = 이전 동전으로만 가능한 경우의 수 + 새로 넣을 동전까지 포함한 경우의수' 로 한다DP로 중복되는 경우를 어
7.백준[1916]_최소비용_구하기 C++ 풀이
다익스트라 알고리즘을 사용할 줄 안다우선순위 큐를 사용할 줄 안다시작 노드, 도착 노드, 비용을 저장해준다우선순위 큐를 이용하여 다익스트라 알고리즘을 실행한다다익스트라 알고리즘을 알고 있으면 풀기 쉬운 문제.하지만 저는이 코드를 넣는 것을 몰라, 시간초과가 계속 발생했
8.백준[1806] 부분합 C++ 풀이
투포인터를 사용할 줄 안다투포인터를 사용해서 길이를 점차 늘려가며 합한 값이 S 이상이 되는지 검사한다\-> S 이상이라면, 맨 왼쪽 길이를 줄여도 S 이상일 수도 있기에, 시작 포인터를 1씩 증가시켜준다\-> S 미만이라면, 아직 값의 개수가 부족하기에, 끝 포인터를
9.백준[1700] 멀티탭_스케줄링
그리디 알고리즘을 사용할 줄 안다.우선 플러그에 1개의 전기기구를 먼저 꽂는다이후 전기기구를 꽂을 때 마다, 그리디알고리즘을 이용하여, 뒤에 더이상 나오지 않는 전기기구 or 가장 늦게 꽂는 전기기구를 선택하여 교체한다.그리디 알고리즘 구현 자체는 굉장히 쉬웠던 문제.
10.백준[1062] 가르침 C++ 풀이
비트마스킹 을 사용할 줄 안다.재귀함수 를 통해 조합을 뽑을 줄 안다.비트마스킹을 통해 각 단어를 비트로 바꿔 벡터에 저장한다재귀함수를 통해 조합하여 만들 수 있는 알파벳의 집합을 전부 구해, 비트마스킹으로 바꾸어 벡터에 저장한다알파벳의 집합과 각 단어를 비교하여 최대
11.백준[2504] 괄호의 값 C++ 풀이
stack을 사용할 줄 알아야한다.문자열을 숫자로 바꾸는 발상의 전환이 필요하다
12.Codeforces Round #737 (Div. 2) B번 풀이 C++
그리디 알고리즘을 사용할 줄 안다숫자값을 저장할 때, pair를 사용해서, {숫자의 값, 위치순서}를 저장해준다.숫자의 값대로 오름차순으로 sort 해준다연속으로 i번째 처음 순서 == i-1번째 처음 순서 + 1 이라면 같은 집합으로 묶을 수 있는 것으로 간주, 계속
13.백준[10816] 숫자 카드 2 C++ 풀이
이분탐색을 사용할 줄 안다들어온 요소들을 sort를 통해 오름차순으로 정렬해준다배열을 생성해, '같은 숫자의 가장 오른쪽 위치'에 숫자의 개수가 저장되게 끔 for문을 돌린다이분탐색을 통해 mid가 목표보다 작거나 같을 경우 mid +1 을 해준다(같은 숫자는 맞지만,
14.[프로그래머스] 후보키 C++ 풀이
DFS를 사용할 줄 안다조합 알고리즘을 사용할 줄 안다각 요소의 개수를 1개부터 최대개수까지 dfs를 돌린다dfs를 통해 각 요소를 조합으로 뽑는다조합으로 뽑는 도중에 이 안에 후보키 대상이 있는지 dfs를 한번 더 사용해서 조사한다후보키 대상이 없으면 set을 하나
15.프로그래머스 프렌즈4마블 C++ 풀이
시뮬레이션을 구현할 줄 안다do-while문을 통해 제거할 블록이 없을때 까지 계속 돌린다. 제거할 블록이 있으면 bool 변수를 false로 만들어 계속 반복문을 실행시킨다2중 for문을 돌며 '-'(제거된 블록) 이 아니라면 4블록을 검사해, 모두 같다면 제거해준다
16.프로그래머스 셔틀버스 C++ 문제풀이
프로그래머스 [1차]셔틀버스
17.[프로그래머스] 추석 트래픽 C++ 풀이
시뮬레이션을 구현할 줄 안다.각 시, 분, 초를 전부 초로 변환하여 끝나는 시간, 처리시간을 저장한다끝나는 시간 - 처리시간 + 0.001 을 통해 시작 시간을 구해 저장한다시작시간 -> 끝나는 시간 순으로 작은 순서로 sort를 진행한다priority_queue를 사
18.프로그래머스 징검다리 C++ 풀이
이분탐색을 사용할 줄 안다.돌들의 위치를 sort를 이용해 오름차순으로 정렬한다이분탐색을 이용해서, 각 돌을 놓을 때 마다 가장 가까운 돌과의 거리를 mid와 비교, 만약 더 작다면 cnt(돌을 뺀 횟수)를 더해준다만약 cnt > n 일 경우 end = mid - 1로
19.프로그래머스 금과 은 운반하기 C++ 풀이
이분탐색을 활용할 줄 안다.이분탐색을 이용한 파라매트릭 서치를 활용할 줄 안다이분탐색에서의 start, end를 입력 범위를 보고 정해준다. 이분탐색의 값은 구해야하는 값인 걸리는 시간으로 잡는다이분탐색을 시행하면서 해당 시간내에 운반할 수 있는 횟수(편도 +1번도 생
20.[백준 1311] 할 일 정하기 1 C++ 풀이
비트마스킹을 사용할 줄 안다비트마스킹을 이용한 dp를 활용할 줄 안다.dp라는 배열을 만들고, dp비트로 활용하되, 비트는 '일을 선택한 곳을 1로 켠 비트'로 저장해준다우선 0번 사람의 0번~n-1번까지의 일을 했다고 초기화 해주고, 그 비트를 vector에 저장해준
21.[백준 1562] 계단 수 C++ 풀이
DP를 사용할 줄 안다비트마스킹을 사용할 줄 안다DP를 위한 배열을 만들되, 배열은 숫자의 길이,마지막(1의자리) 수의 번호,비트를 가질 수 있게 저장한다. 여기서 '비트'는 '현재 숫자에서 찾을 수 있는 숫자는 1로 켠 비트' 로 설정한다. ex) 숫자가 13이면 0
22.[백준 2580] 스도쿠 C++ 풀이
완전탐색(브루트포스)를 사용할 줄 안다얕은 복사(&)로 함수 인자를 넘겨줄 수 있다숫자를 기입하되 가로줄,세로줄,큰 박스에 set을 만들어 숫자를 저장해준다dfs를 돌되, 꼭 '얕은복사'로 비어있는 칸에 해당하는 vector를 넘겨준다1~9까지 반복하며 가로줄,세로줄,
23.백준[20046] 동전 옮기기 C++ 풀이
DP를 사용할 줄 안다기본 입력을 받고, S 문자열에서 옮길 동전을 따로 저장, S에서 옮길 동전을 뺀 문자열을 따로 저장해준다DFS를 돌면서 t 문자열의 0번부터 끝번까지 조사를 한다.새로운 S 위치의 문자와 t 위치의 문자가 같으면 두 위치를 1씩 증가시키고 dfs
24.백준[1202] 보석 도둑 C++ 풀이
그리디 알고리즘을 사용할 줄 안다multiset을 사용할 줄 안다lower_bound를 사용할 줄 안다multiset을 이용하여 bag을 저장한다보석의 정보를 vector에 저장하고, sort를 통해 정렬해준다보석의 value를 큰값부터 조사하되(본인은 음수를 이용하여
25.백준[1865] 웜홀 C++ 풀이
밸만포드 알고리즘을 사용할 줄 안다밸만 포드 알고리즘 이용, n-1번 각 노드에서 다른 노드로 가는 가중치를 계산한다.한번 더 가중치를 계산하여, 이번에도 갱신될 경우 음수사이클이 존재한다고 판단, 이는 시간이 돌아가는 것과 같은 말이기에, YES를 출력하고, 없으면
26.백준[2208] 보석 줍기 C++ 풀이
Dynamic Programming(동적계획법)을 사용할 줄 안다각 자리의 보석까지 m개의 보석을 주울때 총 합을 저장한다.DP를 이용, 이전 DP에서 현재 주울 보석과 각 자리의 m개의 보석만 주웠을 때를 비교해서 큰 값을 저장한다.왜? ex) m이 4일때, 1 2
27.백준[2887] 행성 터널 C++ 풀이
MST 알고리즘을 사용할 줄 안다각 x,y,z 별로 sort를 해서 바로 양옆 행성과의 거리를 거리가 작은 순으로 priority queue에 저장한다\-> 왜? : 결국 행성간 거리는 x,y,z간의 거리중 가장 작은 값이다. 각 좌표별로 sort한다면, 바로 옆 행성
28.백준[14938] 서강그라운드 C++ 풀이
다익스트라 알고리즘을 사용할 수 있다.각 노드별로 거리와 다음 노드를 저장한다.다익스트라 알고리즘을 사용해서 각 노드에서 다른노드까지의 최단거리를 구한다.반복문을 통해 각 노드에서 내렸을 때 다른노드까지의 최단거리가 m보다 작거나 같다면 획득 가능 아이템으로 추가하고,
29.백준[6087] 레이저 통신 C++ 풀이
BFS를 사용할 줄 안다.다익스트라를 사용할 줄 안다.기존 다익스트라 알고리즘을 이용하되, 기준을 '꺾은 갯수' 로 표현한다.\-> 꺾은 개수는 4가지 dy,dx를 만들고(우,밑,좌,위) 바로 옆 방향으로 옮긴다면 꺾는다고 표현한다.(ex. 현재 위 방향인데 다음 방향