본문 바로가기

전체 글

[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) 부모 노드의 키 값이 자식 노드의 값보다 작거나 같은 완전이진트리 가장 작은 값은 언제나.. 더보기
[알고리즘] LCS 알고리즘 1. LCS 알고리즘이란? - LCS = 최장 공통부분 문자열 - Substring : 연속된 부분 문자열 ex. x = 'CCAYCKP' y = 'CCAPCAK' - Subsequence : 연속되지 않은 부분 문자열 ex. x = 'ACAYKP' y = 'CAPCAK' 2. LCS 알고리즘 구현 (LCS 길이찾기) 문제 : [백준] 9251. LCS https://www.acmicpc.net/problem/9251 [풀이과정] 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 3 3 4 P 0 1 2 3 3 3 4 x와 y에 가장 최근에 추가된 글자가 서로 같으면 b.. 더보기
[SWEA] 1264.이미지 유사도 검사 문제링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Q_MqIvUCFAZN&categoryId=AV18Q_MqIvUCFAZN&categoryType=CODE&&& 시간복잡도 On(n^2) 사용한 알고리즘 LCS(최장 공통부분 수열) 알고리즘 풀이로직 LCS 알고리즘 사용 [https://gayoung78.tistory.com/72] 코드 어려운점 이 알고리즘을 알기 전까지 이런 로직으로 구현 x='RBKBGRBGGG', y='BGKRBRKBGB'를 비교할 때 x가 R일 때 y에 있는지 확인하고, x가 RB일 때, y의 index를 활용해서 RB가 있는지 확인하는 방식으로 가려고 했다. 더보기
[LEETCODE] 17. Letter Combinations of a Phone Number 시간복잡도 O(n^3) 사용한 알고리즘 무슨 알고리즘을까요..? 풀이 로직 각 숫자가 가지고 있는 문자열을 설정한다 0 더보기
[LEET CODE] 131. Palindrome Partitioning 시간복잡도 O(n^2) 사용한 알고리즘 재귀 알고리즘 풀이 로직 Palindrome인지 확인하는 함수 만들기 Palindrome인 문자라면 list에 추가하고, 그 다음 문자부터 다시 확인 -> 재귀 코드 어려웠던 점 반복되는 과정이라 재귀를 사용해야한다는 것은 파악했지만, 어떻게 처리해야 i에 따라서 추가해줄 지에 대한 고민에서 시간이 생각보다 오래걸렸습니다. 더보기

티스토리툴바