개발 블로그

오늘도 N과 M 시리즈를 복습 차원에서 다시 풀어보았습니다. 유형마다 조금씩 차이도 있고, 함수 구현하는데 있어 도움이 많이 될 것 같아서 다시 풀어보았습니다. 6 ~ 12번 까지 문제 설명 드리겠습니다. 6번 : N개의 자연수 중에서 M개를 고른 수열, 고른 수열은 오름차순이어야 한다. 7번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다.(사전 순으로 증가하는 순서로 출력) 8번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 9번 : N개의 자연수 중에서 M개를 고른 수열(중복 수열 제거, set 사용..

오늘은 N과 M 시리즈를 다시 풀어보았습니다. 백트래킹(완전탐색)은 BFS, DFS에서도 굉장히 많이 응용되어서 나오기 때문에 잘 알아둬야 할 것 같습니다. 문제마다 조금씩 다른 유형이지만, 조건을 잘 보고 로직을 조금씩 다듬으면 수월하게 풀 수 있을 것 같다고 생각합니다. 1번부터 5번까지 문제 설명 드리겠습니다. (공통) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1 : 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 2: 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열, 고른 수열은 오름차순이어야 한다. 3: 1부터 N까지 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 4: 1부터 N까지 자연수..

벌써 종강한 지 두 달이 다 되어 가네요.. 방학을 맞이해서 대학교에서 제일 친한 친구들과 일본도 갔다 오고, 갔다 온 이후 정말 많은 일이 있었는데,,, 쉴 틈 없이 지나간 거 같네요. 우선적으로 방학 때 알고리즘 문제를 유형별로 나누어 많이 풀어보았습니다. DP, BFS, 브루트 포스, 재귀, 백트래킹, 문자열 등 다양하게 풀어보면서 SW마에스트로 코딩 테스트 준비를 하였습니다. 시험에 대한 기대감이 높지만, 걱정도 많이 됩니다. 최근 일주일은 SW마에스트로 자소서에 거의 몰빵을 했습니다. 저의 간절함을 드러내고, 해왔던 노력, 꿈, 열정 등을 보여주기 위해 밤을 지새워가면서 썼던 것 같습니다. 더불어 같이 학과 친구들에게 첨삭을 받으면서 저의 자소서를 많이 다듬을 수 있었습니다. 저의 자소서를 기반..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 기본적인 BFS문제와 유사한데, 높이가 주어져서 2차원이 아닌 3차원으로 표현해야 합니다. 더불어 이동 방향도 상, 하, 좌, 우에서 앞, 뒤가 추가된 6가지로 표현할 수 있습니다. 이동 방향이 행, 열, 높이 총 3개가 있으므로 원소를 3개 참조해야 합니다. 이러한 경우에 c++에서 제공하는 tuple 헤더를 이용해서 해당 원소를 한 번에 참조할 수 있게 되고 굉장히 편리..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 이 문제는 분할 정복 알고리즘의 대표적인 예시가 되는 문제라고 생각합니다. N*N 크기의 행렬로 표현되는 종이를 9 등분해서 나온 종이가 모두 같은 숫자이면 해당 숫자의 개수를 1 늘려줍니다. 그렇지 않으면 다시 9등분 해줘서 다시 같은 숫자가 나오는지 확인해야 합니다. 테스트케이스를 예시를 들어서 설명드리겠습니다. 9 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -..

https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 이 문제의 로직은 기존 하노이탑과 동일합니다. 그런데 원판의 개수가 100개라서 최악의 경우 O(2^100)이 걸리기 때문에, 이는 기존 int형, long형의 범위를 훨씬 초과하게 됩니다. 기존 하노이탑 로직 예시(그림에서 원판이 n = 5개인 경우) 4(n-1)개의 원판(가장 아래쪽의 있는 원판을 제외한 나머지 원판)을 2번 탑으로 이동시키기 1개의 원판(가장 아래쪽에 있는 원판)을 3번 탑으로..

분할 정복은 문제를 2개 또는 그 이상의 작은 부분 문제로 나눈 다음 푸는 것(분할) DP의 경우는 작은 부분문제가 중복이 되므로 Memorization을 통해 중복을 제거하고, 분할 정복은 문제를 나누었는데, 중복이 되지 않기에 한 번만 풀어주면 가능 푼 다음에 다시 합쳐서 정답을 구하는 경우(정복) 예시 : 퀵 소트, 머지 소트, 큰 수 곱셈.. 대표적인 알고리즘 1. 이분 탐색 (Binary Search) 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘 리스트의 크기를 N이라고 했을 때 크기가 N인 리스트를 계속해서 절반으로 나누기 때문에, O(logN)의 시간 복잡도가 걸리게 됩니다. while(leftx) { right = mid-1; } else { left = mid+1; } } 중..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 이 문제는 0번 스위치를 누를지 말지 결정하고 풀어야 하는 문제입니다. 왜냐하면 모든 스위치를 한 번씩 눌러보는 브루트 포스로는 복잡도 문제로 해결할 수 없습니다. 0번 스위치를 누른다면, 1번 스위치만 신경 쓰면 되고, 1번 스위치가 눌러지면 2번 스위치만 고려하면 되기 때문입니다. 그래서 시간 복잡도 O(N)으로 풀 수 있게 됩니다. #include #include..

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 이 문제는 3*3 행렬을 반대로 (0->1, 1->0) 뒤집어서 주어진 A에서 행렬 B로 만들 수 있는 최소 연산 횟수를 물어보는 문제입니다. 이 문제의 핵심은 (N-2) * (M-2)의 연산을 수행해 보는 것입니다. 왜냐하면 이 연산을 모두 수행했을 때, 주어진 행렬 B와 일치하지 않으면 더 이상 행렬 B를 만들 수 없기 때문입니다. 이러한 연산으로 인해, 어떠한 원소를 두 번 뒤집는 것은 원래대로 돌아오기 ..

https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 가장 기본적인 BFS 문제입니다. 이동 경우의 수가 보기와 같이 6가지 이고, 인접 노드를 방문하면서, 연산 횟수를 하나씩 증가시켜주면 끝나는 문제입니다. 개인적으로 BFS 입문 문제로 괜찮은 문제라고 생각합니다. #include #include #include using namespace std; int mov[6][..