https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net dfs로도 풀수있다고 하는데, 문제보자마자 난 파이썬 permutation 모듈이 생각나서 그냥 그렇게 풀었는데 메모리초과도 안나고 시간초과도 안나서 통과했다 from itertools import permutations n, m = map(int, input().split()) array = [i for i in range(1, n+1)] # 1...n result = [] for i in l..
Algorithm (PS)
https://www.acmicpc.net/problem/5212 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 문제 아이디어 1. 이중 for문을 순회하면서 땅을 찾으면 상하좌우를 확인하여 인접 세칸 이상이 바다인지 확인한다 단!!!! 여기서 지도의 의미는 섬을 포함한 최소 직사각형이므로, 지도 범위인 (r, c)를 초과하면 바다이다 for i in range(r): for j in range(c): if array[i][j] == 'X': # 땅이면 인접 세칸 이상이 바다인지 확인하기 count = 0 for k in range(4): nx = i + dx[k] ny = j + d..
array = [ [0 ,0 ,0 ,0, 0], [4 ,4 ,4 ,4, 4], [3 ,3 ,3 ,3, 3], [2 ,2 ,2 ,2, 2], [1 ,1 ,1 ,1 ,1]] n = 5 for i in range(n): print(array[i]) print() for i in range(-1, -n, -1): array[i] = array[i-1] array[0] = [0 for i in range(n)] for i in range(n): print(array[i]) for문 수행 이후 array의 값
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 1. 유형 : DFS 2. 문제 아이디어 1 2 3 4 5 6 7 3 1 1 5 5 4 6 입력되는 노드를 시작점이라고 보고 인덱스들이 이어지는 노드라고 생각하여 그래프를 그리면 다음과 같다. 1: [2, 3] 2: [] 3: [1] 4: [6] 5: [4, 5] 6: [7] 7: [] 그래프를 dfs로 순회한다. 방문한 노드를 visited 리스트에 표시하여 이미 방문한 노드는 재방..
https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 최단거리를 이용하는 다익스트라알고리즘의 응용 버전이다. 카카오 코딩테스트 해설을 참고 했다. - 간선의 정보들로 인접 graph를 만든다. 그리고 문제에서 그래프 자체는 양방향 그래프인데 내가 일방향으로 처리를 해서 계속 list 에 인덱스 없다고 에러가 떴다 그래프 문제에서 양방향인지 일방향인지 항상 주의하자 ! !!!!!! - 다익스트라 알고리즘을 출발지의 개수만큼 실행하면 시간초과가 나므로..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 최단경로를 구하는 방법 중 하나인 다익스트라 알고리즘을 이용해서 풀었다 문제는 기본 다익스트라 알고리즘을 이용해서 풀었다. 시작 정점에서 각 정점까지의 최단거리를 구해서 distance 리스트에 저장하면 된다. # programmers import heapq v, e = map(int, input().split()) k = int(input()) # 시작 정점..
https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 풀이 Greedy 유형이라는 힌트가 나와있다 가로길이의 경우 calendar[i]를 하나씩 확인하면서 일정이 있을 때마다 계속 하나씩 더해주면 된다 (calendar[i] != 0 이면 하나씩 더함) 세로길이의 경우 현재 범위에서 일정이 겹치는 수들 중 max값으로 갱신한다. 이 예시에서는 2일에서 9일사이의 최대 세로 길이는 3칸이다. 그리고 10일째 될때 일정이 없는데, 이때 저장된 row값과 col 값을..
https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net bfs 문제인데 칼이라는 조건이 추가되었다 칼이 있을 때와 칼이 없을 때 최단거리가 달라진다 ..!!!! 이걸 어떻게 처리하느냐가 관건인데, 우선 칼을 가지고 있으면 굉장히 문제가 간단해진다 if array[x][y] == 2: # knife min_time = visited[x][y]-1 + n-1-x + m-1-y # 칼까지의 최단거리 + 칼에서부터 공주까지 거리 칼까지의 최단..
