풀이이문제는 기존 dp문제처럼 1차원으로 점화식을 구하려면풀수가 없다.. dp문제는 꼭 1차원으로 점화식을 구하는게 아니다라는 걸 알려준 문제!dp 1, dp2, dp3에각각 1,2,3으로 끝나는 상황을 넣는다.ex)dp3은 2 1 1 2 3이 예시를 보면
https://www.acmicpc.net/problem/2225이 문제의 접근도 2차원리스트로 dp 리스트를 만들어 접근해야된다숫자 n을 k개의 숫자로 나타내는 갯수를 어떻게 알아낼것인가?이 생각을 30분정도 해도 떠오르지 않아, 무작정 귀납법 방법을 사용하
문제 문제 바로가기 풀이 위 문제를 보고 2가지 풀이 방법이 떠올랐다. 첫번쨰는 연산자 파이썬에서 지원하는 permutations 모듈을 이용하여 푸는 방법과, 하나는 DFS를 이용하여 (백트래킹) 최대, 최솟값을 구하는 방법이다. permutations 모듈을 사용
백준 14500 테트로 미노이 문제를 처음 봤을 땐, 일반적인 DFS문제라고 생각했다. 완전탐색으로 탐색하고, 테트로미노는 정사각형 4개 임으로, 조건문 조건 걸고 진행하였지만 이 방식으론 문제를 풀수 없었다,,,일반적인 DFS랑은 접근하면 테트로미노 모양중 'ㅗ' 모
16197\. 두 동전 바로가기이 문제는 두 동전중 , 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성해야 한다.사용 알고리즘 : BFS 최단 시간 알고리즘input 받으며 두 동전의 위치 좌표를 받는다.(x, y, xx, yy)
문제 풀기 : 12100번한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시킨다.같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다.한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서
문제 16928뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩
문제 링크총 돌의 개수는 고정이다(3개로 고정입니다) 총 돌의 개수가 3의 배수가 아니라면 어떤 수를 쓰더라도 모든 그룹에 있는 돌의 개수를 같게 만들 수 없다.(이게 포인트!)먼저 이 문제는 돌의 총합이 3의 배수가 되지 않으면, 어떠한 방식을 써도 모든 그룹에 돌의
문제 보러 가기N×M의 행렬로 표현되는 맵에서 0은 이동할 수 있는칸, 1은 벽(이동할 수 없는 칸)을 나타낸다.단, 벽을 부수고 이동할 수 있는 기회가 1번 주어지므로 부셨을 때 이동경로가 짧아진다면 부셔도 된다.(1, 1)에서 시작하여 (N,M)까지 가는데 최단거리
문제 보러 가기이전에 벽 부수고 이동하기를 풀어서 대부분의 로직은 똑같았다.앞서 이전에 푼 벽 부수고 이동하기는 벽을 딱 한번 부실수 있었는데, 이 문제는 k번 부실수 있어 3차원 배열을 만드는 것이 아니라 입력되는 k에 따라 차원을 만들면 된다.그후 k번 벽을 뚫을
문제바로가기해당 문제는 8\*8 체스판이 존재하고, 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 이 문제의 특징은 벽이 움직이고(1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고) 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동 여부를 구하는 것벽이 한 칸 내
오늘은 코테에 가끔씩 나오는 힙을 사용하는 문제를 대비하기 위해 heap에 대해 알아보도록 하겠습니다힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면
https://www.acmicpc.net/problem/1202요약하자면, 첫줄에 N(보석 개수)와 K(가방 개수)가 주어지고, 다음에 N줄에 걸쳐 보석의 무게와 보석의 가격이 주어지며, 다음 K줄에 걸쳐 각 가방의 허용 무게가 주어집니다. 상덕이가 K개의
백준 12970먼저 해당문제는 특정 문자열에서 (A, B) 쌍의 개수를 구해야한다.예를 들어 ABBAABBB 라는 문자열에서 (A, B) 쌍의 개수를 구해봅시다.모든 A에 대해서 각 A 뒤에 있는 B의 개수를 구해서 더하거나 모든 B에 대해서 각 B 앞에 있는 A의 개
문제https://www.acmicpc.net/problem/1300문제는 이러하다.nxn 크기의 배열 a의 a\[i]\[j] = i x j 일때,a 배열의 모든 값들을 일차원 배열 b 에 넣고, 오름차순 했을 때 k번째에 위치한 b\[k] 를 구하면 된다.해
문제 바로가기 https://www.acmicpc.net/problem/4991업로드중..문제는 이러하다오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.방은 크기가 1×1인 정사각형 칸으
https://www.acmicpc.net/problem/9935업로드중..초기에는 stack의 자료구조를 활용하지않고, 파이썬 문자열 내장함수인 replace를 활용했다2 . replace를 활용할때, 최악의 경우 O($N^2$)가 되어 시간 초과가 발생했다
문제보러가기해당 문제는 4개의 톱니바퀴가 동일하게 존재하고, 입력으로 몇번째 톱니바퀴가 어느방향(시계 :1, 반시계:-1)으로 움직일지 주어지면 해당 입력에 맞게 톱니바퀴가 움직이고, 다른 톱니바퀴들은 아래 그림과 같이 맞닿는 면의 극이 같으면 회전하지 않고, 다르다면
3190 문제 보러가기문제는 이러하다먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.만약 이동한 칸에 사과가 없다면, 몸길이를
문제 보러 가기해당 문제는 간단하다. 배열 A에서 행의 갯수가 >= 열의 갯수보다 많으면 -> R연산()3,1,1 ->(R연산 수행) 3,1,1,2A에서 열의 갯수가 >= 행의 갯수보다 많으면 -> C연산()해당 수와 등장 횟수를 모두 넣어 정렬을 실행할 때, 체크할
문제 바로 가기 문제 설명 알고리즘 : DP 제곱 반복 수행 -> 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용 -> DP로 풀 수 있다는 것을 알 수 있다. 단순하게 구현으로 이중 for문으로 구현할수있지만, 이 문제는 시간제한 0.5초로 파이썬이
문제바로가기각각의 과목은 매학기 개설되며 한 학기에 들을수있는 과목수는 제한 x\-> 만약 선수과목이 없다면 한번에 모드과목을 수강 가능각각 과목들의 선수 관계 표현-> 위상정렬 이용(defaultdict)그리고 선수과목이 없는 과목들은 큐에 넣어준다(앞에 진입하는
https://www.acmicpc.net/problem/11438문제 : 11438번(lca2)스스로 풀었는가? : x (시간복잡도 N\*M인 코드로 풀어 시간 초과)동빈나님의 강의를 참고했습니다!!lca 강의https://www.youtube.co
해당 문제는 크루스칼 알고리즘을 통해 최소 비용 신장 트리를 구하는 것입니다.크루스칼 알고리즘이란 가장 적은 비용으로 모든 노드를 연결하는 알고리즘입니다.추가적으로 알고리즘 이해가 필요하신 분은 나동빈님 크루스칼 알고리즘보고 오시는 걸 추천드립니다!!크루스칼 알고리즘
[이중운선순위큐] (https://school.programmers.co.kr/learn/courses/30/lessons/42628) 문제 풀러가기 🔎 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. | 명령어 |
👉문제 링크 클릭n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는