https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 N x N 모양의 지역에 디저트 카페가 모여있다. 칸의 숫자는 디저트의 종류를 뜻하며 카페들 사이에는 대각선 방향으로만 이동 가능 대각선으로 카페 투어를 떠난 후 다시 처음 카페로 돌아오면 된다. 이때, 한 번 먹은 종류의 디저트 카페는 갈 수 없고, 왔던 길도 돌아갈 수 없다. # 접근 방법 #1 dfs dfs를 이용하여 사각형을 그려주며 탐색할 수 있다. 회전 방향을 정하고, 카페와 디..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 8*8의 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 조금 더 일반화시켜 N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수를 구하시오. # 접근 방법 및 Solution "모든 경우의 수"인 브루트 포스로 해결할 수 있지만 이후의 사건이 이전의 사건에 종속적이므..

다익스트라(dijkstra) 알고리즘은 일상생활에서, 지하철, 내비게이션 등 여러 분야에서 사용되는 알고리즘이다. 활용 예시를 보면 알 수 있듯이 최단 경로 알고리즘인 다익스트라 알고리즘을 알아보자. # 다익스트라 알고리즘 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 자료 구조로는 그래프(graph) 사용 노드와 가중치를 가진 간선을 이용하여 실제 거리를 표시한다. 초기에 우선순위 큐를 사용하지 않은 다익스트라 알고리즘 O(V^2)의 시간 복잡도 우선순위 큐로 인한 개선으로 O(E log V) - V, E = 노드와 간선의 수 삽입 삭제, 최소 값 추출 - O(logV) 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용 => 다이나믹 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 위 그림처럼 도로 곳곳이 파손되어 있다. 복구하기 위한 공병대는 상하좌우로 이동 가능하며, S(0,0)에서 G(N-1,N-1)까지 복구 작업을 하는데 가장 빠른 시간 내에 수행한다. 깊이 1에 시간 1이 걸리며 한 칸씩 움직일 수 있다. # 접근 방법 최단 경로 알고리즘이다. 다익스트라 알고리즘을 사용하며, heapq 대신 BFS를 함께 사용해주어도 될 것 같다. 내가 갈 좌표에 대해, 좌..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net # 조건 add x : S에 x를 추가한다. S에 이미 x가 있는 경우 연산 무시 remove x : S에서 x를 제거한다. S에 x가 없는 경우에는 연산 무시 check x : S에 x가 있으면 1을, 없으면 0을 출력 toggle x : S에 x가 있으면 x를 제거, 없으면 x를 추가 all : S를 {1,2,3,...,20} 으로 바꾼다. empty : S를 공집합으로 바꾼다. # 접근 방법 & Solution 조건의 함수들을..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net # 조건 버튼은 0~9까지의 숫자와 +, - 버튼 + 버튼은 1채널 위로, -는 1채널 아래로, 채널은 무한대이며 0아래로는 안 내려간다. 이동하려고 하는 채널 N까지 최소 눌러야하는 버튼 수를 구하여라. # 접근 방법 눌릴 수 있는 버튼에 한해서 제일 가까운 채널까지 이동한다. 이 때 누르는 버튼 수는 이동채널의 길이와 같다. 그 이후에는 +와 -버튼을 이용할 수 밖에 없으므로 ..

지금까지 알고리즘을 풀면서 재귀와 반복문은 많이 사용했을 것이다. 똑같은 상황에서 사용가능 한 이 두가지 방법을 언제 사용하는 것이 좋은지 알아보자. 목차 1. 재귀? 2. 반복문 3. 비교 1. 재귀(Recursion) 우선 재귀를 사용하기 위해서 수학적 귀납법 증명에 대해 간단히 알아보자. n이 0일 때 문제를 풀 수 있고 n-1에서 문제를 풀 수 있으면 n에서도 문제를 풀 수 있다 위의 2가지가 사실이면 모든 가능한 n에 대해 문제를 풀 수 있다는 것이 사실!! 이렇게 프로그램을 돌리면 순차적인 코드에서와 마찬가지로 필요한 계산이 완전히 동일하지만 단순히 표현하는 방법이 달라지는 것 재귀 위의 수학적 귀납법의 풀이 과정을 이용한 것이 재귀이다. 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net # 조건 피보나치 함수는 f(n ) = f(n-1) + f(n-1)의 성질을 가진다. 정수 n이 주어졌을 때 0과 1이 몇 번 출력되는지 구하여라. # 접근 방법 문제에 주어진대로 재귀를 이용하여 구해봤지만 역시나 시간초과. 메모이제이션을 이용해봐도 시간초과가 나게 되었다. 0과 1이 출력되는 횟수가 수가 증가함에 따라 각각 피보나치 함수와 동일하게 출력됨을 발견 따라서 dp table을 따로 만들어 준 후 입력 n에 대해 횟수를 출력시켜준다. # 시간초과 코드 def fibo(n): glob..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net # 조건 1 x 1 x 1 크기의 블록들로 이루어진 3차원 세계 땅을 고르게 해야 집을 지을 수 있다. 세로 N, 가로 M 크기의 집터 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다. 인벤토리에서 블록하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다. 1번 작업은 2초, 2번 작업은 1초 인벤토리에 B개의 블록 들어있고 256의 높이 초과 불가 걸리는 최..