본문 바로가기

python

 (50)
[백준] 7453 합이 0인 네 정수, python https://www.acmicpc.net/problem/7453 a*b*c*d의 모든 경우의 수를 확인하게 되면 4000⁴ 가 되어 시간초과가 난다.그래서 처음에는 A와 B의 합 배열 AB와 C와 D의 합 배열 CD를 만들어 AB에 있는 값에 -1을 곱한 값이 CD에 있으면 하나씩 세는 방법으로 풀었다.여기서 합 배열을 구할 때 중복된 숫자가 있을 때를 가정하여 (합, 등장 횟수)를 딕셔너리로 저장했다.하지만 C와 D의 합 배열을 생성하게 되면 추가적인 메모리 낭비와 이후 생성된 CD배열과 AB배열 비교에서 연산을 한번 더하게 되는 문제가 발생한다.따라서 CD배열을 직접 생성하는 대신, C와 D의 합을 계산해 바로 AB합배열에 있는지 체크하면서 개수를 추가해 주면 된다. 기존 딕셔너리에 저장하게..
[백준] 2250 트리의 높이와 너비, python https://www.acmicpc.net/problem/2250 노드번호, 왼쪽 자식노드, 오른쪽 자식노드가 입력으로 주어진다. 루트 노드가 아니라면 노드에서 1번, 자식노드에서 1번 총 2회가 등장하게 된다. 따라서 등장 횟수가 1번인 노드가 루트노드가 된다. 루트노드를 찾았으면 트리를 전위순회 하게되면 그 순서가 왼쪽으로부터의 떨어진 거리이다.bfs탐색을 하며 각 레벨마다 해당 레벨에 포함되는 노드들을 담은 배열을 생성한다. 마지막으로 각 레벨에 대해 저장된 노드들의 첫번째와 마지번째 위치의 차이를 계산하면 해당 레벨의 넓이가 된다.이 넓이의 최댓값을 구하였다. import sysfrom collections import dequeinput = sys.stdin.readlinen = int(i..
[백준] 14236 명제 증명, python https://www.acmicpc.net/problem/14236 처음에는 모든 명제가 함축되기 위해선 i=> j명제들의 i와 j가 모두 2회 이상씩 나와야 함축된다고 생각했다.예를 들면 1=>2와 2=>1처럼 1과 2가 2회 이상 나와야 함축이라고 생각해서 백트래킹으로 dfs를 돌면서 명제가 2번씩 등장하는 케이스들을 모두 찾은 다음, 해당하는 케이스에서 bfs를 돌면서 한 i에서 모든 j로 가는 경로가 있으면 통과라고 풀었는데 시간초과가 나서 해결하지 못하였다.이 문제는 SCC를 구하는 문제이다. 강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python 강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python강한 연결 요소란? 강한 연결 요소, SCC(S..
[프로그래머스] 코딩 테스트 공부, python https://school.programmers.co.kr/learn/courses/30/lessons/118668?language=python3 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 모든 문제를 해결하기 위해 알고력과 코딩력의 최댓값을 계산한다. dp [i][j]는 알고력이 i, 코딩력이 j에 도달하기까지의 최소 시간을 저장한다.dp [현재 알고력+증가 알고력][현재 코딩력+증가 코딩력]에 d dp[현재 알고력+증가 알고력][현재 코딩력+증가 코딩력] 과 dp [현재 알고력][현재 코딩력]+걸린시간 중 최솟값을 갱신한다. 만약 현재 알고력+증가 알고력 또는 현재 코딩력+증가 코딩력이 최대 알고력, ..
[프로그래머스] 주사위 고르기, python https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 완전탐색을 통해 구현력을 테스트하는 문제인 것 같다. 첫 번째로 각 주사위를 값: 등장 횟수의 딕셔너리로 바꾸었다.주사위가 [3,3,3,3,4,4] 면 {3:4, 4:2}로 변환하였다. 두 번째로는 combinations를 통해 주사위를 선택할 수 있는 케이스들을 전부 구하고 각 케이스에 대해 첫 번째 단계에서 변환된 딕셔너리로 선택된 주사위들로 나올 수 있는 합: 경우의 수 딕셔너리를 구하였다.주사위 1이 {3:4,4:2}고 주사위 2가 {2:2,..
[프로그래머스] 미로 탈출 명령어, python https://school.programmers.co.kr/learn/courses/30/lessons/150365?language=python3 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 백트래킹을 통해 구현하였다. dfs를 도는데 방향 순서를 d, l, r, u로 탐색하게 하면 맨 처음 조건을 만족해서 종료되는 시점이 사전순으로 가장 빠르게 됨이 보장된다.처음 조건을 만족하게 되면 flag=True로 설정하여 나머지 탐색은 즉시 종료한다.dfs를 돌면서 현재 남은 횟수로 목적지에 도달 가능한지 여부를 판별하여 종료를 한다. import syssys.setrecursionlimit(10**6)def s..
[백준] 17825 주사위 윷놀이, python https://www.acmicpc.net/problem/17825 해당 게임판을 그래프로 변환했다.백트래킹을 통해 각 말의 위치를 계산하고 최댓값을 갱신한다.말이 도착하는 칸에 다른 말이 있는 경우와 이미 도착한 말은 백트래킹할 때 제외해야 한다.10,20,30 이 적힌 칸은 파란화살표로 진행해야 하므로 해당칸일 때 처음 1칸은 파란 길로 가야 하므로 flag를 두어 처리했다. import sysfrom copy import copyinput = sys.stdin.readlinearr = list(map(int, input().split()))graph = [[] for _ in range(32)]score = [0]*32# 게임판을 그래프로 변환for i in range(20): graph[..
[백준] 17471 게리맨더링, python https://www.acmicpc.net/problem/17471 그룹을 나눈 다음 유니온파인드로 해결한 문제이다. 유니온 파인드 알고리즘, python 유니온 파인드 알고리즘, python유니온 파인드 알고리즘이랑, 두 집합을 하나로 합치고(union) 두 원소가 같은 집합에 속해있는지 확인하는(find) 알고리즘이다. 유니온 파인드를 구현하기 위해서는 부모노드의 번호를 저장할 rootaiden0413.tistory.com n개를 2개의 그룹으로 나눌 수 있다.1개 n-1개, 2개 n-2개... n-1개 1개로 나눌 수 있다.즉 k,n-k (1 k, n-k로 나눌때 combinations을 사용해서 모든 케이스를 구했다.해당 케이스를 a그룹이라고 하고, a그룹에 포함되지않는 나머지 노드들을 ..

티스토리툴바