algorithm
-
백준 12100 2408(easy)Algorithm/BOJ 2021. 3. 8. 15:03
출처: www.acmicpc.net/problem/12100 분류: 시뮬레이션 접근방식 바킹독님의 유튜브 강의를 참고했습니다. 최고 🥰 2048.. 하는 건 좋아했는데 막상 만들라고 하니 꽤 어려웠습니다. 하지만 항상 지나고 생각해보면 그리 어렵지 않습니다 💪 한 행만 잘 합칠 수 있다면 이걸 반복하고, 회전시켜서 간단하게 해결했습니다. 한 행 기울이기 먼저 한 행을 왼쪽으로 기울여서 합치는 걸 생각해보겠습니다. 저는 합쳐진 새로운 행을 만들어 나간다고 생각을 했는데요, 왼쪽으로 기울일거니까 합칠 배열의 인덱스를 0으로 두고 기존의 행을 돌면서 새로운 배열을 만들어 나갔습니다. 새로 만들어질 배열을 mixed, mixed의 현재 인덱스를 movingPoint 라고 해볼게요. mixed 를 기존 행의 크기..
-
백준 18808 스티커 붙이기Algorithm/BOJ 2021. 3. 7. 18:48
출처: www.acmicpc.net/problem/18808 분류: 시뮬레이션 접근방식 주어진 요구사항대로 잘 구현하면 되는 문제였습니다! 각 부분을 함수로 잘 쪼개면 어렵지 않게 해결할 수 있을 것 같네요 :) 저는 isPaste, paste, rotate 등을 함수로 분리해서 해결했습니다. rotate 하는 부분이 좀 헷갈렸는데, 기억해두면 나중에도 유용하게 사용할 수 있을 것 같아요! 90도 회전 func rotate(_ sticker: [[Int]]) -> [[Int]] { let rowSize = sticker.count let colSize = sticker[0].count var rotated = [[Int]](repeating: [Int](repeating: 0, count: rowSize..
-
백준 2143 두 배열의 합Algorithm/BOJ 2021. 3. 5. 13:44
출처: www.acmicpc.net/problem/2143 분류: 이분 탐색, 투 포인터 접근방식 합이 0인 네 정수 문제와 비슷했던 문제였습니다. 주어진 각 배열에서 나올 수 있는 부분합을 모두 구해준 뒤 정렬해서 투 포인터로 해결했습니다. 마찬가지로 T인 케이스를 찾았을 때 중복인 수의 개수를 세서 쌍을 찾아줘야 합니다 :) 해결방법 let t = Int(readLine()!)! let n = Int(readLine()!)! let a = readLine()!.split(separator: " ").map { Int(String($0))! } let m = Int(readLine()!)! let b = readLine()!.split(separator: " ").map { Int(String($0))..
-
백준 1939 중량제한Algorithm/BOJ 2021. 3. 4. 17:06
출처: www.acmicpc.net/problem/1939 분류: 이분 탐색 접근방식 하 이번 문제도 너무 어려웠습니다... 설명이 애매해서 이해도 어려웠고 메모리제한............ ㅂㄷㅂㄷ 먼저 문제의 마지막에 " 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. " 라고 되어있어서 마지막에 주어진 두 섬으로 한 번에 가는 경우를 체크하는건가? 그럼 중간에 경로들은 왜 주어진거지? 문제가 좀 이상한데? 라고 생각했었습니다. 결국 여기서 말하는 한 번의 이동이란 처음 섬에서 특정 중량으로 출발시킨 짐이 목표 섬까지 도착하는 경로를 의미합니다. 중량을 기준으로 이분 탐색을 해서 각 중량으로 이동이 가능한지 체크해서 해결했습니다. var mostWeight = 0..
-
백준 7453 합이 0인 네 정수Algorithm/BOJ 2021. 3. 4. 14:53
출처: www.acmicpc.net/problem/7453 분류: 투 포인터, 이분 탐색 접근방식 4개의 배열이 주어지고 각 원소의 합이 0이되는 쌍이 몇 개인지 찾는 문제입니다. 이 문제의 첫 번째 아이디어는 4개의 배열을 각각 생각하려고 하면 힘드니 2개씩 묶어서 합쳐주는 것입니다. a b 의 합이 될 수 있는 모든 경우를 담은 배열 ab, c d 의 합이 될 수 있는 모든 경우를 담은 배열 cd 를 만들고 둘 모두 오름차순으로 정렬해줍니다. 다음으로 ab는 작은 수부터, cd는 큰 수부터 포인터를 움직여 0이 되는 경우를 찾는 것입니다. ab, cd 원소의 합이 0보다 작으면 low를 증가시키고 0보다 크면 high를 줄여줍니다. sum이 0일 때 주의해야할 건 중복을 찾아서 쌍을 계산해줘야 합니다..
-
백준 2110 공유기 설치Algorithm/BOJ 2021. 3. 3. 20:52
출처: www.acmicpc.net/problem/2110 분류: 이분 탐색 접근방식 이분 탐색 문제인 걸 알고 접근했는데도 접근이 어려웠던 문제였습니다. ㅠㅠ 이녀석 쉬워지질 않네요... 공유기들의 위치가 주어지기 때문에 이걸 가지고 어떻게 이분탐색을 해야하나 싶지만, 저희는 공유기 사이의 거리가 가장 큰 경우를 찾아야 합니다. 따라서 공유기 사이의 거리를 가지고 이분 탐색을 돌려야 합니다. 따라서 저희는 최소 설치 거리를 low 최대 설치 거리를 high 정해서 이분탐색을 해야합니다. 다음에는 해당 거리를 최소 간격으로 해서 공유기를 설치할 수 있는지 없는지만 체크해주면 됩니다. 이건 일단 나중에 생각해보죠 :( 자 그럼 공유기 사이의 거리가 가장 짧은 경우는 어떤 경우일까요? 바로 옆집에 공유기를 ..
-
백준 15810 풍선 공장Algorithm/BOJ 2021. 3. 3. 00:17
출처: www.acmicpc.net/problem/15810 분류: 이분탐색 접근방식 스태프 한 명이 만들 수 있는 풍선의 개수는 시간 / 걸리는 시간 으로 구해줄 수가 있고 특정 시간에 만들어진 풍선의 개수는 해당 시간에 각 스태프가 만들 수 있는 풍선의 개수를 모두 더해 구할 수 있습니다. 이제 최대 걸리는 시간을 특정할 수 있다면 각 시간에 원하는 풍선 개수를 넘거나 같은 시간을 찾아 이분 탐색으로 반씩 잘라가며 찾을 수 있습니다. 처음으로 풍선의 개수를 넘거나 같은 시간을 찾아야 하기 때문에 이분탐색 lower bounded 로 풀어줬습니다. 마지막으로 최대 걸리는 시간(High)을 정해줘야 합니다. 처음에는 staff의 최대 범위가 1000000이여서 적당히 원하는 풍선의 개수 * 1000000..
-
Programmers Lv2) [2021 카카오블라인드] 메뉴 리뉴얼Algorithm/Programmers 2021. 2. 27. 14:04
출처: programmers.co.kr/learn/courses/30/lessons/72411 분류: 조합 접근방식 카카오 블라인드 2번 문제였습니다! 주어진 코스의 개수에 해당하는 조합을 모두 찾고 그 중에서 가장 많은 사람이 먹었던 메뉴들을 골라주면 됩니다. 여러 개라면 모두 넣어줍니다. 주어진 입력 범위가 그리 크지 않기 때문에 ( 20(orders) x 10(각 order의 최대 길이 ) x 10(course) x 10(각 course의 최대 길이) = 20000 정도?) 그냥 다 돌면서 조합을 찾아주고 필터해주면 됩니다. 조합을 찾는 방식은 어렵지않게 찾아볼 수 있습니다 :) 저는 각 코스 문자열의 인덱스를 돌면서 해당 인덱스를 추가해서 재귀, 추가하지 않고 재귀를 돌려서 만들었습니다. func..