모영이의 블로그

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 : 중복되는 수열을 제외해야한다. 2 4 4가 있고 길이가 2이면 2 - 4(첫번째 4) 2 - 4(두번째 4)가 중복된다. 주어진 수를 제거하면 안되는게 2 4 4에서 중복되는 4를 제거하면 2 4가 되어 4 - 4 수열을 체크 못한다. 그래서 중복되는 값을 없애야하고 자연스럽게 in을 사용했지만, in은 시간복잡도가 list와 tuple일때 O(N)이지만 set, dict일때 O(1)이다. 그래서 set을 사용했다. 전체코드 import sys im..

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 다익스트라 : 어떤 한 정점에서 가장 먼 곳의 정점은 가장 먼 두 정점 중 하나다. 문제의 핵심은 이것인데, 사실 잘 알기가 어렵다. 그래서 처음엔 DFS로 모든 경로의 거리값을 계산해 최댓값만 업데이트 시켰다. 이렇게 하면 시간초과와 메모리 초과가 발생하는데, 5까지 있다고 하면 1, 2, 3, 4, 5에서 출발하는 정점의 거리를 각각 찾아내기 때문에 이를 해결할 수 없다. 하지만, 처음 말했던 공식을 안다면, 어떤 한 정점이 무조건 포함됨을 알기에..

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 : 한번 간 곳은 다시 방문하지 않도록 설계 전체 코드 import sys input = sys.stdin.readline def bt(t:int, result:list, visited:list): if t == 0: print(*result) return for i in range(len(nums)): if i not in visited: bt(t-1, result + [nums[i]], visited + [i]) N, M = map(int, ..

1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 분할 정복 : 시작점을 기준으로 +d만큼 탐색을 한다. 만약 압축 실패시 분할 압축. 전체 코드 import sys input = sys.stdin.readline def apchuk(si, sj, d, result): color = graph[si][sj] isTrue = True for i in range(si, si + d): for j in range(sj, sj + d): if graph[i][j] != color: isTrue = Fals..

1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라 알고리즘 : 벽의 길은 가중치를 1을 두고 나머지 길은 0으로 두면 다익스트라 알고리즘을 사용할 수 있다. BFS로 상하좌우를 탐색하고 갈 수 있는 길을 찾아내면 된다. 길의 가중치가 0이라면 벽이 없는 길은 아무렇게나 가도 상관이 없을 것이다. 1) 최소 힙에 가중치와, 노드좌표를 넣는다. 2) 다익스트라 알고리즘 사용 3) 상하좌우 탐색 BFS사용 전체 코드 import sys import collections import h..

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 : 각 자리의 최대값은 위의 왼쪽 오른쪽 중 최댓값에 자기 자리를 더한 것이다. 1) 각 층별로 계산을 해야한다. 한칸 내려갈 때마다 계속 1씩 늘어나는 구조다. 2) p1과 p2에 부모의 값을 담는다. 왼쪽 부모는 맨 왼쪽 인덱스일때를 제외하고 담을 수 있고, 오른쪽 부모는 맨 오른쪽 인덱스일때를 제외하고 담을 수 있다. 3) p1과 p2 중 큰 값 + 자신의 현재 위치값 업데이트 해주기 전체 코드 import sys input = sys.stdin.readline N = int(input()) graph = [..

Using Null - SQLZOO teacher id dept name phone mobile 101 1 Shrivell 2753 07986 555 1234 102 1 Throd 2754 07122 555 1920 103 1 Splint 2293 104 Spiregrain 3287 105 2 Cutflower 3212 07996 555 6574 106 Deadyawn 3345 ... dept id name 1 Computing 2 Design 3 Engineering ... Teacher sqlzoo.net 기본 정보 teacher -> id, dept, name, phone, mobile dept -> id, name #1 NULL은 IS NULL은 =이 아니라 IS를 사용해야 한다. SELECT n..

More JOIN operations - SQLZOO This tutorial introduces the notion of a join. The database consists of three tables movie , actor and casting . movie id title yr director budget gross casting movieid actorid ord More details about the database. 1962 movies List the films where the yr is sqlzoo.net 기본 정보 movie -> id, title, yr, director, budget, gross actor -> id, name casting -> movieid, actorid,..

7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net BFS : 나이트가 이동할 경로를 전부 업데이트 하다가 목적지를 만나면 값 출력 1) 나이트는 총 8개의 범위를 갈 수 있고 그 경로를 dx와 dy에 저장해 놓고 사용한다. 2) 나이트의 현재 위치가 목적지와 같다면 그 곳의 dp값을 리턴한다. 3) 나이트가 갈 수 있는 방향 8개를 전부 확인하고 나이트가 가지 않았던 위치면 그곳을 탐색한다. dp값이 -1 초기값이면 한번도 안갔던 곳이고 dp값을 업데이트 시켜주는데, 이전의 출발 지점의 dp값에 +1 한 값을 넣..

The JOIN operation - SQLZOO game id mdate stadium team1 team2 1001 8 June 2012 National Stadium, Warsaw POL GRE 1002 8 June 2012 Stadion Miejski (Wroclaw) RUS CZE 1003 12 June 2012 Stadion Miejski (Wroclaw) GRE CZE 1004 12 June 2012 National Stadium, Warsaw POL RUS ... goal matchid t sqlzoo.net 문제의 이름이 없어서 내가 맘대로 적었다. 기본 정보 game -> id, mdate, stadium, team1, team2 goal -> matchid, teamid, player..