성공을 즐기자

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 왼쪽 전봇대 번호 순으로 정렬을 한 후 오른쪽 전봇대의 가장 긴 증가하는 순열의 길이를 구하면 된다. 구한 순열의 길이는 겹치지 않고 설치할 수 있는 전깃줄의 길이이므로 전체 전깃줄의 개수에서 구한 길이를 빼주면 제거해야하는 전깃줄의 길이가 나온다. 코드 : if __name__=="__main__" : n = int(input()) arr = [list(map(int,input().split()))fo..

점수를 저장할 score 리스트 , dp값을 저장할 리스트를 만든다. 들어오는 계단의 개수가 1,2,3 일때는 하드코딩을 해준다. 그 이상일 때는 for문을 돌면서 dp 배열을 채워준다. 조건에는 한 계단 혹은 두 계단씩 오를 수 있다는 조건이 있다. 그리고 마지막 도착 계단은 반드시 밟아야 한다. 마지막 계단을 밟고 2단계 이전 계단을 밟는 경우와 (score[i] + dp[i-2] ) 마지막 계단과 바로 이전 계단 그리고 2단계 이전 계단을 밟는 경우가 있을 수 있다. (score[i] + score[i-1] + dp[i-3]) 코드 : if __name__=="__main__" : score = [] dp = [] l = int(input()) score.extend(list(int(input())..

🐾 20220917 행복하고 재밌는 DFS 문제다. ^^ 1,2,3,4 CCTV 마다 볼수있는 방향이 다르다. 이를 미리 cctv_dir으로 설정해 놓는다. 1. 주어진 그래프를 돌면서 cctv가 있는 곳의 위치와 번호를 저장한다. 2. DFS에 그래프와 횟수를 인수로 넘긴다. 2-1. 종료 조건은 모든 cctv를 탐색한 경우이다. 2-2. 현재의 그래프와 동일하지만 객체는 다른 지도를 만든다. (원본 배열의 보존을 위해) [copy.deepcopy이용] 2-3. cctv의 타입에 따라 갈 수 있는 방향을 돌면서 감시가능 영역을 설정한다. 2-4. DFS를 이용해 재귀적으로 탐색할 수 있도록 만든다. 2-5. 원본 배열에서 deepcopy를 통해 감시 전으로 돌아갈 수 있도록 만든다. CCTV를 발견할 ..

완탐으로 열심히 풀어봤지만 결과는 메모리초과..시간 초과...... 문제의 분류를 보니 수학이었다. 역시 완탐이 아니라 머리를 써서 공식을 알아내야하는 문제다. 코드 : def cal(num) : if num ==0 : return 0 elif num == 1 : return 1 elif num %2 ==0 : return num // 2 + 2*cal(num//2) elif num %2 == 1 : return num //2 + 2*cal(num//2) +1 if __name__=="__main__" : a,b = map(int,input().split()) print(cal(b) - cal(a-1)) 이런 수학 문제가 코테에 나오나...... 참고 블로그 : https://dkrnfls.tistory..

완탐인가 했는데 완탐은 맞다. 다만 아이디어를 곁들인... 대체 이런 아이디어는 어떻게 떠올리는지 궁금하다. 1. 먼저 행별로 0의 개수를 구한다. 2. 조건에 부합한 행을 찾는다. 2-1. 0의 개수가 k(변환 횟수)보다 크다면 k번을 다 뒤집어도 다 켜질수가 없으므로 첫번째 조건은 0의 개수가 k보다 작거나 같다. 2-2. 그리고 두번 째 조건은 0의 개수가 짝수라면 k도 짝수 , 0의 개수가 홀수라면 k도 홀수여야한다. 그 이유는 k 보다 작은 0들을 모두 1로 바꾼 다음 남은 k의 값이 짝수여야만 불이 켜진 상태를 유지할 수 있기 때문이다. 만약 0이 짝수고 k도 짝수라면 k의 개수에서 0을 빼면 남는 값은 짝수이다. 만약 0이 홀수고 k도 홀수라면 k의 개수에서 0을 빼면 남는 값은 짝수이다. ..

🐾 20220923 처음 DFS로 풀었다가 recursion Error로 까였다. 이렇게 생긴문제는 유니온파인드를 꼭 생각해서 풀어야겠다. 간단하게 유니온 파인드를 정리해서 포스팅 해봤다. https://what-am-i.tistory.com/371?category=1000199 [python]유니온파인드 알고리즘_이것도 알아야해? 유니온 파인드 : 노드를 UNION하고 부모를 FIND해서 서로소 집합을 찾아내는 알고리즘 UNION연산은 두 원소를 뽑아 원소가 포함된 집합의 부모노드를 비교한다. 만약 다르다면 같은 부모를 가리키도 what-am-i.tistory.com 1. 입력받은 도시의 연결 여부를 이용해 서로소 집합을 만든다. 1-2. UNION - 부모 노드를 구해 비교한다. 다르면 동일하도록 만..

복습 : 🎉 20220911 🐾 20220916 백트래킹 문제인데 숫자들을 상하좌우 각각 구분해서 다르게 합쳐주는 코드를 만드는 것이 쉽지않았다. 밑 그림과 같이 블록을 확인하면된다. 그 이유는 곰곰히 생각하면 알 수 있다. 상은 위로 블록들을 올리는데 동일한 값의 블록을 찾아야하고 이동하려는 쪽의 칸이 먼저 합쳐지기때문에 위에서 아래로 탐색한다. 좌를 설명해보면 왼쪽으로 블록을 옮기므로 블록이 합해지는 것이 왼쪽에서 오른쪽으로 탐색해야한다. 코드 : from collections import deque import copy def get(i,j) : if mp[i][j] : q.append(mp[i][j]) mp[i][j] = 0 def merge(i,j,di,dj) : # 보드에 있는 칸들을 돌면서 ..

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 뭔가 DFS인것 같아서 DFS로 풀려고했는데 깊이가 너무 깊다고 까였다.... 정답을 찾아보니 다들 BFS로 풀이되어있었다. 최소시간을 구하다보니 그런것 같다. 최솟값 -> BFS 3가지의 연산이 있다. 1. 클립보드에 저장 2. 클립보드의 이모티콘 화면에 저장 3. 화면의 이모티콘 하나 삭제 화면에 있는 이모티콘과 클립보드에 있는 이모티콘의 개수, 그때의 시간 이 3가지의 값을 저장하기위해서 2차..

이 그림처럼 주사위를 기본으로 생각하면 된다. 다만 위치는 해당 값 -1으로 3은 동쪽을 1은 아래 쪽을 가리킨다. 처음에 이 기본 주사위의 1이 천장에 있는 줄 알고 풀었다가 시간을 오래 끌었다. 기본 주사위 굴리기 문제에서 BFS가 추가된 문제이다. 해당 주사위 칸에서 BFS를 돌려 숫자가 같은 것의 개수와 해당 주사위 칸의 값의 총합을 출력하는 문제다. 위 그림에서 0이면 오른쪽으로 돌려서 생각해보면 된다. 위 그림에서 오른쪽으로 돌리는 주사위로 변한 위치를 대입해준다. [리스트는 0-index이기 때문에 1을 빼준다.) 그러면 5와 2는 그대로이므로 4631 (기본) -> 1463 이 된다. 각각 1을 빼주면 3520 -> 0352가 된다. 그게 바로 밑 코드의 dir == 0인 경우다. 코드 :..

와 정말 복잡한 구현이다. 이 문제를 많이 풀면 구현능력이 생길것같다. 자주 풀어보자. 1. 입력된 그래프를 일렬로 만들어 deque 형태로 저장한다. (indexing 함수) 2. m번 만큼 magic_shark를 호출한다. 2-1. dir방향으로 s만큼 0으로 만들어준다. 2-2. fill_blank 함수로 0을 채워준다. 2-3. 연속된 구슬이 4개 이상 있다면 터뜨린다.(bomb 함수) 터뜨리면서 개수를 저장한다. 2-4. 터지는 구슬이 있는 동안 fill_blank함수를 호출한다. 2-5. grouping 함수로 개수와 숫자로 구슬을 덮어준다. 3. 저장된 터뜨린 구슬의 개수를 계산하여 출력한다. 코드 : from collections import deque def indexing(): # 중앙..