본문 바로가기

전체 글204

[백준] 플로이드 워셜(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.
[프로그래머스] 코딩테스트 개념 해시(딕셔너리) / Greedy 1. 해시 문제 https://programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아래 코드처럼 remove를 사용했더니 def solution(participant, completion): d = {} for x in completion: participant.remove(x) answer = participant[-1] return answer 37점으로 시간 초과가 나왔다. 아마도 remove 모듈이 시간 복잡도 O(n)라서 총 O(n^2)이 되었고, 문자열이라서 메모.. 2023. 2. 24.
다익스트라(Dijkstra) 최단 경로 알고리즘 최단 거리 알고리즘 1. 다익스트라 최단 경로 알고리즘 2. 플로이드 워셜 3. 포드 알고리즘 다익스트라 최단 경로 알고리즘 하나의 정점에서 나머지 모든 정점까지의 최단 거리를 찾는 알고리즘 그리디와 DP 알고리즘이 적용된다. "방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정 반복 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해 > 마지막 노드에 대해서는 해당노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없음. 이미 확정된 상태로 갱신 안될 거기 때문에. 방법1. 간단한 다익스트라 알고리즘 - O(V^2) 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색) 노드 개수.. 2023. 2. 23.
[백준] 2292 벌집문제 - 브론즈2인데 왜 못 풀었을까. 간단한데 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net # BOJ_2292 # 입력 n = int(input()) # 위치 1부터 시작 position = 1 # 시작점부터 이동 갯수를 count = 1로 세준다. move_cnt = 1 while n > position: # 6의 배수로 증가 position += move_cnt * 6 move_cnt += 1 print(move_cnt) 2023. 2. 22.

티스토리툴바