본문 바로가기

코딩 테스트43

[백준] (Swift) 10815번: 숫자 카드 📌 문제 10815번: 숫자 카드 📌 풀이 풀이는 두 가지가 모두 정답으로 나왔다. 이진 탐색 세트(Set) 자료형 (1) 이진 탐색 처음에는 주어진 배열을 선형으로 접근했더니 ‘시간 초과’가 나와서 이진 탐색으로 바꿔서 푸니 바로 정답이 나왔다. (2) 세트(Set) 자료형 이렇게 끝내기는 너무 아쉬워서 다른 자료형으로 풀어 보았는데, Set 자료형으로 풀면 정답이 나온다. for in을 쓸 때 Array의 시간 복잡도는 $O(n)$, Set의 시간 복잡도는 $O(1)$이다. 그 이유를 찾아 보니, Set는 해시 테이블을 이용해 만든 자료구조이기에 선형 탐색을 하지 않는다고 한다. 선형 탐색과 이진 탐색에 대한 간단한 설명은 여기를 클릭! [CS50 2019] (컴퓨팅 사고) 알고리즘 이전 강의에서는 .. 2023. 4. 11.
[백준] (Swift) 2981번: 검문 📌 문제 [백준] (Swift) 2981번: 검문 📌 풀이 문제를 푸는데 수학적인 센스가 필요한 문제가 있는데 이 문제가 대표적인 것 같다. 입력 받는 값을 '나머지'의 관점으로 다시 생각해 보자. 종이에 적힌 모든 숫자를 적은 배열 papers에서 임의의 숫자 m으로 나누었을 때 나머지가 같은 두 요소를 A, B라 하자. 이를 아래와 같이 표현할 수 있을 것이다. $papers\begin{cases} A = ma + r \\ B = mb + r \end{cases}$ 두 요소를 한번 빼 보면 나머지가 없어지는 걸 확인할 수 있다. $A - B = m(a - b)$ 아래 2가지가 문제 풀이의 핵심인 것 같다. 이렇게 나머지를 없앤 요소를 하나씩 모아서 최대공약수를 구하고 1번을 제외한 최대공약수의 공약수.. 2023. 4. 7.
[프로그래머스] (Swift) 정수 제곱근 판별 - Lv.1 📌 문제 코딩테스트 연습 - 정수 제곱근 판별 | 프로그래머스 스쿨 📌 풀이 Swift의 squareRoot() 메서드와 삼항 연산자를 이용해 풀어 보았다. squareRoot() | Apple Developer Documentation 다만, squareRoot()는 Double에 있는 공식 문서여서 형 변환에 유의해야 한다. 문제의 함수의 반환값 또한 Int가 아닌 Int64이니 그에 맞게 형 변환을 하자 📌 코드 func solution(_ n:Int64) -> Int64 { // n의 제곱근을 상수로 할당 let root = Int64(Double(n).squareRoot()) // 제곱근이 실제로 맞으면 원하는 조건의 반환값을, 아니면 -1을 반환 return root * root == n ? .. 2023. 4. 3.
[백준] (Swift) 1850번: 최대공약수 📌 문제 1850번: 최대공약수 📌 풀이 처음에는 입력값이 실제 정수가 아닌 1의 개수라서 이를 정수로 변환하는 함수를 만들었다. 하지만 그렇게 하면 입력값이 클 경우 시간이 너무 오래 걸리는 경우가 생겼다. 몇 번 실제로 값을 계속 넣어 보니 겉으로만 1의 개수이지, 1의 개수들끼리 최대공약수를 구하여 이를 정수로 변환만 하면 된다. 이를 눈치채지 못하면 계속 돌고 돌아 멘붕에 빠질 수 있다. 최대공약수를 구하는데 사용한 유클리드 호제법(Euclidean Algorithm)은 아래의 링크에서 자세히 설명해 두었다. [재귀] 유클리드 호제법과 최대공약수, 최소공배수 [재귀] 유클리드 호제법과 최대공약수, 최소공배수 유클리드 호제법을 배워 보고 재귀적으로(recursively) 구현한 것과 반복적으로(it.. 2023. 4. 3.
프로그래머스) 분수의 덧셈 (Swift) 📌 문제 코딩테스트 연습 - 분수의 덧셈 | 프로그래머스 📌 접근 방식 두 분수를 더하여 기약분수로 만드는 알고리즘은 크게 세 단계로 나누어진다. 통분: 서로 다른 분모를 같게 만든다. 덧셈: 분모를 같게 하기 위하여 곱해진 분자를 서로 더한다. 약분: 분모, 분자를 더 이상 나눌 수 없을 때까지 나눈다. → 최대공약수 이용 여기서 통분과 덧셈은 단순한 사칙연산으로 해결이 가능하지만, 약분에서는 최대공약수를 구하여 한번에 나누는 게 핵심이다. 최대공약수을 구하는 방법은 유클리드 호제법을 이용했는데, 이에 대한 설명은 아래에 자세히 다루었으니 참고 하자. [재귀] 유클리드 호제법과 최대공약수, 최소공배수 유클리드 호제법을 배워 보고 재귀적으로(recursively) 구현한 것과 반복적으로(iterative.. 2023. 3. 27.
프로그래머스) sublime 자주 쓰는 단축키 (Mac) 프로그래머스의 sublime으로 코딩 테스트를 푸는데 중간에 편집하고 다듬는 과정은 여간 번거롭지 않다. 더군다나 sublime의 단축키는 기존에 쓰던 IDE의 단축키와 같은 것도 있고 다른 것도 있어 더 헷갈린다. Visual Studio Code에서 자주 쓰던 단축키 기능이 sublime에도 있나 해서 찾아 보며 정리해 봤다. 문제를 풀며 자주 쓰는 것들을 모아 봤는데, 유용한 것이 있으면 계속 업데이트 할 예정이다. 📌 한 줄 편집 단축키 설명 CTRL + CMD + ↑/↓ 줄 전체 위/아래로 한 줄 이동 CMD + SHIFT + D 줄 전체 복제 CMD + X 줄 전체 잘라내기 CMD + RETURN 커서부터 줄 처음까지 삭제 CMD + K 커서부터 줄 끝까지 삭제 📌 다중 커서 편집 단축키 설명.. 2023. 3. 27.
[백준] (Python/Swift) 3040번: 백설 공주와 일곱 난쟁이 📌 문제 3040번: 백설 공주와 일곱 난쟁이 📌 올바른 풀이 7개의 옳은 데이터를 찾는 게 아닌 그것의 여집합인 2개의 틀린 데이터를 찾는 것이 핵심이다. 그 2개의 데이터를 어떻게 다루냐에 따라 여러 방식이 있을 것이다. 압도적으로 크거나 압도적으로 작은 수로 재할당 하거나 처음 발견한 두 깂을 저장하여 배열에서 삭제하거나 적당한 수(0이나 -1)로 재할당 하되, 이중 for 문을 한번에 break 하여 빠져 나오는 것이다. 아래의 내용은 초반에 잘못된 방식으로 접근하여 작성한 풀이와 코드이다. 📌 잘못된 풀이 7개의 옳은 데이터를 찾는 게 아닌 그것의 여집합인 2개의 틀린 데이터를 찾는 것이 핵심이다. 이중 반복문을 돌 때, Python의 range() 함수와는 다르게 이중 for 문에서 바깥쪽 f.. 2023. 3. 25.
[백준] (Swift) 1157번: 단어 공부 📌 문제 1157번: 단어 공부 📌 풀이 1: [Character: Int] 형태의 딕셔너리 딕셔너리를 이용해 주어진 문자열의 인덱스를 지날 때마다, 해당 값의 알파벳을 딕셔너리의 값에서 1을 더하는 식으로 문제를 풀었다. 📌 코드 // 입력 받은 문자열을 input에 할당 let input = readLine()! // 함수에 input을 대입하여 출력 print(findWordOfMaxFrequency(input)) // 주어진 단어에서 가장 많이 사용된 알파벳을 대문자로 출력하는 함수 정의 func findWordOfMaxFrequency(_ word: String) -> Character { var charFrequency: [Character: Int] = [:] var maxCharFreque.. 2023. 3. 22.
[백준] (Swift) 3613번: Java vs C++ 📌 문제 3613번: Java vs C++ 📌 풀이 개요 이 문제의 핵심은 Java 형식(Camel case)과 Cpp 형식(Snake case)의 특징을 확인하여 이를 서로 변환하는 것이다. 각 형식의 예외 조건을 찾아 해당 형식에 부합한지를 판별해야 한다. 변수명의 이름이 바뀔 때마다 Java 형식은 대문자가 되고, Cpp 형식은 밑줄('_')이 따라 붙는다. 여기에 맞지 않는 것은 예외 처리로 판별한다. 📌 풀이 1. Java 형식이 아닐 때 첫글자가 대문자일 경우 밑줄이 하나라도 있을 경우 2. Cpp 형식이 아닐 때 양끝에 밑줄이 있을 경우 밑줄이 2개 이상 붙어 있을 경우 대문자가 하나라도 있을 경우 이제 위의 형식을 판별했다면 서로 다른 형식으로 변환하면 된다. 3. Cpp에서 Java로 변.. 2023. 3. 21.
[백준] (Swift) 10872번: 팩토리얼 (재귀 vs 반복) 📌 문제 10872번: 팩토리얼 📌 풀이 개요 N에서 1까지 차례로 곱하는 팩토리얼은 크게 2가지 경우로 풀어 볼 수 있다. 재귀적으로(recursively) 푸는 방식이거나, 반복적으로(iteratively) 푸는 방식이다. 📌 풀이 1: 재귀함수 재귀에 대한 개념은 아래의 링크 페이지에 정리해 두었다. [알고리즘] 재귀(Recursion)와 콜 스택(Call Stack) 알고리즘 이론에서 기본이며, 분할 정복이나 백트래킹 같은 여러 알고리즘의 기반을 맡고 있는 재귀(recursion)는 무엇일까? 이에 대해 자세히 알아 보자. 인형 안에, 조금 더 작지만 모양이 같은 andy-archive.tistory.com 재귀함수로 푸는 방식은 아래와 같다. 팩토리얼에 대한 함수를 정의해야 한다. → $\mat.. 2023. 3. 18.
반응형

티스토리툴바