https://www.acmicpc.net/status?user_id=freemjstudio&problem_id=15666&from_mine=1 채점 현황 www.acmicpc.net 두번째 예시로 생각해보자 i) 중복 제거 n = 4, m = 2 그리고 후보로 주어진 숫자들은 9 7 9 1 이다. 어처피 우리는 중복해서 같은 숫자를 선택할 수 있으므로 중복을 set() 함수를 통해 제거한 후 다시 list로 형변환한다. 그러면 9 7 1 세가지가 남는다. 비내림차순이라는 조건이 주어졌으므로 -> 오름차순으로 바꿔봅시다. 그러면 후보들을 정렬했을 때 1 7 9 가 됩니다. ii ) for문과 재귀함수 호출 우리는 이제 1 7 9 세가지 선택지가 있고 이 세가지 숫자들을 for문을 통해서 순회하며 하나씩 ..
파이썬
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1) 적록색약이 아닌 사람 : array를 바꿀 필요 없이 BFS로 총 구역이 몇개인지 구한다. -> 어떻게 count를 하는가 ???가 또 관건인데... bfs에서 같은 문자가 계속 나오면 배열 c를 1로 표시를 해둔다. 그러면 이경우 R와 같은 위치에는 1이 나머지 배열은 아직 0이겠지요 ?? 이후 이중 for 문에서 if c[i][j] == 0: bfs 배열 c[i][j] 값이 0이면..
명령어 실행전에 python 3.x.x 설치를 해주세용 맥은 기본으로 python 2.x.x가 설치되어있을 테지만 이는 권장하지 않는다네요 1. 가상환경을 생성할 디렉토리로 이동 ex) cd Users/freemjlab 2. python3 -m venv ./(생성하고자 하는 가상환경 이름) python3 -m venv ./mysite python3의 venv 모듈을 통해 가상환경을 생성해줍시다. 짠 !! 이렇게 mysite 디렉토리가 생긴걸 확인할 수 있죵?? 3. 가상 환경 활성화 cd mysite/bin/ 경로로 이동해서 source activate 명령어를 입력합니다 (가상환경 이름) 이 표시되면 활성화 상태입니다! 4. 가상 환경 비활성화 동일한 경로에서 deactivate 명령어를 쳐주세요 이때..
https://sinclairstudio.tistory.com/24 union-find 알고리즘을 알아보자! in Python 1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노 sinclairstudio.tistory.com Union find 정리 글은 위에 !! 이건 서로소 집합인지 판별하고 합집합 연산을 수행하는 알고리즘이다 크루스칼 알고리즘은 무엇인가 !! 우리가 그래프 알고리즘에서, 최저비용 경로를 계산할 때 사용할 수 있다 다익스트라는 최단거리 ! 크루스칼은 최저비용 ! 1. 신장트리 하나의 그래프가 있을 때, 모든 노드를..
1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노드의 개수가 V, 간선의 개수가 E인 그래프가 있을 때, 인접행렬은 O(V^2) 만큼의 메모리가 필요하다 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(1)의 시간으로 알아낸다. 2) 인접 리스트 (Adjacency List) : 리스트로 연결하여 사용하는 방식 공간복잡도: 간선 개수만큼인 O(E) 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(V)의 시간으로 알아낸다. 2. 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합이다. 서..
1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노드의 개수가 V, 간선의 개수가 E인 그래프가 있을 때, 인접행렬은 O(V^2) 만큼의 메모리가 필요하다 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(1)의 시간으로 알아낸다. 2) 인접 리스트 (Adjacency List) : 리스트로 연결하여 사용하는 방식 공간복잡도: 간선 개수만큼인 O(E) 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(V)의 시간으로 알아낸다. 2. 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합이다. 서..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제를 풀 때 핵심적인 아이디어는, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 다이나믹 프로그래밍 알고리즘을 수행해야 한다는 것이다 ! 문제에서 주어진 예시 N = 7 인 경우에는 6일과 7일자의 상담을 수행하면 7을 넘기게 된다. 이와 같은 경우를 고려하기 위해서 뒤에서부터 DP를 수행하여 저장한다. 경우를 나누는 것은 두가지로, i번째 날의 상담을 수행했을 때 n을 넘는다면 이 경우는 불가능하니까 value를 0이라고 생각하여 dp 그래프에 0 값으로 처리를 한다. dp[i] = dp[i+1] # 단, 여기서 dp list의 맨 ..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 유형 : 구현 + dfs 문제집에는 dfs로 분류되어 있었는데 구현 유형스러웠던 문제 ㅋㅋ 1. 벽을 설치한다 3개까지 -> board 2차원 배열 돌면서 board[i][j] == 0 이면 벽 설치 가능 2. 3개 다 설치했으면 바이러스를 퍼뜨려 본다. 바이러스 퍼뜨릴 때 재귀호출해서 상하좌우 이동한다. 3. 바이러스를 퍼뜨린 후 안전지대를 계산한다.그리고 원래 가지고 있던 최대 안전지대 값이랑 비교하..
