링크 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 소요시간: 9분 26초 설계하기(접근방법) 1. 입력받기 n, m 을 입력받는다 2. 구현하기 중복 순열을 전부 탐색한 후 중복을 제거해줄라고 했으나 시간 초과가 났다 그래서 백트래킹으로 풀었다. dfs 내의 for문을 탐색할 때 이전에는 이전 숫자 + 1을 탐색했다면 1-> 2 -> 3 이번에는 이전 숫자부터 탐색하면 된다1 -> 1 -> 1 종료조건은 똑같이 m의 길이로 해주면..
링크 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 소요시간: 3분 6초 설계하기(접근방법) 1. 입력받기 n, m 을 입력받는다 2. 구현하기 백트래킹의 변형이지만 실제로는 재귀함수 문제같다 visited를 코드에는 선언했지만 필요없었다 1 ~ n까지 차례때로 선택하고, 중복을 허락한다 즉 visited를 검사할 필요가 없다 3. 출력하기 ans를 출력한다 코드(출력) n , m = map(int, input().split()) ..
링크 : https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 소요시간: 9분 23초 설계하기(접근방법) 1. 입력받기 n,m 을 입력받는다 2. 구현하기 이전 문제와 구조는 비슷하다 마지막으로 리스트에 append 해줄 때 sort()를 한 후 ans 에 있는지 없는지 검사해준다 그러면 중복을 피할 수 있다 +++ 혹은 검사를 할 ㄸ i부터 n까지가 아닌 이전에 append한 숫자를 인자로 넘겨서 apppend ~ n까지 순회하면 중복을 피..
링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 소요시간: 연습 문제 설계하기(접근방법) 1. 입력받기 n, m 을 입력받는다 2. 구현하기 백트래킹 연습문제를 풀었다 백트래킹은 재귀 함수를 만들 때 구조화 하는 것이 중요하다 탐색 중복 방지를 위해 visited을 선언해줘야 한다. 이 visited는 재귀함수 들어가기 전에 1로 바꿔주고 재귀함수가 끝났을 때 = 종료조건 이면 다시 visited를 0으로 바꾸어준다 또한 재귀적..
링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 소요시간: 실패 설계하기(접근방법) 1. 입력받기 행열을 입력받는다 2. 구현하기 BFS로 풀어보려다가 도저히 방법이 떠오르지 않아서 다른 블로그의 풀이를 참고했다. 이 문제의 핵심은 case를 가로 세로 대각선으로 나누어서 푸는 것이다 dp 리스트를 선언할 때 dp = [[[0,0,0] for _ in range(n)] for _ in range(n)] 과..
링크 : https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 소요시간: 10분 7초 설계하기(접근방법) 1. 입력받기 노드와 간선을 입력받는다 2. 구현하기 1부터 노드를 bfs로 순회하면서 자식 노드 번호에 부모 노드 번호를 저장한다 3. 출력하기 2번 노드부터 부모 노드를 출력한다 코드(출력) from collections import deque import sys input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n + 1)..
링크 : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 소요시간: 35분 실패 설계하기(접근방법) 1. 입력받기 트리의 노드 수와 간선을 입력받는다 2. 구현하기 트리의 가중치, 누적 가중치까지는 잘 구현했다 하지만 그 이후로 어떻게 끝과 끝을 연결해야 트리의 가장 큰 지름을 보장할 수 있을지 몰랐다 서치를 해보니 한 노드에서 가장 깊은 곳을 기준으로 다른 깊은 곳을 찾아내면 그것이 트리의 지름을 보장한다고 한다 따라..
링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 소요시간: 35분 22초 설계하기(접근방법) 1. 입력받기 토마토 행렬을 입력받는다 2. 구현하기 -1이 있는 구역은 ripe를 전달하지 못한다 1이 여러 군데 있는데, 이 부분은 bfs 시작시 q에 append를 여려 개 해주면 된다. 매 시도마다 토마토를 다 확인하는 것은 불가능하다 즉 토마토의 개수를 미리 세두면 된다 이미 익은것과 익지 못하는 구간을 빼면 전체..
