programing/Algorithm
-
[SWEA] 1868 - 파핑파핑 지뢰찾기programing/Algorithm 2019. 11. 1. 19:05
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 삼성 SW Expert Academy의 1868번 문제인 파핑파핑 지뢰찾기에 대해 알아보도록 하겠습니다. 접근 방법 해당 문제는 실제 지뢰찾기와 유사한 로직을 가지고 있습니다. 바로 0인 칸을 누르면 연쇄작용이 일어난다는 점입니다. 그 외에 특이사항으로는 지뢰가 어디 있는지 미리 알고 있다는 것과, 지뢰를 제외한 나머지 모든 칸을 오픈하기 위해 필요한 최소 클릭 횟수를 구하는 정도겠네요. 제가 생각하는 키 포인트는 다음과 같습니다. 값이 0인 칸들의 목록 : 최소 횟수를 구하기 위해, 보드를 스캔 후 값이 0인 칸들의 좌표 목록을 만듭니다. 해당 좌표에 해당하는 칸들을 모두 클릭(오픈)하면, 값이 1 이상인 칸..
-
[SWEA] 2806 - N-Queenprograming/Algorithm 2019. 10. 29. 19:02
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 삼성 SW Expert Academy의 2806번 문제인 N-Queen에 대해 알아보도록 하겠습니다. 회의 시간 : 2019.11.03 13:00 ~ 15:00 회의 장소 : 강남역 SG스터디룸 접근 방법 N-Queen 문제는 백 트래킹의 대표적인 문제입니다. 알고리즘 수업때 한번쯤 배우고 지나갑니다. 제가 생각하는 키 포인트는 다음과 같습니다. 백 트래킹 : 퀸을 특정 위치에 놓아 보고, 조건에 맞지 않다면 퀸을 치우고 다른 자리에 놓아 봅니다. 퀸을 놓을 위치 : 문제에서 퀸들은 서로를 공격할 수 없어야 합니다. 즉, 특정 위치가 안전한 자리인지 확인해야 합니다. 위 두 키 포인트를 위해, column라는 ..
-
[BJ] 17471 - 게리맨더링programing/Algorithm 2019. 10. 20. 00:15
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 오늘은 백준 17471번 문제 게리멘더링에 대해 알아보도록 하겠습니다. 회의 시간 : 2019.10.21 (토) 17:00 ~ 19:00 회의 장소 : 패스트파이브 서울숲점 2D 접근 방법 딱 봐도 두가지 개념이 혼합된 문제입니다. 연결 요소(connected component)와 조합(combination)입니다. 큰 요점은 모든 노드를 빠짐없이 두개의 그룹으로 분할하며, 동시에 두 그룹은 연결 요소여야 합니다. (물론 다른 방법으로도 풀 수 있을 거에요. 아마도..) 이 외에도 비트마스크, 서로소 집합 등등 여러가지 개념들을 이용한 분들도 계시더라구요. 어찌됬건, 제가 생각하는 키 포인트들은 다음과 같습니다. 연결 요소 : ..
-
[Algorithm] 조합 (Combination)programing/Algorithm 2019. 10. 19. 23:30
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 오늘은 조합에 대해 알아보도록 하겠습니다. 조합 (Combination) 조합이란, 요소의 개수가 n개인 집합에서 r개를 순서 없이 뽑는 것을 말합니다. 보통 조합은 $_{n}C_{r}$으로 표현하며, 다음과 같이 정의됩니다. $$_{n}C_{r} = \frac{n!}{r!(n-r)!}$$ 또한, 조합은 또다른 공식이 있는데, 다음과 같습니다. $$_{n}C_{r} = _{n-1}C_{r-1} + _{n-1}C_{r}$$ 이해가 잘 안되시죠? 간단히 예를 들어보겠습니다. [1, 2, 3]에서 2개를 뽑는다고 가정해봅시다. 그러면 다음과 같이 두 가지 경우로 나눌 수 있습니다. (1, x) : 첫번째 요소를 1로 결정한 경우. 즉..
-
[BJ] 13460 - 구슬 탈출 2programing/Algorithm 2019. 10. 12. 22:12
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 백준 13460번 문제인 구슬 탈출 2에 대해 알아보도록 하겠습니다. 회의 날자 : 2019.10.13 회의 장소 : 패스트파이브 서울숲점 2A 접근 방법 구슬을 최대한 적은 횟수로 기울여서 탈출시켜야 합니다. 딱 봐도 감이 오시나요? BFS를 사용하는 문제랍니다. 제가 생각한 이 문제의 키 포인트들입니다. 트리 구조 : 판을 상하좌우 4방향으로 기울일 수 있습니다. 다음 상태는 이전의 상태와 수행한 동작에 영향을 받으므로, 각 상태를 트리의 노드로 생각할 수 있습니다. BFS : 트리 구조에서, 최단 횟수를 구하는 경우에 사용합니다. BFS는 해를 찾았을 경우 해당 해가 최단거리임을 보장하지만, DFS는 최단..
-
[BJ] 2309 - 일곱 난쟁이programing/Algorithm 2019. 10. 5. 20:38
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 백준 2309번 문제인, 일곱 난쟁이에 대해 알아보겠습니다. 접근 방법 사실 문제를 처음 보고 풀 때는, DFS를 생각했습니다. 순서에 상관 없이 합이 100이 되도록 난쟁이의 키들을 고르기만 하면 되니까요. (다 풀고 더 좋은 코드를 찾다보니 이게 바로 조합이라는 것을 알게 되었습니다.) 이 문제에서 중요하다고 생각하는 키 포인트는 다음과 같습니다. 순서 상관 없음 합이 100이 되어야 함 난쟁이의 숫자는 7명 순서가 상관 없다는 것에서 부터 순열이 아닌 조합임을 알 수 있고, 트리에서 여러가지 탐색 경로가 같은 경우로 취급된다는 것을 의미합니다. 합이 100이 되는 것은 재귀 함수의 중단 조건중 하나가 될 ..
-
[BJ] 11724 - 연결 요소의 개수programing/Algorithm 2019. 9. 28. 23:38
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 오늘은 백준 11724번 연결 요소의 개수에 대해 포스팅하겠습니다. 연결 요소(connected component) In graph theory, a component, sometimes called a connected component, of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. 연결 요소란, 무향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 ..
-
[Algoritm] logn, nlogn은 어떻게 도출할까programing/Algorithm 2019. 9. 13. 18:54
시간복잡도를 보다보면 $O(n\log n)$의 시간복잡도를 가지는 알고리즘들이 많습니다. 이 $n\log n$이란 값은 어떻게 도출되는걸까 생각을 해봤습니다. 간단하게 이진탐색을 예로 들어봅시다. 주어진 데이터는 $n$입니다. 이진탐색은 주어진 데이터를 반씩 쪼개서 둘 중의 한 부분에서 원하는 값을 찾습니다. 최악의 경우, 남은 데이터의 개수가 1이 될 때 까지 반씩 쪼개는 작업을 반복해야 합니다. 그렇다면 다음과 같은 수열을 유추할 수 있습니다. $$n : 1, n/2 : 2, n/4 : 3, ..., 1 : x$$ 이때, 연산의 횟수를 $x$라고 가정했을 때, $n$이 1일 경우 $x$는 무슨 값일까요? 1에서 2를 $x$번 곱해야 $n$이 되므로, $n = 1 \times 2^{x}$라는 방성식을 ..