개발 블로그

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 일반적인 BFS탐색 문제와 크게 틀에서 벗어나진 않지만, 벽(1)을 한 번 이동할 수 있는 조건에서 큰 차이를 보입니다. 그리고 이 조건으로 인해 조금 더 어려워졌습니다. 저는 입력을 2차원 배열로 받고, 구하고자 하는 최단경로를 3차원으로 만들어줘서 풀었습니다. 왜냐하면 벽을 부순 경우가 최단 경로가 될 수 있고, 부수지 않은 경우가 최단 경로가 될 수 있기 ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS +DFS알고리즘을 활용하면 되지만 조건이 굉장히 까다로운 문제입니다. 벽을 부순 후 벽을 기준으로 이동할 수 있는 영역이 몇 개 인지 탐색하는 문제입니다. 이것을 일일이 탐색한다면 시간 복잡도가 O((MN)^2)으로 매우 오래 걸리게 됩니다. 그래서 이동할 수 있는 영역에 대해서 그룹을 짓고 그룹의 크기가 담겨있는 vector를 만들어 줍니다. 그리고 해당 벽을 기점으..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이 문제를 해결하기 위해 적용한 것은 에라토스테네스의 체, 투 포인터 알고리즘입니다. 에라토스테네스 체는 2의 배수(2는 제외, 소수이므로)부터 특정 수의 배수까지 걸러주는 알고리즘입니다. 출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 ..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이 문제는 c++의 set헤더를 이용하면 쉽게 풀 수 있는 문제였습니다. multiset 헤더는 set헤더와는 다르게 중복된 값을 저장할 수 있기에, 이중 우선순위 큐를 풀기 위해서는 multiset을 이용해야 합니다. 왜냐하면 문제에서 D -1 연산을 했을때 최소값이 중복되더라도 한 번만 제거하기 때문입니다. erase() 함수를 통해 원소를 삭제할 수 있다. (erase함수 안에 인자로 값..

기능 추가한 패키지는 다음과 같습니다. (기존 틀에서 벗어나진 않지만, Spring Security와 도메인 추가, 이미지 처리, 페이징 처리 등 다양한 기능들을 추가하였습니다) 우선 시큐리티 부분부터 차근차근 설명드리겠습니다. SecurityConfig.class @EnableWebSecurity @Configuration @RequiredArgsConstructor public class SecurityConfig { private final TokenProvider tokenProvider; private final CorsFilter corsFilter; private final JwtAuthenticationEntryPoint jwtAuthenticationEntryPoint; private f..

오늘도 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 -..