Breath everything

이것 저것

카테고리 없음

1. 생각 정리 그림만 보면 되게 복잡한 것 같지만 파이프의 끝부분이 가리키는 좌표 이동하는 느낌으로 생각하면 될 듯 이전 단계에서 어떤 방향으로 움직였는지가 다음 방향 선택에 영향을 미친다. 가로 이동 -> 이전에 대각선 or 가로 세로 이동 -> 이전에 대각선 or 세로 대각선 이동 -> 이전에 대각선 or 가로 or 세로 2. DFS 풀이(시간 초과) def dfs(pos): global cnt x, y, z = pos # n,n 도달 if x == n - 1 and y == n - 1: cnt += 1 # 가로 세로 대각선의 경우 대각선 이동 if x + 1 < n and y + 1 < n: if graph[x + 1][y + 1] == 0 and graph[x][y + 1] == 0 and gr..

2021. 10. 23.

IT/백준

1. 생각정리 탑을 쌓을 때 고려해야 하는 사항은 세 개다. 무거운 것은 무조건 아래 밑면이 넓은 것은 무조건 아래 위의 두 조건들을 만족시키면서 가장 높은 탑을 쌓을 수 있어야 함 일단 '밑면의 넓이' 혹은 '무게' 중 하나에 대해 정렬을 해준 뒤 코드를 짜면 생각해야 할 조건이 하나 줄어든다. 그리고 dp를 이용해서 하나씩 영역을 확장시키며 쌓을 수 있는 가장 높은 높이를 구할 수 있지 않을까? 여기서 "첫 번째까지 고려한 최대 높이는 dp [1]에", "두 번째까지 고려한 최대 높이는 dp [2]에"... 이렇게 dp를 채운 뒤 dp리스트의 최댓값이 쌓을 수 있는 최대 높이이다. 그리고 mapp과 dp를 바탕으로 하나씩 기억을 더듬어가면 문제가 원하는 답을 도출할 수 있다. 2. 성공 코드 N = ..

2021. 10. 23.

복기/코딩테스트

1. 문제 - 연속하는 자연수 두 개 이상 곱해서 만들 수 있는 값을 크기 순으로 나열한 수열 arr가 있다. ex) 2, 6, 12, 20, 24, 30, 42... - 자연수 n이 매개변수로 주어질 때 arr [n]을 return 해주는 함수 만들기 - n은 1~10^6 2. 풀이 - 일단 arr의 요소들을 나열해보며 규칙을 발견해보자 (0) 1*2 = 2 (1) 2*3 = 6 (2) 3*4 = 12 (3) 4*5 = 20 (4) 2*3*4 = 24 (5) 5*6 = 30 (6) 6*7 = 42 (7) 7*8 = 56 (8) 3*4*5 = 60 (9) 8*9 = 72 (10) 9*10 = 90 (11) 10*11 = 110 (12) 4*5*6 or 2*3*4*5 = 120 (13) 11*12 = 13..

2021. 10. 18.

IT/프로그래머스

1. 생각 정리 완주를 못한 사람은 무조건 한 명 존재 participant 리스트의 길이 = completion 리스트의 길이 +1 2. 성공 코드(리스트 sort를 통한 방법) 일단 participant, completion 리스트를 정렬한 뒤 쭉 비교 비교하다 같은 인덱스에 있는 값이 다르면 return participant [i] def solution(participant, completion): participant.sort() completion.sort() for i in range(len(completion)): if participant[i] != completion[i]: return participant[i] return participant[-1] #무조건 완주 못한 사람은 한명 ..

2021. 10. 14.

IT/프로그래머스

