BFS로 최단거리를 구하면 되는 문제이다. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 부수면서 이동하기 문제의 쉬운 버전이다 ㅎㅎ 이제 이런 간단한 그래프 문제는 한번 시도만에 바로 맞다니 ㅠㅠ 감격스러운걸...! from collections import deque n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) dx = [-1, 1, 0..
Algorithm (PS)
최단거리 찾는 문제인데 벽하나 부술수있다는 게 특이점이다 풀이 1 :시간초과가 났다 이중포문으로 백트래킹은 무리였던건가 ㄱ- 파이썬만 그런지 c++도 그런지 궁금하다 진짜 이 경우, 내가 가는 경로 중에 벽이 있는지 상관없이, 모든 벽을 한번씩 다 없애보는 코드인데, 효율성을 높이려면 내가 가는 경로 도중에 마주친 벽을 제거해야 할 것 같다.. from collections import deque n, m = map(int, input().split()) graph = [list(map(int, input())) for _ in range(n)] INF = int(1e9) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(): # 최단 경로 구하기 dist = [[-1] ..
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 유형 : DP, Knapsack Algorithm 작년 알고리즘 수업시간에 배웠던 Knapsack Problem 과 동일한 문제이다 !! 원래 유래는 도둑이 물건을 훔칠때 들 수 있는 무게는 한정되어 있는 상황에서 최대한의 가치를 가방에 넣을 수 있는 방법을 구하는 것이었다. Knapsack Algorithm은 0-1 배낭 문제, ..
https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 난이도 : 하 유형 : 시뮬레이션 문제에서 하라는 대로 해주면 된다. 배열의 가장 마지막 원소와 크레인이 집어 올린 원소와 같으면 배열의 마지막 원소를 pop 시킨다. 그리고 결과값에 2개를 더해준다. 단 주의할 점은 원소를 빼낸 후에 break 문을 걸어야 안쪽의 for 문 순회에서 벗어날 수 있다. !!! (크레인 처리 이후에 바로 다음 move를 수행하기 위해서이다. ) def so..
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 유형 : BFS/ DFS (나는 BFS로 풀었당) 어려웠던 부분은 '최단 거리'를 어떻게 구하냐는 것이다. BFS로 최단거리를 구하는 방법을 꼭 기억해두자 !! 현재 위치 (x, y)에서 -> 상하좌우 를 확인하는데 (for 문으로 확인 nx = x + dx[i], ny = y + dy[i])-> 0 ~ n 의 범위 안에 있어야 하며 (0 dist[nx][ny] = dist[x][y] + ..
https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 최종적으로 맞은 코드는 다음과 같다. 우선 이중 for문을 쓸 때 j의 범위를 1부터 i에 루트를 씌운 값까지!!! 라는 범위를 주어 반복문의 범위를 줄여서 시간초과를 극복했다,, 또 이번에 새롭게 알게된 점은 i**2 보다 i*i 가 계산 속도가 더 빠르다는 것이다 !!!!! 헐 ~~~~~~ 찾아보니까 i**2 는 몇 제곱을 하는지 옵션을 줄 수 있어서 ,..
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이문제는 가장 긴 증가하는 수열 + 가장 긴 감소하는 수열을 합쳐놓은 문제같다 ㅋㅋ 마침 두개 다 풀었고, 그래서 나는 1. 가장 긴 증가하는 수열 만들기 : dp 2. 가장 긴 감소하는 수열 만들기 : dp2 3. 합친 수열중에서 가장 길이가 긴 수열 값 구하기 -> dp3 테이블을 만들었다. # 11054 가장 긴 바이토닉 수열 n = int(input()) array = list(map(int, input()...
자료구조 시간에 트리 구조 배웠을 때 처럼 !! 재귀 함수를 이용하여 트리를 순회할 수 있다. + 트리 자료구조를 다시 정리하자 ! # 1991 트리 순회 n = int(input()) tree = {} # dictionary type for i in range(n): root, left, right = input().split() tree[root] = [left, right] # key, value #preorder root - left - right def preorder(root): if root != '.': print(root, end='') # root preorder(tree[root][0]) # left preorder(tree[root][1]) # right # inorder left ..
