yeony's story

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)

정렬을 이용하여 풀었던 문제 min함수 내에서 for문을 또 따로 돌려서 최단 거리를 찾아내고 최단 거리가 여러개일 경우엔 아무거나 선택된다. n = int(input()) array = [list(map(int, input().split())) for _ in range(n)] # 정렬, min(거리) array = sorted(array, key=lambda x: x[1]) answer = 0 for i in range(len(array)): answer += min([abs(array[x][0] - array[i][0]) for x in range(n) if x != i and array[x][1] == array[i][1]]) 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번 아이스크림과 선택될 수 없다. 이 코드의 핵심..

처음에는 행은 행 따로 열은 열 따로 체크를 해줘야겠다라는 생각이 떠올랐다. 행은 x가 아예 없는 행의 개수를 세어주고 마찬가지로 열도 x가 아예 없는 열의 개수를 세어준다 이렇게 구한 개수중에 큰 값을 출력해주면 된다. 모든 행과 열에 최소한 한 명 이상의 경비원이 배치되어야 한다. 지금 위에서 구한 건 행과 열마다 각각 배치되어야할 경비원의 수를 구한것이다. 만약 행에 있어야할 경비원의 수가 2이고 열에 있어야할 경비원의 수가 3이라고 하자. 문제에서는 모든 행과 열에 경비원이 있어야한다고 했으니까최소한 3명이 있어야 위 조건을 만족할 수 있다. 따라서 max함수를 이용해서 구해주는 것이다. n, m = map(int, input().split()) array = [input() for _ in ra..

보자마자 조합을 써야하는 문제인가 싶었다. 일단 집 위치와 치킨집 위치를 각 배열에 정리해주었다. 탐색하기 편하도록! combinations 함수를 이용하여m개의 치킨집 경우의 수를 뽑아낸다. 도시의 치킨거리가 가장 작게되는 경우의 수를 구하는 거니까.min함수를 이용해야 한다. answer의 초기값은 int형 max값으로 설정 (1 * 10^9)만약 answer의 값이 sum보다 크다면answer에는 sum값을 집어넣어주면 된다. from itertools import combinations n, m = map(int, input().split()) array = [list(map(int, input().split())) for _ in range(n)] houses = [] chickens = [] ..

문제에 나와있는 순서대로만 구현하면 풀리는 문제! 빈칸 : 0, 벽 : 1, 청소한 칸 : 2로 구분하였다. 처음에는 청소한 구역도 1로 처리했는데 이렇게 하면 2번의 c,d조건을 판별할 수 없었다. 그리고 1번이랑 2번을 각각 독립적으로 움직이게끔 하는 과정이 살짝 버거웠다 ㅎ.. 그리고 % 연산자를 활용해야 하는 부분을 잘 기억해야한다.. 매번 헷갈리지만 ^0^ 왼쪽 방향으로 돌릴 땐 (d+3)%4로 해주면 되는데, d에 3을 더하는 이유에 대해 알아야 앞으로도 사용해먹을 수 있을 것 같아서 상세하게 풀어써보기! 방향은 0, 1, 2, 3 이렇게 있다. 3에서 왼쪽으로 움직이면 2가 되어야하는데 이때는 -1을 해주면 된다. 그러나 문제가 있다. 0에서 왼쪽으로 움직이면 방향은 3이 되어야한다. 그래서..

백트래킹을 사용하여 풀어나간 문제! 이번에는 방문하는 노드 체크 과정을 빼먹지 않고 잘 했다! for문에서 시작점 부분을 함수 매개변수로 넘겨주는 부분을 설정하지 않아서 애먹었던... cnt가 6 => 즉, 6개의 숫자를 모두 뽑아낸 경우에는 그 숫자들을 모두 출력한다. print(*array)를 하게 되면, 배열 형식으로 출력되지 않고 1 2 3 4 5 6 이런식으로 출력된다! # k=array[0] # array[1]~array[7] = 원소 배열 def dfs(array, cnt, temp, i): k = array[0] if cnt == 6: print(*temp) return for i in range(i, k + 1): if visited[i]: # 방문한 노드 continue visited[..

오랜만에 bfs 문제를 접했다..! 역시나 오늘도 헤맸다 !.! 문제 해석하기 1 4 2 2 1 (시작점 idx 2 ) 2 -> 왼쪽 1 o -> 오른쪽 4 o -> x -> 오른쪽 1 o -> 왼쪽 2 o -> 왼쪽 4 o o의 개수 = 5개 from collections import deque n = int(input()) array = list(map(int, input().split())) start = int(input()) - 1 visited = [0] * n result = 0 def bfs(start): # start=idx global result queue = deque() queue.append(start) visited[start] = 1 result+=1 while queue: ..

보자마자 백트래킹이 떠올랐던 문제! 백트래킹의 원리는 이해했는데 자꾸 방문처리 체크하는 부분을 빼먹어서 애를 먹는다; 백트래킹 dfs(depth,now): if depth==n: return #함수 종료 for i in range(n): if visited[i]: continue visited[i]=1 dfs(depth+1,now) visited[i]=0 문제를 풀긴 풀었는데 시간이 7140ms..? 허허.. 최대한 필요 없는 과정 제외했다고 생각했는데 ㅠㅠ... s_team에는 스타트팀에 들어간 팀원의 번호 t_team에는 링크팀에 들어간 팀원의 번호를 넣었다. func함수에서 각 팀의 능력치를 계산하고 최소인지 아닌지 판별하여 answer에 값을 넣는다. n = int(input()) s = [lis..

딱 보자마자 완탐하면 시간초과날 것 같은 느낌.. 조건을 보니 수가 작지 않았기 때문 (사실 아직 정확하게 구분하지는 못하는데, 느낌상 알 수 있었다..) 그래서 완탐 대신 투포인터로 풀었다 left , right 인덱스를 이용하여 풀었다. 2 7 4 1 5 3 위 리스트를 일단 오름차순으로 정렬한다. 1 2 3 4 5 7 left는 맨 왼쪽 > 배열[0] right는 맨 오른쪽 > 배열[n-1] array[left]+array[right]의 값이 M보다 작으면? left를 오른쪽으로 한칸 이동 시킨다. 만약 M보다 크거나 같다면? rigth를 왼쪽으로 한 칸 이동시킨다. 그리고 M과 같다면 answer+=1 n = int(input()) # 재료 : n개, M (두 재료의 번호를 합쳐서 M이 되어야 갑..

보자마자 lambda 함수로 정렬해놓고 나라 번호 저장하는 배열 하나 만들면 우선순위도 해결되겠다고 생각하며 풀기 시작했다. lambda를 매번 까먹는 1인.. array=sorted(array,key=lambda x:x[2], reverse=True) [a,b,c] -> c 기준으로 내림차순 정렬 만약 answer의 길이가 3개가 되면 이미 금은동이 정해진 거니까 반복문에서 빠져나온다. 시간 : 84ms..? 거의 맨 끝이다.. 고수님들의 코드를 한 번 탐색하러 가봤다! n = int(input()) # lambda로 정렬 array = [list(map(int, input().split())) for _ in range(n)] array = sorted(array, key=lambda x: x[2],..

최대한 반복문을 줄이고자 했던 나의 노오력.. temp값이 1이면 반복문 1번 2이면 반복문 2번 이런식으로 answer 배열에 값을 채워넣었다! [1,2,2,3,3,3...] 그래서 answer 길이가 끝을 나타내는 정수(입력값)보다 커지면 반복문을 종료하고 합을 도출해내는 방식으로 구현하였다. f, e = map(int, input().split()) temp = 1 answer = [] while len(answer) < e: for _ in range(temp): answer.append(temp) temp += 1 print(sum(answer[f-1:e]))

아스키코드, chr(), ord()를 이용하면 풀 수 있었던 문제! ord(문자) -> 숫자 ord(A) -> 65 ord(a) -> 97 chr(숫자) -> 문자 chr(65) -> A 알파벳 개수는 26개 temp = input() answer = '' for idx, i in enumerate(temp): i = ord(i) if 65

초기 max값은 1 * 1e9 초기 min값은 -1*1e9 이 문제는 백트래킹 개념을 사용하면 풀 수 있다. for문을 돌려서 해야하나 잠시 고민했는데 재귀함수만 이용해도 충분히 가능했던 문제! (아직 재귀함수 사용하는 게 서투른 편..) + , - , * , / 순으로 if문 작성 (주의해야 할 부분) 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 나는 temp가 음수일 때, 양수일때를 나눠서 처리해줘야하는 줄 알았다. 그러나 파이썬 연산자만 잘 활용해도 충분히 간단하게 풀 수 있었다. 파이썬 연산자에서 나눗셈을 담당하는 연산자는 총 3가지 1. / : 나누기 2. // : 나누기 ..

아휴 이 문제는 이해하는 것부터 힘들었다 ^.^; 말장난에 놀아난 1인.. 나야 나.. visited를 1차원 배열로 하려고 했는데 계속 오류가 났다 결국 더 보기 편하게 2차원으로 걍 쪼개버렸다 A B C 친구가 있다. 2-친구가 되기 위한 조건은 총 2가지 1. A, B가 서로 친구 or 2. A와 C, B와 C가 친구인 경우 아래 예시로 살펴보면 A와 B가 친구 -> 2-친구 조건1 만족o A와 C가 친구 x -> 조건1 만족x, 그러면 조건 2를 살펴본다. A와 B가 친구이고 C와 B가 친구이므로 A와 C도 친구가 될 수 있다. -> 조건2 만족o ** fucn 함수 안에 있는 조건문에서 인덱스 순서가 바뀌어도 상관 없었다 A->B랑 친구이면 B->A도 친구이기 때문! # 두사람이 친구 or (A..

역시나 처음에 조합부터 떠오른 1인.. 하지만 시간 초과 뜰 게 뻔해서 dp로 다시 방향을 바꾸었다! 이 문제는 피보나치 수열과 매우 유사하다. n=1일때 1개 n=2일때 2개 n=3일때 3개 (1+2) n=4일때 5개 (2+3) dp[n]=dp[n-1]+dp[n-2] 그래서 간단하게 답을 도출해낼 수 있었다. 정답코드는 아래와 같다 n=int(input()) dp=[0] * 1000001 dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=(dp[i-1]+dp[i-2])%15746 print(dp[n]) 위 코드 같은 경우에는 시간이 473ms가 떠서 더 좋은 방식이 있나 찾아봤더니 행렬곱셈을 이용하여 피보나치 수열을 하게 되면 더 빠르게 값이 도출된다는 것을 알게 되었다...

처음 생각해냈던 풀이는 시간초과가 났다. 백트래킹 방식으로 풀어봤는데 모든 경우의 수를 탐색해서 그런가보다 :( 그래도 ide에서 돌리면 값은 나오긴 하지만 시간 초과 문제를 해결해야 정답을 인정받을 수 있으므로 다른 방식으로 코드를 작성했다. # n = int(input()) # n

덱을 이용해서 양방향 배열 구현하기 연산의 종류 3가지 1. 첫 번째 배열 원소 빼내기 2. 왼쪽으로 배열 이동 3. 오른쪽으로 배열 이동 while i != array[0]: array.appendleft(array.pop()) cnt += 1 array.popleft() while문이 끝난 뒤 array.popleft()를 붙여주지 않아서 한동안 헤맸다! 문제 풀기 전에 미리 설계를 해두고 코드를 짜는 습관을 들여보자 :).. from collections import deque n, m = map(int, input().split()) array = deque([i for i in range(1, n + 1)]) location = list(map(int, input().split())) cnt =..