본문 바로가기

알고리즘/백준알고리즘

[백준 알고리즘/Python] 2178 미로 탐색
알고리즘/백준알고리즘 2022. 2. 24. [백준 알고리즘/Python] 2178 미로 탐색 문제 문제 이해 처음에 dfs로 풀려다가 뭔가 이상한거 같아서 더 좋은 방법이 있겠다 생각했습니다. 가까이 있던 bfs를 생각해보았습니다. bfs로 에서 부터 1칸씩 쭉쭉 이동할 때 마다 count를 1씩 늘려주면 됩니다. 그렇다면 1번 씩 이동할 때 마다 count를 1개씩 늘려줘야 하니 queue 안에 다음 좌표값과 이동해온 크기를 집어넣습니다. 큐에 넣을때마다 크기를 증가시키는게 아니라 한 사이클마다 크기를 증가시켜줘야 합니다. 여기서 사이클은 어떤 좌표에 있을 때 주변에 1이 있다면 그곳으로 가야할 것입니다. ex) 라는 좌표가 있습니다. 까지 오는데 3번 걸린 것입니다. 만약 으로 가야한다면 를 큐에 집어넣으면 됩니다. 만약에 에도 1이 있습니다. 그러면 를 큐에 집어넣습니다. 이런식으로 큐에 ..
[백준 알고리즘/Python] 2667 단지번호 붙이기
알고리즘/백준알고리즘 2022. 2. 23. [백준 알고리즘/Python] 2667 단지번호 붙이기 문제 문제 이해 dfs로 하나의 좌표가 1이라면 다른 1을 찾아서 쭉쭉 스택을 쌓는 형식으로 풀면 됩니다. 이번에는 dfs가 스택이 쌓일 때의 수와 1개의 사이클이 끝날 때를 고려했습니다. import sys sys.setrecursionlimit(10**6) c = [] # dfs 한 사이클 돌 때 나오는 수 r = [] # 나오는 수를 오름차 순으로 def dfs(x,y,count): #주어진 범위를 벗어나면 종료 if(x = n or y = n): return False if(graph[x][y] == 0): return False #현재 노드와 연결된 다른 노드를 재귀적으로 방문 if(graph[x][y] == 1): graph[x][y] = 0 count += 1 #하나의 사이클의 호출 횟수 d..
[백준 알고리즘/Python] 4963 섬의 개수
알고리즘/백준알고리즘 2022. 2. 22. [백준 알고리즘/Python] 4963 섬의 개수 문제 문제 이해 2차원 배열에서 상하좌우, 대각선을 고려해서 1이면 다른 1을 찾을 수 있게끔 합니다. 1을 찾는다면 0으로 만들어서 다시 검색이 안되도록 만듭니다. 코드 import sys sys.setrecursionlimit(10**6) def dfs(x,y): #주어진 범위를 벗어나면 종료 if(x = h or y = w): return False if(graph[x][y] == 0): return False #현재 노드와 연결된 다른 노드를 재귀적으로 방문 if(graph[x][y] == 1): graph[x][y] = 0 dfs(x-1,y-1) #왼쪽 위 대각선 dfs(x-1,y) # 상 dfs(x-1,y+1) #오른쪽 위 대각선 dfs(x,y-1) #왼쪽 dfs(x,y+1) #오른쪽 dfs(..
[백준 알고리즘/Python] 11724 연결 요소의 개수
알고리즘/백준알고리즘 2022. 2. 21. [백준 알고리즘/Python] 11724 연결 요소의 개수 문제 문제 이해 dfs를 돌면서 쭉 깊이 들어가면 그 한번의 사이클이 연결 요소 입니다. python의 제귀 제한이 걸려 있어서 sys.setrecursionlimit(10000) 해야 런타임 에러를 해결할 수 있습니다. 그리고 input()으로 입력을 받으면 시간초과가 나기 때문에 sys.stdin.readline을 써서 입력을 받아줍시다. 코드 import sys sys.setrecursionlimit(10000) input = sys.stdin.readline #DFS 메서드 정의 def dfs(v): #현재 노드를 방문 처리 visited[v] = True #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(i) N, M =..
[백준 알고리즘/Python] 1260 DFS와 BFS
알고리즘/백준알고리즘 2022. 2. 19. [백준 알고리즘/Python] 1260 DFS와 BFS 문제 문제 이해 DFS는 스택으로 BFS는 큐로 해결할 수 있습니다. 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용합니다. 함수를 계속 호출했을 떄 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료가 됩니다. 즉, 제귀로 깔끔한 코드를 짤 수 있습니다. 먼저 DFS 코드입니다. #DFS 메서드 정의 def dfs(graph, v, visited): #현재 노드를 방문 처리 visited[v] = True print(v, end=' ') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) 여기서 graph는 2차원 배열입니다. 처음에 시작인 v노드를 거치고 graph..
[백준 알고리즘/Python] 1748 수 이어 쓰기1
알고리즘/백준알고리즘 2022. 2. 18. [백준 알고리즘/Python] 1748 수 이어 쓰기1 문제 문제 이해 처음에 발견했던 규칙이 1자리수는 1씩늘어나고 2자리수는 2씩늘어나고 3자리수는 3씩 늘어나고 ... 그렇다면 예를들어 120이 들어왔을 때 100 ~ 120까지의 수를 제외하면 1자리수, 2자리수의 갯수의 값과 같습니다. 220이 들어왓을 때 100 ~ 220까지의 수를 제외하면 1~99까지의 자리수는 같겠죠 1~9 => 9개 10~ 99 => 90개 100 ~ 999 => 900 개 이런식으로 규칙을 가졌습니다. 그렇다면 1일 때는 9 * 1 * 1 2일 때는 9 * 10 * 2 3일 때는 9 * 100 * 3 의 규칙을 찾을 수 있습니다. ex) 220이 들어왔을 때 먼저 1~99 의 자리수를 구하고 100 ~ 200의 값을 따로 구하면 됩니다. 코드 num = int(input()..
[백준 알고리즘/Python] 6064 카잉 달력
알고리즘/백준알고리즘 2022. 2. 16. [백준 알고리즘/Python] 6064 카잉 달력 문제 문제 이해 1~40000까지 다 구하려다가 시간초과가 났습니다. 다른 방법을 찾아보는데 x를 고정시키는 방법이 있었습니다. x를 고정시키고 M값을 더하면 x는 그대로있고 y만 변하게 됩니다. ex) 10 12 3 7 의 값이 주어졌을 때 처음 1 1에서 1씩 2를 올려 3 3을 만듭니다! x값은 일치가 되었죠. 다음부터는 10씩 올립니다. 그러면 3 17 -> 3 27이 되겠지요. 하지만 y는 13이 되면 1로 돌아갑니다. 1 1 3 3 3 (13)1 3 11 3 (21)9 3 (19)7 (종료) 이런 방식으로 시간을 단축시킵니다. 코드 test_case = int(input()) def lcm(num1,num2): for i in range(max(num1,num2),0,-1): if((num1%..
[백준 알고리즘/Python] 1107 리모컨
알고리즘/백준알고리즘 2022. 2. 16. [백준 알고리즘/Python] 1107 리모컨 문제 문제 이해 처음에 실제 리모컨 누르는 로직을 생각했습니다. ex) 5457중에 6,7,8이 고장났다. 5 누르고 -> 목표 값과의 최소 확인 54 누르고 -> 목표 값과의 최소 확인 545 누르고 -> 목표 값과의 최소 확인 5457 누르고 -> 목표 값과의 최소 확인 이렇게 접근을 했는데 로직이 복잡해지고 만약 고장난 수를 제외하면 모든 수를 파악할 수가 없었습니다. 다른사람의 풀이를 참고했을때 허망함을 느꼈습니다. 그냥 0~1,000,000까지 수열을 돌리고 그중에 고장난 버튼수를 제외합니다. 그리고 목표값과 거리가 가장 작은 수를 찾습니다. 이게 부르트포스 인가.. 하고 느꼈습니다. 근데 채널의 수는 0~ 500,000까지 인데 1,000,000을 넣는가? 수빈이가 이동하려는 채널은 0~ 50..
[백준 알고리즘/Python] 1476 날짜 계산
알고리즘/백준알고리즘 2022. 2. 14. [백준 알고리즘/Python] 1476 날짜 계산 문제 문제 이해 1 1 1 부터 15 28 19 까지 의 수를 모두 돕니다. 그리고 16, 29, 20 일 때마다 E,S,M을 초기화 시켜주면 됩니다. 코드 E, S, M = map(int,input().split()) count_E = 0 count_S = 0 count_M = 0 for i in range(1,7980+1): count_E += 1 count_S += 1 count_M += 1 if((count_E % 16) == 0): count_E = 1 if((count_S % 29) == 0): count_S = 1 if((count_M % 20) == 0): count_M = 1 if(count_E == E and count_S == S and count_M == M): print(i) br..

티스토리툴바