yeony's story

처음엔 주어진 문자열을 암호화하는 줄 알고 구현을 해서 시간이 좀 걸렸다. 그러나 암호화되어 있는 문자열을 원래의 문자열로 출력하는 문제였던 것..! 열은 입력값으로 주어졌다 행은 전체 문자열을 열로 나눈 값으로 정했다. aei | jfb | cgk | lhd 1번째(aei) , 3번째(cgk)는 왼쪽 -> 오른쪽으로 판별해서 a는 array[0]에 넣고 e는 array[1]에 넣고 i는 array[2]에 넣는식으로 cgk도 넣어준다. 2번째 (jfb), 4번째(lhd)는 오른쪽->왼쪽순으로 각각의 값을 array 배열에 넣어준다. j는 array[2]에 넣고 f는 array[1]에 b는 array[0]에 그러면 array=[ [a,b,c,d], [e,f,g,i], [i,j,k,l], ] 이런식으로 자리..

dfs로 풀었던 문제! 모든 관광지가 연결되어 있으므로 양방향 그래프를 그려준다. 양방향 그래프를 구현하는 건 아래와 같이 구현해주면 된다. a와 b가 양방향으로 연결되어 있다는걸 구현하고자 한다면, a 인덱스에 b값을 넣고 b 인덱스에 a값을 넣어주면 된다. for _ in range(m): a, b = map(int, input().split()) # 양방향 그래프 array[a].append(b) array[b].append(a) 함수 fs 부분에서는 idx와 ans를 인자로 넘겨준다. 이때 visited 배열도 사용해서 방문했는지 체크한다. 만약 방문한 곳이 아니라면 dfs 호출! 방문한 곳이라면 아무런 작업 x import sys input=sys.stdin.readline t = int(inp..

이렇게 하니까 시간초과 ㅠ ㅠ 리스트의 경우에는 시간이 자료의 크기에 비례하여 늘어나지만 딕셔너리는 거의 일정한 시간으로 탐색을 완료한다. 따라서 리스트 대신 딕셔너리로 다시 구현을 해보았다. n=int(input()) array=[] for _ in range(2*n-1): person=input() if person not in array: array.append(person) else: array.remove(person) print(*array) person이 dic에 이미 이름을 올린 경우? -> dic에서 정보를 지운다 (마라톤 완주 성공한 사람이니까) dic에는 완주를 못한 사람만 남아있다. dic={key:value} key가 dic에 있는 걸 알고자한다면 if key in dic 조건문으..

뚜렷한 방법이 떠오르지 않아서 구하는 풀이를 직접 적어보고 찾아내었다. 위 예제로 생각해보았다. 행 = 8, 열 = 10 1번 상자 : 2 X 4 2번 상자 : 2 X (10-6) 3번 상자 : (3-2) X 4 4번 상자 : (3-2) X (10-6) 5번 상자 : (8-3) X 4 6번 상자 : (8-3) X (10-4) 행과 열을 각각 리스트로 받으면 행 = [0,2,3,8] 열 = [0,4,10] 행[i+1]-행[i] || 열[j+1]-열[j] 위 식을 이용하면 방금 풀었던 풀이대로 프로그램 구현이 가능해진다. sort() 과정은 필수 col, row = map(int, input().split()) rows = [0, row] # 행 cols = [0, col] # 열 for _ in range..

빙글빙글 움직일 때 위 1칸, 오른쪽 1칸, 아래 2칸, 왼쪽 2칸, 위 3칸, 오른쪽 3칸 ... 이동하는 걸 보면 규칙을 찾을 수 있다. 그래서 위, 오른쪽 처리는 upRight() 함수가 해주고 아래, 왼쪽 이동 처리는 downLeft() 함수가 처리해준다. 여기서는 dx,dy의 값을 반대로 뒤집어줘야함! 위로 올라가면 y의 값이 +1 되어야하고 아래로 내려가면 y의 값이 -1이 되어야하기 때문이다. n=int(input()) # 위, 오른쪽, 아래, 왼쪽 dx=[0,1,0,-1] dy=[1,0,-1,0] x=0 y=0 num=0 def upRight(): global x,y,n,num num+=1 for _ in range(num): # 위 x += dx[0] y += dy[0] n -= 1 if..

