백준
-
알고리즘: 백준 1002번 터렛 (feat. python)알고리즘/백준(BaekJoon) 2020. 12. 30. 18:20
1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) for i in range(n): x1, y1, a, x2, y2, b = (map(int, input().split())) dis = ((x1-x2)**2 + (y1-y2)**2)**(1/2) r1 = a if a>b else b r2 = a if a
-
알고리즘: 백준 2565번 전깃줄 (feat. c++) 최장증가수열문제(LIS)알고리즘 2020. 8. 31. 22:41
백준 2565번 문제입니다. 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 좀 꼬아놓은 최장증가 수열 문제 (사실 최장증가수열문제는 처음 접해보았다...) 처음에는 파이썬으로 스택을 이용해서 풀었지만 무슨 이유인지 틀렸다고 나왔다... (틀린 코드) n = int(input()) line_list = [] for i in range(n): line_list.append(list(map(int, input().split()))) del_count = 0 while True: cross = [] for i in ran..
-
알고리즘: 백준 11048번 이동하기 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 27. 22:42
백준 11048번 링크입니다. 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net DFS 인줄 알았지만 시간초과가 나길래 다시 보니 다이나믹프로그래밍이였던 문제 dp를 이차원 리스트로 만들어서 dp[N][M] = (N, M)까지 오기까지의 합이라고 한다면 dp[N][M] = max(dp[N - 1][M], dp[N][M - 1], dp[N - 1][M - 1]) + maze[N][M] 라고 할 수 있다. import sys input = sys.stdin.readline N, M = map(in..
-
알고리즘: 백준 2293번 동전 1 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 25. 20:51
백준 2293번 링크입니다. 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 결론부터 말하면 dp를 이용해 풀어야 풀린다. 시간제한이 0.5초로 dp를 제외한 다른 방법을 쓰기가 까다롭다. 처음에는 dfs를 이용해 풀었지만 시간초과가 나길래 결국은 다른 분의 답을 참고하였다. import sys class Node: # 방문처리를 위해 노드 클래스를 만들었다. def __init__(self, data): self.data = data def dfs(start, tar..
-
알고리즘: 백준 14888번 연산자 끼워넣기(feat. python)알고리즘/백준(BaekJoon) 2020. 8. 24. 22:08
백준 14888번 링크입니다. 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 이렇게 열심히 풀긴 했지만 결국 틀렸다... 하지만 이 문제 하나로 여러가지 경험을 한 것 같아서 만족한다. permutation이라는 편리한 모듈을 알게 되었고 stack과 dfs에 대해서 좀 더 깊게 알 수 있었다. permutation을 통해서 가능한 연산자순서의 경우의 수를 구했고 stack을 통해 필요한 값을 넣고 뺌으로써 원하는 값을 구하는 방법을 체득하였다. i..
-
알고리즘: 백준 11057번 오르막 수 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 24. 11:45
백준 11057 링크입니다. 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 다이나믹 프로그래밍을 이용하면 쉽지만 어떤 구조를 이용하면 좋을지가 가장 어렵다. dp를 이차원리스트로 해서 dp[i][j] = 길이가 i인 끝자리수가 j인 오르막 수 라고 하면 쉽게 해결할 수 있다. (끝자리수를 기준으로 나누는게 포인트) i는 1 ~ 1000 j는 0 ~ 9까지 가능하다 예를 들어 dp[2][3]을 구한다고 하면 dp[2][3] = dp[1][2] + dp[1][1] + dp[1..
-
알고리즘: 백준 11052번 카드 구매하기(feat.c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 18:13
백준 11052번 링크입니다. 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍을 이용하면 쉽게 해결할 수 있다. 우선 코딩하기 전에 dp[n]을 말로 정의하는 게 중요하다. dp[n] = n개의 카드를 구매했을 때 최댓값 라고 하자 dp[n]을 구하기 위해서는 다음과 같은 과정을 거친다. (편의상 k번째 dp[n]을 dpk[n]라고 하자) dp1[n] = dp[n - 1] + packs[1] dp2[n] = dp[n - 2] + packs[2] dp3[n] = dp[n - 3] + packs[3] ..
-
알고리즘: 백준 1697번 숨바꼭질 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 14:40
백준 1697번 링크입니다. 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net bfs를 이용하면 문제가 생각보다 쉽게 풀린다. 최대 가능 인풋이 100000이기 때문에 시간복잡도가 최대 n^2 까지 가능하다고 생각하였다. 최단거리 문제이기도 해서 bfs를 선택하였다. #include #include using namespace std; int visit[100001]; bool check(int x) { //check 함수가 중요한듯! if (x 100001) ret..