본문 바로가기

Computer Science/Algorithm48

[백준] 14888번 연산자 끼워넣기 - 백트래킹(DFS) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net DP로 풀 수 있지 않을까 했는데, 백트래킹을 이용하여 DFS로 짤 수 있어야 풀 수 있는 문제였다. 백트래킹은 한정된 조건을 제시한 문제를 풀 때 쓰는 전략이다. 쉽게 설명해서 모든 경우의수를 시도하여 문제의 정답을 찾아나가지 않고(다중 for문) 시간을 단축하기 위해 한정된 조건에서 BFS나 DFS와 함께 구현한다. 백트랭킹의 특성 한정 .. 2023. 3. 5.
[백준] 드디어 실버에서 골드로 짜쟌 하루에 평균 한 문제씩 2달간 풀면 브론즈에서 골드로 넘어갈 수 있는 것 같다. 마지막 문제는 특정 지점을 경유해서 1번에서 n번 노드로 가는 최단 경로를 구하는 문제였다. https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 내가 푼 풀이 # BOJ_1504 # 1. (1, v1) + (v1, v2) + (v2, n) # 2. (1, v2) + (v2, v1) + (v1, n) # 1과 2중 최솟값.. 2023. 3. 3.
[백준] 1043번 거짓말 가능한 파티수 - set 활용 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 해당 문제를 각각의 파티를 m회차 점검하며, 진실을 듣게 될 사람을 추가하는 방식으로 구현하였다. 중복을 없애기 위해 extend와 set을 적절히 활용했고, for party in party_list: 을 자주 활용했다. 1. List를 활용하여 구현(코드가 길고 가독성 떨어짐) # BOJ_1043 def add_know_list(people_list): global known_list for person.. 2023. 3. 3.
[백준] 플로이드 워셜(Floyd-Warshall) 알고리즘 11403번 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 2차원 그래프에서 각 노드끼리 서로 갈 수 있는 경로가 있는 지 확인하는 문제 i에서 j로 가는 간선이 존재하는가 - 1 존재하지 않는가 - 0 1. BFS를 이용하여 구현 # BOJ_11403 from collections import deque import sys input = sys.stdin.readline def bfs(start, end): q = deque() visited = [[False] * n for _ in range.. 2023. 3. 3.
[백준] 11724번 무방향 그래프 DFS BFS - 재귀에러 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. DFS - 재귀함수로 그래프 탐색 재귀함수로 구현한 DFS로 풀었더니 런타임 에러가 뜬다. 아마도 재귀 함수가 문제 제한 보다 더 많이 중첩되어서 에러가 뜨는 것 같다. # BOJ_11724 # dfs def dfs(start, visited): global graph if visited[start]: return False vi.. 2023. 2. 28.
[백준] 18870 - 이분탐색 말고, 딕셔너리 활용해봐 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 이분탐색은 python3는 안되고 pypy3만 돌아간다. # BOJ_18870 import sys input = sys.stdin.readline # 입력 n = int(input()) nums = list(map(int, input().split())) set_nums = list(set(nums)) # print(set_nums) sort_nu.. 2023. 2. 27.
[백준] 1697번 숨바꼭질 아니 DP로 풀 수 없어. 이건 BFS야 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net DP로 풀려다가 도저히 범위를 잡지 못해서 .. 놔줌 ㅠ # BOJ_1697 # 입력 me, sister = map(int, input().split()) dp[1] = dp[x] = dp[x//2] + 1 # # # 최소 시간 찾기 # root_count = 0 # root_sister = sister # while root_sister > me: # root_sist.. 2023. 2. 27.
[백준] 11726번 타일 쌓기 문제 - DP로 풀 수 있었잖아 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net dp로 풀려다가 타일 앞에 눕힌 것(2), 세운 것(1) 씩 추가해주면 이전 dp[n - 1] 앞에만 붙이면 되는 거였는데.. 대칭 구조까지 생각하고 복잡하게 생각해서 단순 구현했다. 1. 수학적으로 풀이 - 중복순열 아래아 같이 1과 2을 더하는 순서를 고려해서 n을 만드는 갯수를 구해보자. 1. n을 2로 나눈(//)수를 two_mod 2. 0, 1, 2, 3, ... two_mod까지 2. 중복순열 갯수 세기 1.. 2023. 2. 27.
[백준] 1629번 분할정복 알고리즘 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net # BOJ_1629 # 입력 a, b, c = map(int, input().split()) # result = (a ** b) % c result = 1 for i in range(b): result *= a result %= c print(result) 분할정복 알고리즘 순서 1. 분할 해결할 문제를 시간복잡도를 낮추기 위해서 여러 개의 작은 부분 문제들로 분할한다. 2. 정복 나눈 작은 문제들을 각각 해결한다. 3. 통합 필요 시 해결된 해답을 모은다 # .. 2023. 2. 25.

티스토리툴바