므네모시아

알고리즘 문제를 풀다가 최단 경로에 관한 문제를 풀게 되었는데, 알고리즘에 대한 정확한 개념을 공부한 지 너무 오래된 것 같아 다시 공부해보았다! 최단 경로에 대한 알고리즘은 여러 가지가 있지만 이번엔 '다익스트라' 알고리즘에 대해 정리해보고자 한다. 다익스트라 알고리즘에 대해 설명하기 전 최단 경로에 대한 설명을 간단히 해보자면, 최단경로 란? - 유향 가중치 그래프를 가정 - 경로란, 한 정점에서 다른 정점까지의 길을 의미 - 경로의 길이란, 경로를 구성하는 간선들의 가중치 합을 의미 - 최단 경로란, 시작정점 → 도착정점의 경로들 중 길이가 가장 작은 경로를 의미 이때, 최단 경로에 대한 것은 또 다음과 같이 구분할 수 있다. - 단일 시작점 최단 경로 : 시작점 1개 → 모든 도착지 1. 가중치 ..

최근에는 이분 탐색을 많이 쓰지 않았다가 얼마 전 카카오 문제 중 순위 검색의 효율성을 해결하기 위해 다시 찾아봤다. 전에 C++ 로 알고리즘 짤 때는 algorithm 라이브러리에 lowerbound 함수가 있어서 그걸 사용했었는데 이젠 필요하면 직접 구현해야하니까 이 참에 개념을 확실히 정리해두는게 좋을 것 같다는 생각이 들었다. 이런게 또 정확히 기억 안나면 사소한 부분 때문에 헷갈린다,, 참고. Lower bound basics LowerBound 찾고자 하는 값 이상이 처음 나오는 위치(인덱스)를 찾는 알고리즘이다. func lowerBound(_ sortedArr: [Int], _ target: Int) -> Int { var start = 0 var end = scores.count whil..

2021 KAKAO BLIND RECRUITMENT 순위 검색 Level 2 문제 각 항목에 대해 하나 씩 선택해야 함 개발 언어 항목 cpp, java, python 지원 직군 항목 backend, frontend 지원 경력구분 항목 junior, senior 선호 소울 푸드 chicken, pizza 지원자 정보 info → 배열 크기는 1 이상 50,000 이하 → “개발언어 직군 경력 소울푸드 점수” 형식 → 이 때 점수는 1 이상 100,000 이하 → 스페이스 하나로 구분 [“java backend junior pizza 150”, ”python frontend senior chicken 210”] 요구 사항 query → 배열 크기는 1 이상 100,000 이하 → “개발언어 and 직군 a..

2022 KAKAO BLIND RECRUITMENT 신고 결과 받기 Level 1 문제 신고 횟수에 제한 없이 다른 유저를 계속 신고할 수 있음 한 유저에 대해서도 여러 번 신고가 가능하나, 동일 유저에 대한 신고 횟수는 1회로 처리됨 k번 이상 신고된 유저는 이용이 정지됨 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 보냄 각 유저 별로 메일을 받은 횟수 반환하기 id 개수 : 2이상 1,000 이하. 중복 없음 report 개수 : 1이상 200,000 이하. 이용자_id 신고한_id 형태의 문자열 k : 1이상 200 이하 Idea 각 유저 별로 신고한 id 목록 구하기 각 유저 별로 신고 받은 횟수 구하기 각 유저 별로 신고한 id 가 k 이상인지 확인하여 메일 받은 횟수 구하기 Code ..

2019 KAKAO 겨울 인턴십 튜플 Level 2 문제 튜플은 중복된 원소가 있을 수 있으나, 순서가 다르면 서로 다른 튜플이다 이 때, 중복 값이 없는 튜플 (a1, a2, a3, …, an) 이 주어질 때, 이 것은 다음과 같이 표현될 수 있다 → {{a1}, {a1,a2}, {a1,a2,a3}, ..., {a1,a2,a3,...,an}} 예로. 튜플이 (2, 1, 3, 4) 이면 다음과 같이 표현될 수 있다. 집합은 순서가 없으므로 집합 내 순서가 바뀔 수 있다. → {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} → {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}} → {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}} 특정 튜플을 표현..

