알고리즘 썸네일형 리스트형 [BAEKJOON] 1153. 네 개의 소수 사용한 알고리즘 에라토스테네스의 체 (소수 찾기) 풀이 로직 소수 = 2 3 5 7 11 13 17 19 23 29,, 1부터 직접 해본 결과 8부터 4개의 소수로 표현할 수 있다. 8 = 2 + 2 + 2 + 2 / 9 = 2 + 2 + 2 + 3 => 2 + 3 + 2+ 2 n이 8이상이고 n % 2 == 0이면 '2 2'로 시작한다. -> n -= 4 n이 8이상이고 n % 2 == 1이면 '2 3'으로 시작한다. -> n -= 5 새로 갱신된 n을 기준으로 에라토스테네스의 체를 이용해 n보다 작은 소수를 찾는다. 코드 더보기 [LEETCODE] 542. 01 Matrix 사용 알고리즘 DP 사용 풀이 로직 각 원소가 이웃한 가장 가까운 0과의 거리를 구해아한다. 최소값을 구해야하므로 dp를 inf로 두고 진행한다. 왼쪽 위부터 돌면서 왼쪽과 위쪽을 비교해 최소값 찾기 오른쪽 아래부터 돌면서 오른쪽과 아래쪽을 비교해 최소값 찾기 코드 어려웠던 점 처음에 matrix[i][j] == 1인 경우마다 bfs를 이용해 풀었는데, 무한루프로 잘 돌아가지 않았습니다. 더보기 [SWEA] 3462. 선표의 축구 경기 예측 문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWFUsJvqAegDFAVB&categoryId=AWFUsJvqAegDFAVB&categoryType=CODE&&& 문제 경기는 3분 간격으로 30개 경기 진행 적어도 한 팀이 골을 소수로 득점할 확률 = 1 - 모든 팀이 소수로 득점하지 않을 확률 입력은 퍼센트, 출력은 소수점 5자리로 출력 로직 모든 팀이 소수로 득점하지 않는 것 -> A팀 : 1 - 소수로 득점, B팀 : 1 - 소수로 득점 결과 : 1 - (A가 소수로 득점하지 않음 = 1 - A가 소수로 득점) * (B가 소수로 득점하지 않음 = 1 - B가 소수로 득점) A가 소수로 득점한 .. 더보기 [PROGRAMMERS] 최고의 집합 풀이 과정 원소의 합이 s가 되는 경우를 모두 구하고 그중에서 최대값을 찾으려했다. 하지만, n > 2인 경우, 경우가 많기도 하고, 규칙을 찾았다. 규칙 : 원소의 곱이 최대가 되기 위해서는 분산이 가장 작아야한다! 코드 더보기 [BAEKJOON] 4915. 친구 네트워크 문제 출처 : https://www.acmicpc.net/problem/4195 사용한 알고리즘 Union find 문제 -> disjoint set 알고리즘 [ https://gayoung78.tistory.com/75 알고리즘 설명] 풀이 로직 친구 네트워크의 숫자를 위해 하나의 거대한 union network의 parent에 몇명의 친구가 있는지 저장하는 number 딕셔너리를 정의 1. 두 사람의 이름을 입력받은 후, 딕셔너리 parents에 없는 이름이라면 추가해준다. 2. 두 이름을 합쳐 친구관계를 만든다. 3. 현재까지 해당 친구관계를 포함하여 같은 집합에 있는 원소의 개수를 출력한다. 코드 getParent parents 딕셔너리를 참조해 부모노드를 알 수 있다. 입력받는 노드가 부모노드이.. 더보기 [알고리즘] disjoint-set(union find) 알고리즘 1. union find(disjoin-set)란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 다수의 노드들 중에 연결된 노드를 찾거나, 노드들을 합칠 때 사용하는 알고리즘 1~10까지 있다고 가정할 때, 아래와 같은 연결 구조를 가지고 있다고 가정하자. [ 진행과정 ] 1과 2가 연결되었으면, 원소 2의 정보를 1로 바꾼다. 1, 2, 3, 4가 모두 연결되어있어 같은 집단에 속하지만, 처음에는 각자의 부모노드를 작성한다. 3과 2는 연결되어있다. -> 3의 연결정보를 2로 바꾼다. -> 2와 1은 연결되어있다. -> 3과 1은 연결되어있으므로 3의 연결정보를 1로 바꾼다. 구현 초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화 Union(합치.. 더보기 [LEETCODE] 51. N-Queens 문제 출처 : https://leetcode.com/problems/n-queens/submissions/ 사용한 알고리즘 backtracking 풀이로직 ㄴㅇㄹㅇㄴ ㄴㅇㄹ 코드 어려웠던 점 backtracking 문제를 간만에 풀어 어려웠고, 이걸 한번에 어떻게 처리하고 다시 돌릴지 고민을 많이했습니다. 제가 푼 과정이 N-Queens의 갯수를 세는 것을 빠르게 할 수 있는 코드였기 때문에 모든 경우를 넣은 후 다시 올바른 형태로 바꿔 집어넣어야했다. board를 바꿔가면서 진행하는데, answer에 넣고나면 그 board를 이용해 바꾸는 것이기때문에 최종값에 계속 초기 board값이 들어갔다 -> board가 계속 바뀌기 때문에 answer의 board도 함께 바뀌는것이다! deepcopy를 이용해서.. 더보기 [알고리즘] heap 구조 1-1. 힙 자료구조 완전 이진트리 중 하나 -> 웃너순위 큐를 위해 만들어진 자료구조 여러개의 값들 중에 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음) heapq 모듈은 이진트리 기반의 최소힙 자료구조를 제공한다. 1-2. 힙 종류 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 값보다 크거나 같은 완전 이진트리 가장 큰 값은 언제나 index = 0에 위치함 (=> 이진트리의 루트에 위치) heap[k] >= heap[2*k+1] and heap[k] >= heap[2*k+2] 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 값보다 작거나 같은 완전이진트리 가장 작은 값은 언제나.. 더보기 이전 1 2 3 4 ··· 9 다음
