알고리즘
-
Hash / Hash Table / Hash Function 및 백준 문제알고리즘/개념 정리 2021. 8. 11. 22:10
해시 함수(Hash Function) 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수. → 해시 함수를 구현하는 방법에 따라서 서로 다른 문자열이 같은 고정 문자열로 되기도 하는데, 이를 충돌이라고 한다. key를 해쉬한 결과를 배열의 index로 사용하게 된다. 해시 충돌(Hash Collision) 서로 다른 문자열을 Hash한 결과가 동일한 경우 해시 함수를 H()라고 했을 때 , H(s1) = H(s2)인 경우 Chaining 또는 Open Addressing을 통해서 해결해야 한다. index가 겹치면 선형 검색을 하는 경우도 있음 → Hash가 항상 O(1)을 보장하는 것은 아님. 해시 테이블(Hash table) Key, Value로 된 쌍을 저장하는 구조 Hash table V..
-
알고리즘 언어 선택 / 언어 별 장단점알고리즘/etc 2021. 3. 14. 00:55
알고리즘 언어 선택 대신 해주실 분 구함.. 일단 나는 학부 2학년부터 4학년까지 모든 알고리즘을 C++로만 풀었었다. 나때는 그랬다 나때는..! 알고리즘을 C++ 외의 언어로 푸는 사람들이 거의 없었다고 그래서 너무 당연히 알고리즘을 C++로 풀어왔었는데 이게 C++이라는 언어를 알고리즘 외에는 쓸일이 없으니까 점점 언어를 바꿔야 하나 싶은 생각이 들고있다. 오늘 Java로 처음 알고리즘을 풀어봤는데 아니 이건 사람할짓이 아니다. 인풋만 몇줄이냐고 에바야진짜 이게 c++ 인풋이고 이게 Java Output인데 그냥 이렇게보기엔 별 차이 없어보이지만 java가 훨씬 복잡하다 ㅠ(이 문제가 그나마 간단한 편) 그렇다고 자바를 안쓰자니 자바 기본적인 문법에 대한 이해도가 너무 낮아지고있어서 걱정이다. 머리가..
-
[백준 / BOJ] 2933 :: 미네랄알고리즘/BOJ(C++) 2021. 2. 6. 22:56
www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 문제 설명 : 막대기를 한번은 왼쪽에서 오른쪽으로, 다른 한번은 오른쪽에서 왼쪽으로 던질 것이다. 이때 각 방향으로 탐색해서 오면서 처음 만나는 미네랄을 캘 것이다.(미네랄이 있는 곳이 0 처리됨) 미네랄은 클러스터(군집)이 있다. 상하좌우로 연결된 미네랄은 같인 미네랄 클러스터이다. 미네랄을 캐면서 하나의 미네랄이 없어지는데, 이 때 기존에 연결되어 있던 클러스터가 서로 분리 될 수도 있다. 그러면 그 두 클러스터 중 하나..
-
[백준 / BOJ] 16988 :: Baaaaaaaaaduk2 (Easy)알고리즘/BOJ(C++) 2021. 1. 2. 21:35
www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net Easy..? 다들 알고리즘 잘하시나봐요..이게 easy라니 ㅠ 문제 : 우선, 앞에 장황한 쓸데없는 설명은 안읽어도 됩니다. 결론적으로 말하면, 우리는 돌 두개를 놓을 것인데, 돌 두개를 놓아서 상대방 돌을 최대한 많이 따먹어야 합니다. 상대방 돌을 딸 수 있는 조건은 Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을..
-
[백준 / BOJ] 1600 :: 말이 되고픈 원숭이알고리즘/BOJ(C++) 2020. 12. 30. 23:03
www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 설명: - 시작 지점(제일 왼쪽, 제일 위 (H,1))에서 도착지점 (제일 오른쪽, 제일 아래(1,W))까지 이동하는 최단 거리를 찾자 - 이동할 수 있는 방법에는 두가지가 있다. 1. 체스판의 나이트 처럼 이동하는 경우(현 자리에서 8가지) 2. 인접한 칸으로 이동하는 경우(현 자리에서 4가지) - 이 때 1번의 방법으로 이동하는 경우는 최대 K번까지 사용 가능하다. 풀이 / 구현 방법 ..
-
비트마스킹(BitMasking) 정리알고리즘/개념 정리 2020. 12. 27. 14:56
비트마스킹(BitMasking) 정리 목차 비트마스킹이란? 비트 켜고 끄기 활용 방법 비트마스킹이란? 비트 마스킹이란, 어떤 정수 값을 비트를 이용해 이진수로 표현하는 방법을 말합니다. 예시를 하나 들어보겠습니다. 책상 5개가 일렬로 있는데 ( . . . . . ) 여기에 사람을 앉히는 경우는 (OXXXXX, OOXXX) 등등 2^5 가지가 있겠죠 이 상태를 모두 표현하여 가지고 있고 싶은데 이 때 활용할 수 있는 방법이 비트마스킹입니다. ex) OOOXX > 이 경우에는 11100(2) == 28 OXXXXO > 이 경우에는 10001(2) == 17 등등 이런식으로 상태를 저장하여 활용하는 방식입니다. 비트마스킹의 이점은 더 적은 메모리로 많은 상태를 표현할 수 있다는 것입니다. 비트 켜고 끄기 비트..
-
LCA(Lowest Common Ancestor) / 최소 공통 조상 알고리즘알고리즘/개념 정리 2020. 12. 27. 01:26
LCA(Lowest Common Ancestor) / 최소 공유 조상 목차 1. LCA란? 2. O(N) LCA 알고리즘 3. O(logN) LCA 알고리즘 LCA란? LCA란 말 그대로 최소 공유 조상이다. 그래프에서 두 노드 각각의 부모들을 쭉 타고 올라갔을 때 최초로 공유하는 부모를 말한다. 이 예시에서 노드 5와 노드 3의 최초 공유 조상은 1이 된다. 이 경우에 노드 12와 노드3의 최소 공유 조상은 1이 된다. O(N) LCA 알고리즘 자 그러면 이제 LCA 알고리즘을 구현해 봅시다. LCA 구현을 위해 3가지 단계가 필요합니다. 각 노드들의 depth를 구하여 가지고 있는다 ( depth : root 노드부터 자기 노드까지의 거리(깊이)) LCA를 구하려는 두 노드 중 더 깊은 노드의 dep..
-
[백준] 1025 :: 제곱수 찾기알고리즘/BOJ(C++) 2020. 12. 21. 00:11
www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 : 문제 설명 세상 난해해.. 자, 차분히 이해를 해 봅시다. 문제를 읽어보면 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열 이라는 문구가 나옵니다. 이게 무슨 뜻이냐 하면 map[i][j] 이렇게 있을 때 (i,j)의 숫자를 뽑는겁니다. 차례로 (x1,y1) , (x2,y2) , (x3, y3) 뭐이런식으로 뽑아 나가겠죠. 이때 x를 나열했을 때도 등차수열, y를 나열했을..