연습문제 최솟값 만들기 Level 2 문제 길이가 같은 배열 두 개가 주어짐 각각의 배열에서 하나씩 숫자를 뽑아 두 수를 곱함 이 과정을 배열의 길이만큼 반복하며 곱한 값을 누적하여 더할 때 최종 누적 값이 최소가 되도록 만들어야 함 이 때, 각각의 숫자는 한 번씩만 뽑을 수 있음 배열의 크기는 1000 이하 자연수 원소의 크기는 1000 이하 자연수 Idea 한 배열은 가장 작은 값부터, 다른 배열은 가장 큰 값부터 각각 곱해서 더하면 가장 작은 값이 나올 것 같음 하나는 오름차순, 다른 하나는 내림차순으로 정렬해서 반복문 사용해서 곱하여 누적하기 Code Swift 뭐지,, 처음에 효율성에서 두 개 시간초과 나길래 잉?? 아닌가 하고 찾아봤는데 다 나랑 똑같음 그래서 다시 돌렸더니 통과됨! impor..

연습문제 피보나치 수 Level 2 문제 2 이상의 n 이 주어졌을 때, n 번째 피보나치 수를 1234567로 나눈 나머지 구하기 Idea 반복문으로 피보나치 수 구하기 한 번 구한 값은 저장하기 Code Swift 재귀 방식은 시간 초과 및 core dump 에러 뜸 func solution(_ n: Int) -> Int { var fibonacci = [0, 1] for i in 2...n { let next = (fibonacci[i-1] + fibonacci[i-2]) % 1234567 fibonacci.append(next) } return fibonacci[n] } 다른 사람 풀이 배열에 저장하지 않고 하는 법 func solution(_ n: Int) -> Int { var n0 = 0, ..

연습문제 행렬의 곱셈 Level 2 문제 두 개의 이차원 행렬이 주어질 때 arr1 에 arr2 를 곱한 결과 반환하기 행과 열의 길이는 2 이상 100 이하 각각의 원소는 -10 이상 20 이하 자연수 곱할 수 있는 배열만 주어짐 Idea arr1 의 행과 arr2 의 열을 각각 곱한 합이 새로운 원소가 됨 arr1 의 행 개수만큼 바깥 반복문을 돌고 arr2 의 열 개수만큼 안쪽 반복문을 돌고 arr1 의 열 개수 또는 arr2의 행 개수만큼 그 안쪽 반복문을 돌면서 arr1 의 행과 arr2 의 열을 곱해줌 arr1 의 행과 arr2 의 열의 원소를 각각 곱하여 합한 값이 새로운 행렬의 한 행의 하나의 원소가 됨 arr1 의 하나의 행에 대해서 arr2 의 모든 열을 위 작업을 하게 되면 새로운 행..

연습문제 JadenCase 문자열 만들기 Level 2 문제 JadenCase 란 모든 단어의 첫 문자가 대문자고, 그 외의 알파벳은 소문자인 문자열 문자열이 주어졌을 때 JadenCase 로 바꿔 리턴하기 알파벳과 공백으로 이루어져 있음 첫 문자가 영문이 아닌 경우는 뒤의 영문 모두 소문자 Idea 공백으로 구분해서 나누고 첫 글자를 확인해서 알파벳이면 대문자로 바꾸기 Code Swift 참고. word.capitalized 를 사용하면 처음 나오는 알파벳을 대문자로 바꿔주고 나머지 뒤의 알파벳은 소문자로 바꿔줌. 이 문제에서는 첫 글자가 알파벳이 아닌 경우 대문자로 변경하지 않기 때문에 사용할 수 없음 word.capitalized() 와는 다름!!! 주의. 공백이 여러 개 있는 경우도 고려해야 함..

연습문제 N개의 최소공배수 Level 2 문제 100 이하의 n 개의 자연수가 주어질 때 n 개의 수에 대한 최소공배수 구하기 예. [2,6,8,14] -> 4개의 수에 대한 최소 공배수 Idea 최소공배수 구하고 나온 최소공배수와 다음 수의 최소공배수 구하는 방식으로 반복적으로 구하기 Code Swift 고차함수 활용: reduce func lcm(_ a: Int, _ b: Int) -> Int { return (a * b) / gcd(a, b) } func gcd(_ a: Int, _ b: Int) -> Int { var num = [a, b].max()! var divisor = [a, b].min()! while num % divisor != 0 { let remainder = num % divi..