본문 바로가기

알고리즘/백준

 (263)
[백준] 20002번 : 사과나무 20002번: 사과나무 해당문제는 구간합 개념을 알면 빠르게 문제를 해결 할 수 있다. 구간합은 다이나믹 프로그래밍으로 접근하여 생각해보면 된다. 만약 2x2 구간을 구한다고한다면 1x2와 2x1 을 더한뒤 1x1을 빼주고 자기자신의 배열 2x2을 더해주면 된다. 점화식은 다음과 같다. 💡 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i[j] 이다. N = int(input()) table = [] dp = [[0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N): table.append(list(map(int, input().split()))) for i in range(1, N+1): fo..
[백준] 2922번 : 즐거운단어 2922번: 즐거운 단어 해당문제는 완전탐색문제로 “생각의 틀”을 벗어나 문제를 풀게 만든 문제입니다. 처음에 문제를 접할때 자음과 모음을 모두 확인해보면서 문제를 해결하려고 접근하였습니다. 그러나 이 방법은 즐거운 단어를 만드는 단어를 구하는 위한 과정이었고, 문제는 “경우의 수”만 구하면 된다는 것 입니다. 모음이 연속해서 3번, 자음이 연속해서 3번이 나오지 않을 조건을 탐색조건으로 분기시켜 깊이우선탐색으로 문제를 해결 할 수 있습니다. 예를들어 이전에 모음이 2번 나왔을경우 그다음 탐색조건은 자음이 나와야하며, 이전에 자음이 2번 연속 나왓을경우 무조건 모음으로 탐색해야합니다. mo = {'A','E','I','O','U'} word = input() def dfs(mocnt, jacnt, lcn..
[백준] 16637번 : 괄호 추가하기 16637번: 괄호 추가하기 해당문제는 완전탐색문제입니다. 현재위치에서 계산할 경우와 그다음위치에서 계산할경우 2가지를 분기시켜 그중 최대값을 출력하면 됩니다. 예를들어 3+8*7 이 주어졌다고 가정하면, 2가지 경우가 나올 수 있습니다. 3+8*7 계산식 3+(8*7) 계산식 여기서 뒤에 +4가 추가된다고 가정하면 이전에 있던 1번 분기점에서 3+87+4의 경우와 3+8(7+4)의 경우로 나타낼수 있습니다. 이전에 있던 2번 분기점에서 3+(8*7)+4의 경우만 존재하게 됩니다. ( 중첩된 괄호는 계산 할 수 없기때문 ) N = int(input()) data = input() def calculate(num1, num2, op): if op == '+': return num1 + num2 elif o..
[백준] 1246번 : 온라인 판매 1246번: 온라인 판매 해당 문제는 완전탐색으로 문제를 해결하였습니다. N^2 의 시간복잡도로 모든 경우의수를 확인하여 문제를 해결 할 수 있습니다. 달걀의 가격을 한번씩 모두 정해보면서 N개의 달걀이 넘지 않으면서 계산한 값의 합 중에서 가장 큰 값을 찾으면 됩니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) P = [] for _ in range(M): P.append(int(input())) P.sort() ans = 0 maxcost = 0 for pr in P: cnt = 0 for pr2 in reversed(P): if pr2 >= pr: cnt += 1 if N >= cnt: if cnt * pr > ma..
[백준] 19236번 : 청소년 상어 19236번: 청소년 상어 해당 문제는 완전탐색, 백트래킹, 구현 문제 입니다. 청소년 상어가 움직인다. 물고기를 먹고 물고기의 방향을 갖는다. 먹은 물고기의 번호를 가중치에 추가한다. 먹을 수 있는 물고기가 없다면 종료한다. 물고기가 움직인다. 물고기가 작은 순서부터 이동한다. 물고기는 한칸을 이동할 수 있다. 이동할 수 있는칸은 빈칸과 다른물고기가 있는칸 이다. 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 물고기가 다른 물고기로 있는 칸으로 이동 할때에는 서로의 위치를 바꾼다. 1-c가 만족될때까지 반복해서 수행한다. 상어가 먹을 수 있는 경우의 수를 구하여 물고기의 번호 합의 최대값을 출력하면 된다. graph[i][j]는 물고기의 번호와 물고기의 방향값을 갖는다. 상어가 먹을..
[백준] 11559번 : Puyo Puyo 11559번: Puyo Puyo 해당 문제는 구현 문제로 상하좌우가 4개이상 연결되어 있는 판별과, 중력을 영향을 받아서 떨어지게되는 로직을 구현하면 된다. 상하좌우가 4개이상 연결되어있는지 판별법 특정 모양에 대하여 기능을 나누었다. ㅗ,ㅜ,ㅏ,ㅓ 의 모양 : 특정 좌표에서 상하좌우로 탐색시 같은색상이 3 이상일때 ㅁ 모양 : 특정 좌표에서 (1,0), (0,1), (1,1)이 같은 색상일때 ㅡ,ㅣ 모양 : 특정 좌표에서 상하좌우로 탐색시 같은색상이 4 이상일때 중력을 영향을 받아서 떨어지는 기능 각각의 열을 탐색한다. 각각의 열에대하여 아래서 부터 위까지 0이 아닌 색상을 큐에 추가한다. 각각의 열에대하여 큐에 추가된 블록을 아래서부터 채워나간뒤, 나머지 블록을 0으로 채운다. from pprint ..
[백준] 17281번 : ⚾ 17281번: ⚾ 완전탐색과 구현 문제의 조합입니다. 타순을 정한다. ( 모든 타순의 경우의 수를 구한다 ) 타순을 구하는 방법 순서가 있는 탐색임으로 깊이우선탐색으로 순열을 만든다. 1번 선수는 반드시 4번타자로 정해져 있으므로 4번 타자가 1번 선수가 아닌상황은 제외한다. 구현법 이닝이 시작되고 타순을 돌린다. 각각의 선수에대하여 안타, 2루타, 3루타, 홈런, 아웃을 구현한다. 안타 b[0], b[1] 각각 b[1], b[2]로 옮긴다. b[0]은 1이 된다. b[2]가 1일경우 점수를 획득한다. 2루타 b[0], b[1] 각각 b[2]와 b[3]으로 옮긴다. b[1]은 1이된다. b[1], b[2]가 2일 경우 점수를 획득한다. 3아웃이 되면 베이스에 있는 값들을 모두 초기화 한다. 이닝을 하나 ..
[백준] 17779번 : 게리맨더링 2 17779번: 게리맨더링 2 완전탐색과 구현 문제입니다. 가능한 모든 경계선 d1, d2의 경우의 수를 구한뒤 그 경우의 수에대하여 경계선을 만들고, 그 경계선으로부터의 지역들을 분리시키고, 분리된 지역으로부터 인구수를 구한뒤 가장많은 인구수와 가장적은 인구수의 차이의 최소값을 구하면 됩니다. 모든 경우의수 탐색 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N) 에 맞는 d1, d2를 구한다. 해당 탐색 구역에서의 경계선 만들기 경계선을 만드는 조건으로 경계선을 만든다. 경계선을 기준으로 1구역과 2구역 3구역 4구역의 그래프를 채운다. 각각의 열과 행에대하여 경계선의 조건에따라서 그래프를 순회하며 채운다. 1구역 2구역 3구역 4구역으로 나누면서 ..

티스토리툴바