Barbera

https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 문제 C++ 풀이입니다. 필요한 배경지식 누적합 참고하면 좋음 : 누적합의 확장, imos법 문제 해결 방법 문제에서 skill을 통해 ..

https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 2022 KAKAO BLIND RECRUITMENT 양과 늑대 문제 C++ 풀이입니다. 필요한 배경지식 BFS, 비트마스킹 문제 해결 방법 그래프나 트리문제에서 BFS나 DFS을 풀이방법으로 생각해 볼 수 있는데,..

https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 2022 KAKAO BLIND RECRUITMENT 양궁대회 문제 C++ 풀이입니다. 필요한 배경지식 DFS, 백트래킹, 조합론 문제 해결 방법 문제를 풀면서 고려해야할 사항들이 많지만, 기본적으로 k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니라 k점만 가져가는 것 그리고 상대보다 한개라도 많이 맞추어야 점수를 획득할 수 있다는 점에 유의해야 한다...

스택(Stack)과 큐(Queue)가 무엇인지, 더 나아가 덱(Deque) 그리고 우선순위 큐(Priority Queue)와 힙(Heap)에 대해서 알아보자. 스택 (Stack) 후입선출(Last In First Out)의 자료구조 가장 나중에 삽입된 데이터가 먼저 삭제된다. Linked List를 이용하여 구현하면 쉽다. 가장 위에 있는 데이터가 위치한 곳을 Top이라고 한다. Top을 통해 데이터를 삽입하는 연산을 push , 삭제하는 연산을 pop이라고 한다. 큐 (Queue) 선입선출(First In First Out)의 자료구조 먼저 삽입된 데이터가 먼저 삭제된다. Linked List를 이용하여 구현하면 쉽다. 삭제연산이 수행되는 곳을 Front, 삽입연산이 이루어지는 곳을 Rear 또는 Ba..

https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 문제 해결 방법 동전의 순서는 중요하지 않으므로 동전별로 차례대로 K원을 몇개나 만들 수 있는지 다이나믹 프로그래밍 하면 된다. 문제에서 주어진 입력으로 예를 들어보겠다. dp[K]를 'K원으로 만들 수 있는 동전조합의 수' 라고 할때 먼저 base case로 dp[0] = 1 을 정의할 수 있다. ('0원을 만들 수 있는 경우는 한가지'라고 인..

https://www.acmicpc.net/problem/10564 10564번: 팔굽혀펴기 각각의 테스트 케이스에 대해서, 동혁이가 응원하는 팀이 득점한 점수의 최댓값을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다. www.acmicpc.net 1년전쯤 한창 DP문제를 풀며 자신감에 차 있을때 풀다가 벽을 느끼며 포기했던 문제였다. 이제는 풀 수 있을것 같아서 도전해 봤는데, 쉽진 않지만 생각하는 대로 문제가 풀리니 뿌듯했다. 필요한 배경지식 다이나믹 프로그래밍 BFS 문제 해결 방법 배낭문제(Knapsack Problem) 풀듯이 문제를 해결했다. 득점의 종류를 이용하여 나올 수 있는 총 팔굽혀펴기의 수를 탐색하는 방법이다. bool dp[i][j] : 총 i점일때 j번 팔굽혀펴기가 가능한가 ..

https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 조합론 - 파스칼 항등식 문제 해결 방법 N=2, M=2 일때 나올 수 있는 문자열을 사전순으로 나열하면 다음과 같습니다. 1번째 문자열 : aazz 2번째 문자열 : azaz 3번째 문자열 : azza 4번째 문자열 : zaaz 5번째 문자열 : zaza 6번째 문자열 : zzaa 문제에서 K=2로 주어진다면 2번째 문자열인 azaz를 출력해야 합니다. 어떻게 출력해야 ..

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 필요한 배경지식 다익스트라 or BFS DP 문제 해결 방법 이모티콘 N개를 만들기 위한 시간의 최소값을 출력하기 위해 다음과 같은 DP배열을 사용했습니다. dp[N][C] = 현재 이모티콘이 N개이고 클립보드에 저장된 이모티콘의 개수가 C개 일때, 필요한 시간의 최솟값 이렇게 정의하면 3가지 연산에 대하여 다음과 같은 식이 성립합니다. 현재 이모티콘의 개수가 n, 클립보드에 복사된 이모티콘의 개수..