성공을 즐기자

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 - 부모 노드를 구해 비교한다. 다르면 동일하도록 만..

유니온 파인드 : 노드를 UNION하고 부모를 FIND해서 서로소 집합을 찾아내는 알고리즘 UNION연산은 두 원소를 뽑아 원소가 포함된 집합의 부모노드를 비교한다. 만약 다르다면 같은 부모를 가리키도록 만든다. FIND 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 부모노드를 찾아 반환하게 만들면 전부 돌면서 찾아야하는 수가 있다. (시간이 너무 오래걸릴수도) 그래서 일일이 거슬러 부모노드를 찾는 것보다 한번에 빠르게 부모 노드에 갈 수 있도록 하는 경로 압축기법을 사용하면 빠르다. 코드 : def union(a,b) : a = find(a) b = find(b) if a > b : parent[a] = b elif a ..

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(): # 중앙..