본문 바로가기
반응형

전체 글1307

[BOJ] 백준 1107 리모컨 출처: https://www.acmicpc.net/problem/1107 Input 5457 3 6 7 8 Output 6 ① 숫자 버튼 없이 +,-로만 조작하는 경우 abs(N - 100); ② 숫자 버튼으로 이동 후 +,-로 조작하는 경우 모든 채널에 대해서 고장 버튼을 고려해서 이동가능한지 확인 후, 해당 채널에서 +,-를 몇 번 눌러야 하는지 확인합니다. Q. N의 최대값은 500,000인데 0 ~ 1000,000채널까지 탐색하는 이유? A. 고장난 버튼에 따라서 50만 위에서 -버튼을 누르는게 좋을 수도 있기 때문에 여유롭게 크기를 잡음 Q. 수학적인 접근 방법이 있을까? N 채널의 차이를 최소로해서 Greedy 방식으로 접근할 수 있지만, Input 1555 8 0 1 3 4 5 6 7 9 O.. 2021. 2. 26.
[BOJ] 백준 3048 개미 출처: https://www.acmicpc.net/problem/3048 Input 3 3 ABC DEF 2 Output CDBEAF 개미 그룹이 서로 →← 방향으로 맞닥뜨렸을 때 swap이 일어나는 것을 구현 ▶ 오른쪽으로 이동중인 개미가 왼쪽으로 이동중인 개미와 마주쳤을 때 서로의 위치를 바꾼다. 개미의 정보를 구조체로 처리 ▶ dir : 개미의 방향, ID: 개미 이름 #include using namespace std; #define RIGHT 0 // 오른쪽으로 이동 #define LEFT 1 // 왼쪽으로 이동 struct ant { int dir; char ID; }; // 개미는 총 알파벳 수만큼 존재 struct ant temp, ants[27]; void swap(int A, int B.. 2021. 2. 26.
[BOJ] 백준 5566 주사위 게임 출처: https://www.acmicpc.net/problem/5566 Input 10 5 0 0 5 6 -3 8 1 8 -4 0 1 3 5 1 5 Output 5 ① 주사위로 이동한 위치 ② 칸에 적힌 지시사항으로 이동한 위치 → 움직인 위치가 도착점(=N)을 지나쳤는지 확인 #include using namespace std; int N, M, board[1001], dice[1001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for(int i = 1; i > board[i]; for(int i = 1; i > dice[i]; int answer = 0, cur = 1; w.. 2021. 2. 26.
[BOJ] 백준 10990 별 찍기 - 15 출처: https://www.acmicpc.net/problem/10990 Input 4 Output * * * * * * * 입력 값 n이 증가함에 따라 별들의 간격과 벌어지는 규칙을 쉽게 확인할 수 있습니다. ▶ 첫번째 줄 n - 1 만큼의 공백과 『*』 ▶ 첫번째 줄을 제외하고는 아래와 같은 규칙을 가집니다. ① n - i 만큼의 공백 문자 출력 후 『*』 ② (i -1) * 2 - 1 만큼의 공백 문자 출력 후 『*』 출력 후 줄넘김 ▶ [문제] BOJ 별 찍기 시리즈 [문제] BOJ 별 찍기 시리즈 [BOJ] 2438 별 찍기 - 1 [BOJ] 2439 별 찍기 - 2 [BOJ] 2440 별 찍기 - 3 [BOJ] 2441 별 찍기 - 4 [BOJ] 2442 별 찍기 - 5 [BOJ] 2443 .. 2021. 2. 26.
[BOJ] 백준 13015 별 찍기 - 23 출처: https://www.acmicpc.net/problem/13015 Input 2 Output ** ** *** ** ** 별도 메모리를 잡지 않고 2n - 1 줄에 거쳐 출력. 3가지 영역으로 구분합니다. 첫번째 / 중간 / 마지막 (첫번째와 마지막은 동일한 출력) ① 초기 a, b, c, d의 값은 아래와 같습니다. ▶ a = 0 , b = n - 1 ▶ c = 3n - 3, d = 4n - 4 n번째 줄까지는 a와 b는 증가 / c와 d는 감소 n번째 줄 이후로는 a와 b는 감소 / c와 d는 증가 ② 별을 찍는 형태는 아래와 같습니다. [첫번째와 마지막 줄] ▶ a 별 b 공백 c 별 d [중간] ▶ 공백 a 공백 b 공백 c 공백 d * n번째 줄에 해당하는 정가운데에서는 b와 c가 같은.. 2021. 2. 26.
[SWEA] 3947 가장 짧은 길 전부 청소하기 출처: [SWEA] SW 문제해결 심화 - 증명의 중요성 Input 2 5 5 1 2 1 4 3 2 1 3 1 2 4 2 5 4 3 4 4 1 2 1000 2 3 100 3 4 500 1 4 600 Output #1 7 #2 1700 [1] - [2], [2] - [4], [4] - [5], [1] - [3] 가중치 합: 1 + 2 + 3 + 1 = 7 위의 예제로만 보면 최소 신장 트리를 구성하는 Prim's Algorithm을 적용하면 되지만, [Test Case #2] 가중치 합: 1000 + 600 + 100 = 1700 입니다. [정점 [1] 기준 Prim's Algorithm 결과] 이는 최소신장트리 ≠ 최단 경로이기 때문입니다. 최소신장트리에서는 정점[1] → [2]까지 600 + 500 +.. 2021. 2. 25.
[BOJ] 백준 1916 최소비용 구하기 출처: https://www.acmicpc.net/problem/1916 Input 5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5 Output 4 출발점 X부터 다른 정점 Y까지의 최소거리 비용을 구하기 위해 다익스트라(Dijkstra)을 이용 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. ( zoosso.tistory.com 정점과 간선의 개수가 비교적 크지 않으므로 선형적으로 구현 * 문제에서 Input Data 중 아래와 같이 서로 다른 .. 2021. 2. 25.
[BOJ] 백준 5052 전화번호 목록 출처: https://www.acmicpc.net/problem/5052 Input 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 Output NO YES 접두사를 이용해서 전화번호를 누르기 전에 다른 전화로 걸리는지 확인. (일상에서의 [통화 연결] 버튼이 따로 존재하지 않는다고 보면 됩니다.) ▶ Trie 이용 : Trie 자료구조에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단 ※ 숫자로 된 문자열이므로 10진 트리로 이해할 수도 있습니다. #include #include using namespace std; int charToIndex(char c){ return c - '0'; } struct Trie { b.. 2021. 2. 25.
[BOJ] 백준 1753 최단거리 출처: https://www.acmicpc.net/problem/1753 Input 5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6 Output 0 2 3 7 INF 음의 가중치가 없기 때문에 다익스트라(Dijkstra) 이용. 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. ( zoosso.tistory.com ▶ 그래프 구현 (인접 리스트 / 인접 행렬) 그래프 표현 (인접 리스트 / 인접 행렬) 정점 u - v 간 간선 여부 확인 - 인접 리스트는 adList[u]의 .. 2021. 2. 25.
[BOJ] 백준 1719 택배 출처: https://www.acmicpc.net/problem/1719 Input 6 10 1 2 2 1 3 1 2 4 5 2 5 3 2 6 7 3 4 4 3 5 6 3 6 7 4 6 4 5 6 2 Output - 2 3 3 2 2 1 - 1 4 5 5 1 1 - 4 5 6 3 2 3 - 6 6 2 2 3 6 - 6 5 5 3 4 5 - 다익스트라(Dijkstra)을 이용해 최단 경로를 구한 후, 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. ( zoosso.tistory.com 경로 추적으로 통.. 2021. 2. 25.
반응형

티스토리툴바