1. 생각정리 clothes 2차원 배열에는 (종류, 이름) 형식으로 스파이가 가지고 있는 옷에 대한 정보가 저장되어 있음 만들어질 수 있는 옷의 조합은 (각 종류별로 옷 종류+1을 다 곱한 값 -1) 2. 96.4/100 코드 set란 2차원 리스트에 옷에 대한 정보들을 저장 1행에는 옷의 종류들을 다 저장 2행부터는 (2행->1행 1열 옷 종류의 옷 이름, 3행->1행 2열 옷 종류의 옷 이름...) 이런 느낌으로 저장 정답을 도출할 때는 2행부터 끝까지 훑으며 각 행의 리스트 길이를 활용하여 계산 근데 내가 코드를 작성하고도 다소 복잡하다는 느낌이 들었음 def solution(clothes): set = [[] for _ in range(30)] #1행에는 옷의 유형, 2행부터는 옷의 종류를 유형..

2021. 10. 14.

IT/백준

1. 생각 정리 전체 map에서 배추가 심어져 있는 위치를 입력받고, 몇 개의 지렁이가 필요한지 구하는 문제 지렁이는 인접한 배추로 이동할 수 있기 때문에 연결되어있는 배추 지역에는 지렁이가 하나만 있어도 됨 결국 전체 map에 0(배추x), 1(배추 o)로 입력을 받고 섬처럼 생긴 1 지역이 몇 개인지? 구하는 접근을 가지면 됨 DFS와 BFS 둘 다 활용하여 풀어보자 2. BFS 시간초과 코드 한번 탐색한 부분은 다시 탐색하지 않게 전체 map과 같은 크기인 visited 리스트를 따로 만들어서 정보를 관리했더니 시간 초과가 떴다. #bfs 시간초과 from collections import deque def bfs(start): q=deque() q.append(start) dir = [(-1,0)..

2021. 10. 13.

카테고리 없음

1. 생각정리 문제를 좀 풀다 보니까 대충 감은 오는 것 같다 연결 정보는 이차원 리스트에 (1행에 1과 연결된 요소들 다 넣기, 2행에 2와 연결된 요소들 다 넣기...)의 느낌으로 입력받고, n+1 크기의 일차원 리스트를 통해 바이러스에 걸리는 것을 확인했는지 여부를 체크해준다 컴퓨터의 수가 적으므로, DFS로 모든 연결정보를 탐색하고, visited정보를 바꿀 때마다 결괏값+=1 해주어 최종 바이러스 걸린 컴퓨터 개수를 도출한다 2. 코드 구현 from collections import deque #컴퓨터의 수 1

2021. 10. 12.

IT/백준

1. 생각 정리 수빈이의 위치에서 동생의 위치까지 무조건 동생과 가까워지는 루트만 따라가면 오히려 시간이 오래 걸릴 수도 있다. 그러므로 각 프로세스마다 (프로세스 단계 * 3)만큼 다양해지는 모든 경우를 고려하여 그중 동생의 위치까지 갔을 때 지금까지 소요된 시간 출력 크기가 100001인 일차원 리스트에 각 위치마다 시간이 얼마나 걸렸는지 갱신하며 동생을 찾을 수 있는 가장 빠른 시간을 구하기 2. 메모리 초과 코드 #메모리 초과 from collections import deque N,K = map(int, input().split()) def bfs(n,k): q = deque([N]) result = 0 count = 1 while q: pos = q.popleft() if pos == K: p..

2021. 10. 12.

IT/백준

1. 생각 정리 처음에 간선 정보 입력을 2차원 리스트에 [[1,2], [1,3]]이런 식으로 담으려 했는데 문제를 더 간단히 풀기 위해서는 빈 2차원 리스트를 생성한 뒤 1행에 1과 연결된 정점 넣어주기, 2행에 2와 연결된 정점 넣어주기... 의 느낌으로 입력받는 게 더 편함 visited 리스트를 따로 만들어서 이미 탐색된 정점에 대한 정보를 관리 DFS의 경우에는 재귀함수로, BFS의 경우에는 deque를 이용하여 구현 2. 코드 구현 from collections import deque #정점 개수 N, 간선 개수 M, 탐색 시작 정점번호 V N, M, V = map(int, input().split()) mapp = [[] for _ in range(N+1)] #두개의 정점이 연결되어있다는 간..

2021. 10. 12.