iyOmSd/Title: Algorithm풀이 28

[Swift Algorithm] 64064 불량 사용자 (2019 카카오 인턴십)

programmers.co.kr/learn/courses/30/lessons/64064코딩테스트 연습 - 불량 사용자개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 풀이방법먼저 불량사용자에 해당하는 유저아이디를 이차원배열의 형태로 모두 저장했어요["frodo", "fradi", "crodo", "abc123", "frodoc"], ["fr*d*", "abc1**"]주어진 예시가 위의 형태라면[[frodo, fradi], [abc123]]이렇게 저장되어있겟죠여기서 저는 문자열로 저장하지않고 간단하게 비교하기위해 인덱스를 사용했어요result ..

[Swift Algorithm] 투 포인터 알고리즘

투 포인트 알고리즘은 구간의 합같이 구간을 비교할 때 효율적으로 사용할 수 있는 알고리즘이에요 보통 for문 중첩을 통해서 O(N^2)시간초과로 인해서 사용하구요 이 알고리즘의 시간복잡도는 O(N)으로 한번의 순회에 조건을 찾을 수 있어요 구간을 비교하면서 원하는 조건에 달성할때까지 먼저 end를 움직인 다음 start를 하나씩 이동하면서 구간을 좁혀가며 조건을 확인해요 조건에 해당하지않게되면 end가 배열의 끝까지 이동했는지 확인하고 끝까지 가지않았다면 end를 하나씩 이동하며 다시 start와 비교하는 과정을 거쳐요 . . . . 예를 들어서 sum이 10이상인 구간을 찾는데 그 중에서 제일 빠른 구간을 찾는다고 할게요 초기상태의 배열은 처음과끝이 같고 현재합은 1이죠 다음으로는 end를 이동시키면서..

[Swift Algorithm] 64062 징검다리 (2019카카오 겨울인턴십)

programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 풀이방법 범위가 2억이기때문에... 그냥풀면 분명이 시간초과가 걸릴거라고 생각...햇고.. 1명씩 건너도록 단순하게 푼경우.. 역시나 시간초과에 걸린... private func solutionP64062(_ stones:[Int], _ k:Int) -> Int { var stones = stones var isJump = true var result = 0 while true { var zeroCount = 0 for stone in stones { if stone = k { isJump..

[Swift Algorithm] 42627 디스크 컨트롤러 (프로그래머스)

programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 주어진 요청에따라 응답하는데 걸리는 최소평균시간을 구하는 문제에요 문제를 보면 아래처럼 요청이 들어와요 이러한 요청을 처리하는 다양한 방법이있죠 왼쪽처럼 처리하면 3 + 7 + 17 = 27ms 오른쪽처럼 처리하면 3 + 11 + 16 = 30ms 왼쪽처럼 하는 방법이 최선의 선택이겟네요! 풀이방법 우선순위 큐를 사용해서 해결 할 수 있는 문제에요 우선순위 큐는 힙자료구..

[Swift Algorithm] 72413 합승 택시 요금 (2021 카카오 블라인드)

programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 시작지점으로부터 A, B까지 가는 택시요금의 최소합을 구하는 문제구요 A,B가 합승해서간다면 요금..

[Swift Algorithm] 42747 H-Index (프로그래머스)

programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 풀이방법 문제는 짧지만 개념이 좀 어려운 문제에요 발표한 논문 n편중 h번이상 인용된 논문이 h편이상이고 나머지논문이 h번이하 인용되면 h의 최댓값이 답이다... 머라는거야... 헷갈리네요 ㅎㅎ [3, 0, 6, 1, 5] 배열이있다면 우선 보기좋게 정렬해볼게요 [6, 5, 3, 1 ,0] 이 될거고 index와 인용된 논문을 비교해줄거에요 h..

[Swift Algorithm]12978 배달 (서머 윈터 코딩)

programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 풀이방법 그래프문제네요 머리로는 생각이 났지만 풀수가 없어서 개념을 다시 참고했구요 2021/03/06 - [iyOmSd/Title: Algorithm풀이] - [Swift Algorithm] 플로이드 와샬 풀면서 이 개념을 쓰면 편하겠다라는 생각은 들었지만.. 더 노력해야겠어요 아무튼 위의 플로이드 와샬 알고리즘을 사용하면 간단해지죠! 최소거리를 잘..

[Swift Algorithm] 플로이드 와샬

그래프 문제에서 자주 출제되는 문제유형중 하나에요 알고 있으면 정말 유용하게 사용 할 수 있다고 생각해요 그래프유형에서 크루스칼 알고리즘과 플로이드 와샬이 대표적인 그리디 알고리즘이에요 크루스칼은 최소 간선을 싸이클 없이 더해가면서 최소 비용을 찾는 과정이라면 (한 정점에서 다른정점으로 가는 최단거리) 플로이드 와샬은 현재 노드의 최솟값을 지정할때 현재값과 다른 경로로 왓을때의 최솟값을 비교해서 넣어주는 방식이에요 (모든 정점에서 다른정점으로 가는 최단거리) 1에서 5까지가는경우는 1 - 2 - 3 - 5 -> 비용5 1 - 2 - 5 -> 비용 3 플로이드 와샬은 이런경우에 유용해요 사용하면 1에서 5까지의 비용은 3이라고 저장되는 방식이에요 func 플로이드와샬() { for i in 0..

[Swift Algorithm] 49994 방문길이 (프로그래머스)

programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이방법 범위가 여유있기때문에 생각하기 쉬운편에 속하는 문제였어요 UDRL 문자대로 움직이고 중복되는 라인은 세지않고 범위를 넘어가지않도록 넘어갈경우 제자리! 튜플(Int, Int)를 이용해서 하려고했지만 Set 튜플이 Hashable하지않아서 Set에는 사용할 수 없더라구요 그래서 구조체를 만들어서 사용햇고 선분은 (1,0) - (0,0) 을 연결한것과 (0,0) - (1,0)을 연결한 것이 같기때문에 == 연산자를 구현해주면 Set에서 걸러질줄 알았는데 안걸러지더라구요 그래서 한번은 그대로 한번은 순서를 바꿔서 2개씩 저장했어요 양방향을 Set에 저장해..

[Swift Algorithm] 72412 순위 검색 (2021 카카오 블라인드 공채)

programmers.co.kr/learn/courses/30/lessons/72412 [Int] { var result: [Int] = [] struct Info { enum DevLanguage: String { case java, cpp, python } enum Job: String { case backend, frontend } enum Career: String { case junior, senior } enum Food: String { case chicken, pizza } let language: DevLanguage let job: Job let career: Career let soulFood: Food let score: Int init(_ s: String) { let infos ..