boj
-
백준 1967 트리의 지름Algorithm/BOJ 2021. 1. 21. 15:14
출처: https://www.acmicpc.net/problem/1967 분류: 트리 접근방식 문제의 서두에 트리는 무방향 그래프라고 알려주면서 힌트를 주고 있습니다. root가 있지만 방향성이 없기 때문에 트리를 돌려서 생각해보면 leaf 노드를 root로 한 트리의 형태를 생각해볼 수 있습니다. root를 포함한 끝 노드에서 다른 끝 노드로 가는 경로가 이 트리의 지름이 됩니다 :) 해결방법 dfs를 돌려서 루트에서 가장 먼 노드를 찾고, 그 노드를 루트로 다시 dfs를 돌려서 가장 먼 지름는 방식으로 해결했습니다. 그 노드의 인접 노드들을 배열로 하는 이중 배열을 만들어서 해결했습니다. 트리가 익숙하지 않아서 이 자료구조를 만드는 데 꽤나 시간이 걸렸네요... 이게 최선인지도 모르겠습니다. 😢 im..
-
백준 3190 뱀Algorithm/BOJ 2021. 1. 9. 13:10
출처: https://www.acmicpc.net/problem/3190 분류: 자료구조 접근방식 특별한 알고리즘이나 수학적 개념보다 주어진 상황에 충실히 구현하면 되는 문제였습니다. 2차원 배열 맵을 만들어두고 체크해도 되겠으나(많이들 그런 식으로 푸신 것 같더라구요) 저는 굳이 배열을 따로 만들진 않고 범위만 체크했습니다. 해결방법 뱀을 링크드리스트 형태로 구현해줬고 body set을 정의해서 자기 자신으로 가려고 하는지 확인했습니다. enum, class 등등으로 정의해서 좀 느리고 길게 풀어진 것 같긴 하지만 그래도 나름 swift스럽게(?) 푼 것 같기는 합니다. 사과를 찾았으면 해당 사과를 지워줘야 하는데 이걸 빼먹어서 시간을 좀 잡아먹었네요 ;; 혹시나 저처럼 실수하시는 분들이 없기를 ㅠㅠ ..
-
백준 13460 구슬 탈출 2Algorithm/BOJ 2020. 7. 24. 13:32
출처: www.acmicpc.net/problem/13460 분류: 완전 탐색 접근방식 상하좌우로 회전시킬 수 있는 보드판 위에 빨강, 파랑 구슬, 빠져나갈 구멍이 있을 때 움직여서 빨간 구슬만 구멍에 넣어야 할 때 최소 횟수를 찾는 문제입니다. 단, 횟수가 10번을 초과하면 안됩니다. 판의 크기가 3 ~ 10 까지로 매우 작고 10번이라는 제한이 있기 때문에 모든 경우를 다 탐색해서 말그대로 완전 탐색으로 해결할 수 있습니다. 개인적으로 구현이 꽤나 까다로웠던 문제였습니다. 상하좌우로 다 해본다는 게 말은 쉽지만 생각보다 까다로웠습니다. 두 구슬은 겹칠 수 없기 때문에 다른 구슬이 앞에 있다면 그 구슬 뒤까지 움직여야 하고 말이죠... 구현 아이디어는 다음과 같습니다. 빨간 구슬과 파란 구슬은 계속 굴..
-
백준 1700 멀티탭 스케줄링Algorithm/BOJ 2020. 6. 17. 14:32
출처: www.acmicpc.net/problem/1700 분류: 그리디 접근방식 플러그의 개수와 사용해야 할 기기들의 순서가 주어질 때 플러그를 최소한으로 뽑을 수 있는 횟수를 찾는 문제입니다. 저는 처음에 단순히 앞으로 사용될 횟수가 가장 적은 플러그를 빼면 되지 않을까 생각했지만, 그렇게 하면 다음과 같은 경우에 최적의 경우가 되지 못합니다. 2 1 3 1 3 1 3 2222.... 이런 경우라면 2 1 3 중에서 사용 횟수는 1과 3이 가장 적지만 2는 나중에 나오기 때문에 당장 2를 뽑아서 사용해야 합니다. 뽑혀있는 플러그 중에서 가장 나중에 사용될 아이를 찾아야 합니다. 플러그를 뽑아야 할 상황이 오면 현재 꽂아야 할 기기 다음부터 확인해서 가장 나중에 사용될 플러그의 인덱스를 찾습니다. 가장..
-
BOJ 2352 반도체 설계Algorithm/BOJ 2020. 6. 12. 16:10
출처: www.acmicpc.net/problem/2352 분류: Greedy, LIS 접근방식 포트에 선이 서로 꼬이지 않게 연결하려고 할 때 가장 많이 연결할 수 있는 개수를 찾는 문제입니다. 문제의 예처럼 이렇게 연결되어 있을 때, 왼쪽을 A포트 오른쪽을 B포트라고 생각해보겠습니다. A[1] -- B[4] 포트가 연결되어 있다면 왼쪽에서 A[1]을 제외한 나머지 포트들은 모두 1보다 크기 때문에 B에서 4보다 작은 포트들에는 연결할 수가 없습니다. 다시말해 A[i] 포트 --> B[j] 포트로 연결하려고 할 때 현재까지 B에 연결되어있는 포트 중 가장 큰 녀석보다 작은 경우에는 연결할 수가 없게 됩니다. 즉, 이 경우엔 B에 연결해야 하는 포트들 중에서 연속적으로 증가하는 수의 최대 길이가 몇이야?..
-
백준 1049 기타줄Algorithm/BOJ 2020. 6. 8. 16:18
출처: www.acmicpc.net/problem/1049 분류: 그리디 접근방식 패키지와 낱개의 가격이 주어지고 고장난 기타줄 이상을 살 수 있는 최소가격을 구하는 문제입니다. 최소 가격을 구하는 문제이므로 패키지와 낱개 각각의 최소값에만 신경쓰면 됩니다. 동전나누기와 비슷하죠? 낱개 6개 가격이 패키지 가격보다 싸지만 않다면 패키지만큼 다 나눠주고 나머지랑 패키지랑 비교해서 풀면 됩니다. 해결방법 let n = readLine()!.split(separator: " ").map{Int($0)!} var minPackage = Int.max var minPiece = Int.max for _ in 0.. minPiece * 6 { print(n[0] * minPiece) } else { var tota..
-
백준 1946 신입 사원Algorithm/BOJ 2020. 6. 8. 15:54
출처: www.acmicpc.net/problem/1946 분류: 그리디 접근방식 다른 사람보다 서류와 면접 점수가 모두 낮은 경우엔 탈락, 합격한 사람의 수를 구하는 문제입니다. 서류 1등은 무조건 합격입니다. 1등보다 면접 등수마저 낮다면 그 사람은 탈락이 되겠죠. 이때 1등의 면접 등수가 서류 2등 ~ 나머지 사람의 합격을 가르는 기준점이 됩니다. 1등의 면접 점수보다 낮은 사람을 모두 거르고 나면 남아있는 사람 중 서류 1등이 다시 합격의 기준점이 되죠. 이를 반복해주면 합격자의 수를 구할 수 있습니다. 하지만 이렇게 해주면 시간 초과가 납니다. (Swift 기준) 매번 나머지를 다시 도는건 너무 비효율적인 방법이죠. 보다 효율적으로 해결할 수 있는 방법이 있습니다. 서류 1등의 면접 등수를 기준..
-
백준 1120 문자열Algorithm/BOJ 2020. 6. 8. 14:58
출처: www.acmicpc.net/problem/1120 분류: Greedy 접근방식 앞뒤로 아무 문자나 붙여서 길이를 같이 만들 때 차이가 가장 적은 경우를 찾는 문제입니다. 앞뒤로 아무 문자나 붙일 수 있으므로 현재 문자열과 비교할 문자열만 가지고 비교하면 나머지는 길이를 맞춰버릴 수 있습니다. 예제 케이스처럼 adaabc aababbc 를 보면, 0번 인덱스부터 adaabc와 adaabc의 길이만큼인 aababb 와 비교해보면 다른 개수는 3개입니다. 나머지는 adaabc 뒤에 c를 붙여버리면 길이를 똑같이 만들 수 있겠죠 1번 인덱스부터 adaabc와 adaabc의 길이만큼인 ababbc 와 비교해보면 다른 개수는 2개입니다. 마찬가지로 앞에 a를 붙여서 길이를 똑같이 만들 수 있겠죠 해결방법 ..