개발 블로그

벌써 종강한 지 두 달이 다 되어 가네요.. 방학을 맞이해서 대학교에서 제일 친한 친구들과 일본도 갔다 오고, 갔다 온 이후 정말 많은 일이 있었는데,,, 쉴 틈 없이 지나간 거 같네요. 우선적으로 방학 때 알고리즘 문제를 유형별로 나누어 많이 풀어보았습니다. 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][..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이 문제는 BFS라고 볼 수 있습니다. 시작 값과 끝 값을 두고 D(num*2 % 10000), S( s-1 > 0 ? 9999 : s-1), L(자리수 왼쪽 한 칸 이동), R(자리 수 오른쪽으로 한 칸 이동) 연산을 하는데, 시작 값에서 끝 값을 만들기 위한 연산의 최솟값을 구하는 문제입니다. 3 1234 3412 1000 1 1 16 테스트케이스를 예시로 들면, 1234에서 34..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 뱀과 사다리에 대한 정보가 주어지고, 사다리는 해당 칸에서 위로 올라갈 수 있지만, 뱀은 아래로 내려가는 구조입니다. 만약 사다리나 뱀을 만나지 않는다면, 주사위를 던져 나올 수 있는 모든 경로를 탐색하면 됩니다(6가지) #include #include using namespace std; int dist[101]; int nex[101];..