성공을 즐기자

와 정말 복잡한 구현이다. 이 문제를 많이 풀면 구현능력이 생길것같다. 자주 풀어보자. 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(): # 중앙..

BFS를 맨날 이차원 리스트에서만 보다가 이렇게 문자열에서 처리하는 문제를 보니 참 신박하다. vis를 set으로 하여 방문여부를 확인하였다. set은 튜플형태로만 add가 된다. (list는 안됨) 덱에 [n,0]와 vis에 [n,0]이 넣어지면서 시작한다. n은 현재 숫자이고 0은 변경횟수를 의미한다. 1. 덱이 있는 동안 반복한다. 1-1 . 덱에서 왼쪽에 있는 값을 꺼낸다. 1-2. 만약 변화 횟수가 K라면 ans를 갱신한다. 1-3. int는 []으로 접근할 수 없으므로 str -> list로 만들어 하나씩 접근할 수 있도록 만든다. 1-4. 이중 for문을 돌면서 변경할 수 있는 모든 경우를 다 본다. 1-5. 첫번째 자리가 i이고 j의 값이 0인 경우 continue한다. 첫번째 자리에 0이..

이 문제는 비트마스킹을 사용해 푼다. 이해하면 어렵지는 않은데 처음에 이해하기가 까다로웠다. 비트마스킹 관련 포스팅은 https://what-am-i.tistory.com/348 1 : 가로 (우측) 0 : 세로 (아래) 로 생각해서 푼다. 종이는 각 칸마다 가로로 자르거나 세로로 자르는 방법만 있으므로 모든 자리에는 2가지의 상태가 존재한다. 모든 칸의 개수는 n*m이고 각각 2가지씩 방법이 있으므로 2^(m*n)가지가 존재한다. 이것을 비트마스크로 1

코테에 유니온파인드가 나오나...?라는 의구심을 품고 푼 문제 유니온 파인드 문제를 처음 풀어봐서 주석을 많이 달아놨다. 이 문제를 푸는 방법은 끊을 간선을 제외한 모든 간선을 먼저 연결하고 끊을 간선들을 역순으로 하나씩 연결한다. 배열의 부모노드의 값은 음수로 집합의 개수가 저장되어있다는 것이 중요하다. 처음 배열은 -1로 초기화한다. edges,div로 연결할 리스트와 제거할 리스트를 입력받는다. 연결할 리스트의 개수만큼을 돌면서 제거될 연결이 아니라면 연결해준다.(union) answer 변수를 0으로 초기화한다. 제거할 연결을 역순으로 union한다. union은 각 집합의 개수의 곱을 반환하므로 반환값을 answer에 더한다. answer을 출력한다. ; 각 원소를 연결해주고 두 그룹의 크기의 ..

처음에 정직하게 풀려고 했으나 계속 시간초과가 발생했다. 역시 사람이 머리를 써야 문제가 풀린다. 이 문제는 3가지로 상황을 나누어 풀어야한다. 1. 회문일 경우 -> 전체 길이 -1 1-2. 회문인데 전부 똑같은 문자열 일경우 -> -1 2. 회문이 아닐 경우 -> 전체 길이 코드 : # 팰린드롬인지 확인 def palin(search) : for i in range(len(search)//2) : if search[i] != search[-(i+1)] : return False return True # 전부 같은 문자열인지 확인 def same(search) : for i in range(1,len(search)) : if search[i] != search[0] : return False retur..

딱히 어렵다고 생각되지는 않았다. 상어가 벽에 충돌할 때 구현하는 법만 안다면 쉬운 문제였으나 그 방법을 생각 못했다. 따로 수학공식이 있을 것이라 생각하고 계속 생각해보려고 했는데 못찾았다. 답을 찾아보니 간단하게 방향만 바꿔주고 가야할 길이를 줄이지 않으면 해결되는 것이었다. 이 문제를 통해 배웠으니 다른 문제에서 만나면 사용하자. 추가로 문제가 분명히 맞는데 자꾸 틀리다라고 떠서 한참을 봤다. 그 이유는 처음 입력받은 r,c를 상어 위치하면서 똑같은 변수에 r,c를 받아서 다른 값으로 변경되었었기 때문이다. 입력받는 변수이름을 주의하자. 1,2,3,4가 상 하 우 좌이다. 이를 0부터 시작하도록 변경하여 그리면 이렇다. 0과 2의 경우 반대 방향으로 가려면 1을 더하면 되고 1과 3의 경우 반대 방..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 코드 : N,K = map(int,input().split()) items = [] dp = [0 for _ in range(K+1)] for i in range(N): w,v = map(int,input().split()) for j in range(K,w-1,-1): dp[j] = max(dp[j],dp[j-w]+v) print..

뭐 이런 문제가 있냐.... 한번에 이해가 잘 안된다. 계속 풀어봐야겠다. 코드 : if __name__=="__main__" : n,L = map(int,input().split()) l=lgap=rgap =0 ant =[] for i in range(1,n+1) : p = int(input()) if p

기울기를 사용한다는 건 생각도 못했다. 그림으로 그려보았다. 건물의 왼쪽은 건물이 보이기 위해서는 기울기가 작아져야하고 건물의 오른쪽은 건물이 보이기 위해서는 기울기가 커져야한다. 이걸 생각만 할 수 있다면 그렇게 어려운 문제는 아니다ㅎㅎ 코드 : # 원점이 (x1,y1) def slope(x1,y1,x2,y2) : return (y2-y1) / (x2-x1) # 기울기가 작아져야 볼 수 있다. def count_left(idx) : min_scope = int(1e9) cnt= 0 for i in range(idx-1,-1,-1) : s = slope(idx, mp[idx], i, mp[i]) if min_scope > s : min_scope = s cnt+=1 return cnt # 기울기가 커야 ..

으렵다!! 그래도 계속 풀다보면 익숙해지겠지 이차원 배열을 뒤집어야하는데 이 문제를 풀면서 포스팅을 작성했다. 참고 : https://what-am-i.tistory.com/330?category=1000199 [python]이차원 배열을 뒤집는 방법_zip(*list) 알고리즘을 풀다보면 이차원 배열을 뒤집어야하는 문제가 가끔 나온다. 그럴때마다 그때 그때 이해해서 적었지만 이것을 정리하고 싶어서 글을 쓴다. 1. " * " python에서 아스트리크(*)은 unpack역할 what-am-i.tistory.com 크기가 가장 큰 블록을 찾을 때 여러 개라면 무지개 블록의 수가 많은 그룹, 무지개 블록의 수도 동일하다면 기준 블록의 행과 열이 가장 큰것을 찾는다. (즉, 1. 크기, 2. 무지개 블록의 ..