https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제를 간단하게 요약하자면, 선거구를 딱 두개로 나누고, 그 선거구는 연결되어 있도록 할 때, 두 선거구 인원차를 최소로 만드는 것이다. 입력 제한이 N이 10 까지이므로 N! 만큼 탐색을 해도 상관이 없었다. combination을 사용해서 풀었다. python의 combination의 시간복잡도는 https://stackoverflow.com/questions/53419536/what-is-the-computati..

https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 참으로 고생 많았던 문제다.. 어떻게 풀어야할지 감도 안잡혀서 일단 종이와 펜을 들었다. 그리고 위 예제를 봤다 3 4 12 16 67 43 7 17 68 48 14 15 77 54 음.. 12를 먼저 선택하고 다음줄부터 7 , 17 , 68 ... 이렇게 탐색을 한다? N^3 이 나올 것이다. 1000이니까.. 10억?? 택도없네 한번 정렬을 해보자 3 4 12 16 43 67 ..

https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 이 문제는 처음에는 진짜 트리를 구성해야하나? 이런식으로 고민을 많이 했다. 하지만 생각해보니 무조건 한쪽 끝에서 시작을 하면 되는거였다!! 그래서 inDegree 가 1인 , 즉 이 그림에서 보면 원에서 선이 한 개만 빠져나가는 것들을 모두 Queue에 풀었다! 위상정렬이라고 해야하나..? 처음 queue에 1번, 2번 , 4번 을 넣은 뒤 ..

https://programmers.co.kr/learn/courses/30/lessons/77886 코딩테스트 연습 - 110 옮기기 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 programmers.co.kr 110은 한 세트로 무조건 움직여야 한다는 개념만 가지면 된다. 그리고 110이 만들어지면 그 이전에건 신경쓰지 않아도 된다. def solution(s): answer = [] for num in s: answer.append(go(num)) return answer def go(num: str): ind = 0 cnt = 0 st = ..

처음에 문제 이해가 안돼서 조금 고생했다.. 토네이도가 바람이 부는데 모래가 어떻게 날아간다는거지?? 를 이해하는데 조금 걸렸던 것 같다. tornado 함수를 구현하고 그부분에 모래의 양을 더해주고, 마지막에 빼주었다. 문제 이해만 한다면 어렵지는 않은 문제. N = int(input()) arr = [[0] * N for _ in range(N)] for i in range(N): line = list(map(int, input().split())) for j in range(N): arr[i][j] = line[j] depth = 1 x = N // 2 y = N // 2 res = 0 def tornado(x, y, nowx, nowy, pro): global arr, N, res if (x < ..

이 문제도 깡 구현 문제이다. 오른쪽으로 가는 것, 아래로 가는 함수를 따로 나누고, 범위를 잘 생각해서 점수를 더하고 없애주면 된다. N = int(input()) blue = [[0]*6 for _ in range(4)] green = [[0]*4 for _ in range(6)] point = 0 def goBlue(t,xx,yy): global blue, green x = xx y = 0 if t == 1: while True: if y > 5 or blue[x][y] != 0: y -= 1 blue[x][y] = 1 break y += 1 if t == 2: y = 1 while True: if y > 5 or blue[x][y] != 0 : y -= 1 blue[x][y] = 1 blue[x]..