# Foundation (88) # Foundation/알고리즘 C++ Combination 함수 해당 포스트 대신, 아래의 포스트를 사용해주세요. [코딩테스트 대비] 순열 및 조합 알고리즘 개요 순열 Permutation과 조합 Combination은 코딩테스트에서 매우 빈번하게 사용되는 도구 중 하나입니다. 어떤 배열의 순열 또는 조합을 구하라! 라는 직접적인 문제는 출제되지 않지만, 이것을 사용 aerocode.net C++ Combination Overview 어떤 집합에서 r개를 선택하여 얻을 수 있는, 모든 조합(Combination)을 가져온다. 예를 들어, 벡터 집합 = {"a", "b", "d"} 에서 2개를 선택하여 얻을 수 있는 조합은 다음과 같다. b d a d a b 다른 예로, 비트셋 집합 = 0b1101 에서 2개를 선택하여 얻을 수 있는 조합은 다음과 같다. 1100 10.. 2019. 10. 20. 16:19 # Foundation/알고리즘 비트셋으로 집합 표현하기 (Bitset) 비트셋이란? 비트셋이란, 말 그대로 Set of Bits를 의미한다. 즉, 여러개의 비트가 모여서 하나의 집합을 형성하는 것 이다. 아래는 8비트를 나타내는 비트셋의 예시이며, 비트셋의 인덱스는 오른쪽에서 왼쪽으로 증가함에 유의하자. 문제 제기 과일을 도메인으로 갖는 공간을 생각해보자. 아래의 집합은 서로 같은가? 다른가? vector A = {사과, 포도, 딸기} vector B = {사과, 딸기, 포도} 포도와 딸기의 위치가 바뀌긴 했지만, 그 집합의 구성원은 일치하므로 같은 집합이다. 하지만 벡터로 표현된 두 집합이 동치인지 확인하는 작업은 복잡하며, 벡터의 크기가 커질수록 느려진다. 비트셋을 이용한 집합표현 (1) 비트셋은 정규화된 집합을 표현하는데 매우 효과적이다. 각 과일마다 비트의 인덱스를 .. 2019. 10. 20. 13:31 # Foundation/알고리즘 그래프 이론 (1) 그래프란?정점(Vertex)과, 두 정점을 잇는 간선(Edge)의 집합.간선에 의해 이어진 두 정점은 서로 인접(Adjacent)하다고 한다. [그림 01] 일반적인 그래프 그래프의 방향성간선에 화살표 표시가 있다면, 해당 방향으로만 움직일 수 있다. 그래프의 방향성간선에 화살표 없음 : 무향 그래프, 양방통행.간선에 화살표 있음 : 유향 그래프, 일방통행. [그림 02] 무방향성 그래프 [그림 03] 방향성 그래프 위의 방향성 그래프에서는 3에서 5로 갈 수 없다.간선에 방향성이 부여되었기 때문. 정점의 차수무향 그래프에서 정점에 연결된 간선의 수를 차수(Degree)라고 한다. 유향 그래프에서는 더욱 세부적으로 구분한다.입력 차수 (in-degree) : 해당 정점으로 들어오는 간선의 수.출력 차수 .. 2019. 7. 23. 18:35 # Foundation/백준풀이 [LCS] 백준 1958 :: LCS 3 LCS 3 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB29661390108848.615%문제문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.입력첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다)출력첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한.. 2019. 7. 10. 00:30 # Foundation/백준풀이 [LCS] 백준 9252 :: LCS 2 LCS 2 성공스페셜 저지시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB83723392258841.897%문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.LCS가 여러 가지인 경우에는 아무거나 출력한다.예제 입력 1 복사ACAYKP CAPCAK 예제 출력 1 복사4 ACAK 문제 풀이1.. 2019. 7. 10. 00:21 # Foundation/백준풀이 [LCS] 백준 9251 :: LCS LCS 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB138355899435242.097%문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 1 복사ACAYKP CAPCAK 예제 출력 1 복사4 문제 풀이1차 풀이 ( 5896 KB, 8 ms)Top-Down 방식의 LCS 알고리즘 활용.두 단어 .. 2019. 7. 10. 00:15 # Foundation/백준풀이 [LIS] 백준 4198 :: 열차정렬 열차정렬 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB123824616621.364%문제에린은 엔지니어이자, 기차를 운전하는 기관사입니다. 또한 그녀는 각 열차를 구성하는 차량을 배열하는 일도 합니다. 그녀는 차량들을 정렬할 때, 열차의 전면에 가장 무거운 차량을 놓고, 후미로 갈수록 중량이 감소하는 순서로 차량을 넣는 것을 좋아합니다.불행하게도, 차량을 배열하는 일은 쉽지 않습니다. 기존에 구성된 열차에 다른 차량을 끼워넣는 일은 비실용적이어서 하지 않기에, 한 차량은 오로지 열차의 전면 혹은 후미에만 추가하는 것이 가능합니다.차량들은 미리 준비된 순서에 따라 역에 도착합니다. 에린은 각 차량이 기차역에 도착할 때, 전면 혹은 후미에 차량을 추가하거나, 차량을 열차에 추가하는.. 2019. 7. 9. 11:54 # Foundation/백준풀이 [LIS] 백준 2568 :: 전깃줄 - 2 전깃줄 - 2 성공스페셜 저지시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB3233102759032.435%문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 .. 2019. 7. 9. 11:48 이전 1 2 3 4 5 6 ··· 11 다음
