성공을 즐기자

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..

기울기를 사용한다는 건 생각도 못했다. 그림으로 그려보았다. 건물의 왼쪽은 건물이 보이기 위해서는 기울기가 작아져야하고 건물의 오른쪽은 건물이 보이기 위해서는 기울기가 커져야한다. 이걸 생각만 할 수 있다면 그렇게 어려운 문제는 아니다ㅎㅎ 코드 : # 원점이 (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. 무지개 블록의 ..

간단하게 보면 1. 얼음을 회전시키고 녹이는 함수 2. 가장 큰 얼음 덩어리의 사이즈를 구하는 함수를 만들어 해결하면 된다. 문제는 얼음을 회전시키는 코드를 생각하기 쉽지않았다는 것이다. 2^L씩 구간을 나누어 시계방향으로 90도 회전하는데 이 방법을 도저히!!! 생각이 나지 않았다. 이걸 매번 tmp로 받아서 저장하고 빼서 만드나? 너무 구차한데? 아닐것같은데 ? 만약 tmp로 안빼고 만들면 숫자가 움직이는 과정에서 원래 숫자를 덮어버려서 안될텐데? 정답은 바로 새롭게 저장할 mp배열을 만드는 거였다^-^! (정말 획기적!) 2^L 만큼의 간격으로 x,y를 넘어다니고 그 안에서는 i,j로 90도 시계방향으로 움직이도록 만든다. 4중 for문으로 나타낸 그림은 아래 그림과 같다. 코드 : from col..

덱으로 이차원 리스트를 만들 수 있다는 것을 처음 알았다..!! 아직도 배울 것이 많다ㅎㅎ 이 문제를 푸는 방법은 그저-! 빡구현!! 할수있다!! 화이팅🔥🔥 1. 숫자들을 리스트 -> 덱으로 만들어 저장한다. 2. 덱으로 저장되어있으므로 rotate를 이용할 수 있다. 3-1. 양옆을 확인하여 동일한 값이 있는지 체크한다. 3-2. 위, 아래를 확인하여 동일한 값이 있는지 체크한다. 4-1. 동일한 값이 있으면 0을 넣는다. 4-2. 없다면 원판을 돌면서 평균을 구하고 원판을 돌면서 원판위 값을 조정한다. 코드 : from collections import deque if __name__=="__main__" : n,m,t = map(int,input().split()) mp = [deque(list(m..