Computer Science/Algorithm48 [프로그래머스] 코딩테스트 개념 해시(딕셔너리) / 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. [백준] 7576번 토마토 상자 - 시간초과.. BFS 활용하자 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 예시 코드 모두 다 돌아가지만 시간 초과가 나온 코드 ㅠㅜㅠㅜ 속상하다. # BOJ_7576 # 모든 토마토가 익는 최소 날짜 구하고 싶어. 결과는 0, -1, 자연수 # 토마토는 상하좌우에 익은 토마토가 있을 때 익어. # 그렇다면 익은 토마토를 중심으로 인접한 토마토로 이동해야하니까 # DFS보다는 BFS가 적합하겠네. # 아니다 굳이 BFS를 쓸 필요 없이 # 인접한 익지 않.. 2023. 2. 20. list, dict, set은 mutable 하다. Shallow Copy & Deep Copy 문제 출처: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net # 입력 받은 모든 토마토 상태 그래프 graph = [list(map(int, input().split())) for _ in range(n)] # 모든 토마토가 익었을 때의 그래프 finish_graph = graph print(graph) for i in range(n): for j in range(m): if finish_graph[i][j] == 0: fini.. 2023. 2. 20. BFS DFS 정복하기 각 문제 유형별 풀 방법 정리 1) 그래프의 모든 정점을 방문해야하는 문제 DFS, BFS 뭐든 상관없다. 편한걸 쓰면 된다. 2) 경로의 특징을 저장하는 문제 예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제. 각각의 경로마다 그 특징을 저장해두어야하는 문제는 DFS를 사용한다. 3) 최단거리를 구하는 문제 미로찾기등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐수도 있지만 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리다. 4) 검색대상그래프가 많이 클때DFS가 좋다고한다. 5) 검색대상의 규모가 별로 크지않고 검색시작지점으로부터 원하는 대상이 별.. 2023. 2. 20. 약점보완: Dynamic Programming " 계속 쓰일 값은 저장해놓고 가져다 쓰자" 메모리를 조금 더 쓰지만, 수행 시간을 단축시킬 수 있다. 큰 문제를 작은 문제들로 분할하여 작은 문제들을 푼 결과를 이용해서 큰 문제를 해결하는 방법 DP를 사용하려면? 1. 큰 문제를 작은 부분 문제로 나눌 수 있을 때 2. 작은 문제에서 구한 정답을 큰 문제에서 사용할 때에도 동일할 때 DP으로 문제를 어떻게 해결할까? 1. 메모이제이션 (Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다 같은 정보를 다시 호출하면 메모했던 결과를 그대로 가져옵니다 값을 기억해둔다는 점에서 캐싱(caching)라고 합니다 '한 번 계산한 결과를 메모리 공간에 기록했다가 필요할 때 .. 2023. 2. 9. [백준] 2164번 카드2 - 시간초과, 짝수 홀수 인덱스만 추출하기 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 처음에는 문제 그대로 구현하였다. num = n square = 0 while num >= 1: square += 1 num /= 2 square = square - 1 print(2 ** square) 그리고 짝수 홀수로 나뉘네 # 카드 구성 설정 cards = [] if n >= 8: n // 8 for i in range(1, n + 1): cards.append(i) # 규칙 그대로 구현해.. 2023. 2. 2. [백준] 10816번 숫자카드2, 시간초과 - 이분탐색만으로도 안됨, bisect 모듈! https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분 탐색으로 아래 풀이 처럼 풀었는데도 시간초과가 뜬다. # BOJ_10816 # 입력 n = int(input()) cards = list(map(int, input().split())) m = int(input()) show_cards = list(map(int, input().split())) # 두 카드 목록 모두 오름차순으로 정렬한다. cards.sor.. 2023. 1. 25. 이전 1 2 3 4 5 6 다음
