전체 글 (75) 썸네일형 리스트형 LIS (Longest Increasing Sequence) 안녕하세요. LIS (Longest Increasing Sequence)에 대해 알아보겠습니다. 개념 LIS는 최장 증가 부분 수열이라고 합니다. 수열에서 가장 긴 증가하는 부분 수열입니다. arr에서 가장 긴 부분 수열은 {2, 4, 8, 9} 입니다. 이를 LIS라고 말하고 LIS의 길이는 4 입니다. (부분 수열은 연속하지 않아도 됨) 풀이 LIS를 구하는 여러 방법 중에서 아래 2가지 방법을 알아보겠습니다. DP 사용 이분 탐색 사용 DP 사용 과정 dp[i]를 arr[i]를 마지막 원소로 갖는 LIS의 길이 라고 둔다면, 0 [BOJ 20942] 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회 백준 20942번 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회 https://www.acmicpc.net/problem/20942 20942번: 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회 첫 번째 자리에는 $15$세의 참가자가 이미 배치되어 있다. 두 번째, 세 번째, 네 번째 자리에 각각 $17$세, $12$세, $19$세의 참가자를 배치하면, $15 \operatorname{\&} 17 = 1$, $15 \operatorname{\&} 12 = 12$, $12 www.acmicpc.net 문제 N개의 자리가 있다. 각각의 자리에는 8세 ~ 19세의 참가자를 배치해야 한다. M개의 연산에 대해, 두 자리에 대한 비트 연산(bitwise and, bitwise or)을 해서 특정 .. [BOJ 3648] 아이돌 백준 3648번 아이돌 https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 문제 한 심사위원이 두 표를 행사합니다. 행사한 두 표 중에 적어도 하나는 결과가 만족해야합니다. 추가로 상근이는 반드시 합격 목록에 들어가 있어야 합니다. 풀이 4 3 1 2 -2 -3 2 4 예제 입력이 위와 같이 주어집니다. 총 3명의 심사위원이 두명한테 투표를 행사했습니다. 양수는 해당 number가 합격해야 한다는 의미이고, 음수는 해당 number가 불합격해야 한다는 의미입니다. 1) 1 2 1번이 불합격하면.. 2-SAT 안녕하세요. 오늘은 2-Satisfiability 에 대해 알아보겠습니다. 개념 전체 식이 True가 되도록 변수에 True 또는 False 값을 배정하는 문제입니다. True 또는 False 2지 선다이기 때문에 2-SAT 이라 불립니다. X, Y, Z 변수에 True 또는 False 값을 할당해 전체 라인이 True가 되도록 만들어봅시다. Line 1 X : True, Y : False, Z : False 가능 Line 2 X에 True 또는 False 를 넣어도 만족하지 않음 불가능 풀이 그래프 모델링을 통해 2-SAT을 풀 수 있습니다. (X or Y) X 또는 Y가 true가 되어야 합니다. 만약 X가 false 라면, Y는 반드시 true가 되어야 합니다. (not X -> Y) 만약 Y가 f.. [BOJ 4305] 성격 진단 테스트 백준 4305번 성격 진단 테스트 https://www.acmicpc.net/problem/4305 4305번: 성격 진단 테스트 각 테스트 케이스마다 정답을 출력한다. 한 줄에 하나의 그룹(partition)을 알파벳순으로 출력하며, 각 그룹의 알파벳순으로 가장 앞에 오는 원소 기준으로 그룹들도 알파벳순으로 출력되어야 한 www.acmicpc.net 문제 5지 선다 중에 1개를 선택하는 성격 진단 테스트 입니다. A B C D E 중에 A를 선택하면, A가 B, C, D, E 보다 더 선호하는 보기라는 것입니다. 이렇게 여러 문항을 테스트 하다가 모순이 생길 수 있습니다. 모순이 있는 집단을 찾는 문제입니다. 풀이 모순이 생긴다는 의미는 A 보다 B를 선호한다고 골랐는데, 다른 문항에서 B 보다 A를 .. 강한 연결 요소 (Strongly Connected Component) 안녕하세요. 오늘은 줄여서 SCC 라고도 불리는 강한 연결 요소에 대해 알아보도록 하겠습니다. 사이클 유향 그래프에서 사이클을 찾는 알고리즘을 SCC 알고리즘 이라고 합니다. 하나의 SCC에 속하는 정점들은 서로에게 도달할 수 있는 것이 사이클 입니다. {1, 2, 5} , {3, 4, 8} , {6, 7} 은 각각 서로 다른 SCC를 이루고, 그 안에서 서로 도달가능한 집합입니다. 알고리즘 SCC를 찾는 알고리즘으로 2가지가 있습니다. 둘 다 알아보도록 하겠습니다. 코사라주 알고리즘 타잔 알고리즘 코사라주 알고리즘 시간, 공간적 비용이 타잔 알고리즘보다 크다는 단점 직관적이고 이해하기 쉽다는 장점 타잔 알고리즘보다 상대적으로 구현 난이도가 낮다는 장점 또한 존재합니다. 작동 과정 모든 노드가 방문될 때.. 최소 스패닝 트리 (Minimun Spanning Tree) 안녕하세요. 오늘은 최소 스패닝 트리에 대해 알아보겠습니다. 스패닝 트리 중 가장 가중치가 작은 트리 스패닝 트리가 무엇인지 먼저 알아야합니다. 그래프 그래프는 위 그림과 같이 노드와 간선으로 구성되는 자료구조입니다. 트리 그래프 그림을 보면 사이클이 존재합니다. 사이클이란, 어떤 노드에서 출발해서 간선을 최대 1번만 이용해서 자신 노드로 돌아오는 것을 말합니다. (3 - 4 - 5 - 3, 3 - 2 - 5 - 3 등) 트리는 사이클이 없는 acyclic graph 라고 합니다. 스패닝 트리 관련 유투브 영상을 찾아봤는데 영어로 아래와 같이 설명합니다. hit all vertices of graph G 그래프의 모든 노드에 도달하는 트리라는 뜻입니다. 트리이기 때문에 사이클이 없는 것을 확인할 수 있습.. A* algorithm 안녕하세요. 오늘은 A* algorithm (A star algorithm) 에 대해 알아보겠습니다. 최단 경로 휴리스틱 알고리즘 시작 정점 s에서 끝 정점 e 까지의 최단 경로를 근사화한 값을 구하기 위한 최단 경로 알고리즘 입니다. 휴리스틱 알고리즘 중 하나 입니다. 최단 경로를 찾는데 가장 유명한 알고리즘이 다익스트라 알고리즘 입니다. 다익스트라 알고리즘은 시작 정점에서 현재 정점까지 걸린 비용이 작은 것을 우선으로 탐색합니다. A* algorithm은 f cost가 작은 것을 우선으로 탐색합니다. f cost = g cost + h cost g cost = 시작 정점에서 현재 정점까지 걸린 비용 h cost = 현재 정점에서 끝 정점까지 걸릴 예상 비용 g cost가 다익스트라 알고리즘에서 우선시.. 이전 1 ··· 6 7 8 9 10 다음