dp를 이용하여 푸는 문제 dp 할 때는 n+1, m+1의 배열로 만든다. 그래야 인덱스 처리를 따로 해주지 않아도 에러가 나지 않는다 :) array 배열 0 0 0 0 0 0 1 2 3 4 0 0 0 0 5 0 9 8 7 6 0 0 0 0 0 dp 배열 0 0 0 0 0 0 1+0 = 1 2+1 = 3 3+3 = 6 4+6 = 10 0 0+1= 1 0+3 = 3 0+6= 6 5+10=15 0 9+1=10 8+10=18 7+18=25 6+25=31 0 0 0 0 0 n, m = map(int, input().split()) array = [list(map(int, input().split())) for _ in range(n)] dp = [[0 for _ in range(m+1)] for _ in ra..

dfs로 푼 문제! 그냥 끝까지 탐색하고 더이상 탐색할 수 없으면 다시 돌아오면 그만! 바깥쪽에 해당하는 0번째 줄만 dfs문을 돌린다. 그리고 맨 마지막줄에 2가 있으면 안쪽까지 탐색이 되는거니까 YES를 출력해주면 되는 문제 그런데 이렇게 하니까 시간이 오래걸렸다 (1243ms) ㅠㅠ import sys sys.setrecursionlimit(3000000) m, n = map(int, input().split()) # m = 행, n = 열 array = [list(map(int, list(input()))) for _ in range(m)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def dfs(row, col): array[row][col] = 2 for i in ra..

최대한 왼쪽에 있는 값을 선택하게끔 해줘야 한다. 사실 idx 처리하는 부분에 있어서 고민을 좀 했는데 for문 안에 max, min 함수를 이용하면 손쉽게 처리가 가능하다는 것을 알게 되었다. n, k = map(int, input().split()) array = list(input()) answer = 0 for i in range(n): if array[i] == "P": # 사람 for j in range(max(i - k, 0), min(n, i + k + 1)): if array[j] == "H": answer += 1 array[j] = 0 break print(answer)

큰 정사각형에서 작은 정사각형을 빼주면 넓이를 구할 수 있다는 걸 발견하고 그 값을 구해서 K를 곱해주는 방식으로 구현을 하였다. 작은 정사각형의 넓이를 구하는 과정에서 살짝 헤맸으나 최장길이의 값의 인덱스를 활용하면 금방 구할 수 있다. k = int(input()) array = [list(map(int, input().split())) for _ in range(6)] longW = 0 longH = 0 longWidx = 0 longHidx = 0 shortW = 0 shortH = 0 # 왼쪽 : 2, 오른쪽: 1, 위 : 4, 아래 : 3 # longW => 왼쪽, 오른쪽 탐색 # longH => 위, 아래 탐색 for idx, temp in enumerate(array): if temp[0]..

이 문제를 보자마자 dfs로 풀어야겠다고 생각함. 일단 조합하면 안되는 숫자들은 딕셔너리에 저장했다. 1->2인 경우 서로 선택하면 안되는거니까 딕셔너리에 각각 값을 넣어주었다. * 딕셔너리 value값 여러개일 때 처리해줘야 하는 방법 * 딕셔너리의 value값이 여러개일 경우 dic[i] = []로 초기화하고 값은 append를 이용해서 넣어주면 된다. 아이스크림이 총 5개 있다. 1 2 3 4 5 그 중에 3개의 아이스크림을 선택하는 경우의 수를 구하는 문제이다. 근데 조합해선 안될 아이스크림들이 있다. 1번,2번 아이스크림 3,4번 아이스크림 1,3번 아이스크림 -> 즉 1번 아이스크림은 2번,3번과 같이 선택될 수 없다. 2번,3번 아이스크림도 1번 아이스크림과 선택될 수 없다. 이 코드의 핵심..