본문 바로가기

코딩 테스트/백준22

[백준] (Swift) 7785번: 회사에 있는 사람 📌 문제 7785번: 회사에 있는 사람 📌 풀이 Set 자료형과 관련 메서드를 알아야 한다. 역순으로 정렬할 때 sorted 메서드를 활용하면 간단히 풀 수 있다. 📌 정답 코드 import Foundation // 첫째 줄 n 입력 var n: Int = Int(readLine()!)! // 필요한 변수 초기화 var input: [String] = [] var result: [String] = [] var employees = Set() // n개의 줄에서 출입 기록을 차례로 집합에 할당 for _ in 1...n { let input = readLine()!.split(separator: " ").map { String($0) } let name = input[0] let status = input.. 2023. 4. 13.
[백준] (Swift) 14425번: 문자열 집합 📌 문제 14425번: 문자열 집합 📌 풀이 Set 자료형과 관련 메서드를 알면 간단하게 풀 수 있는 문제였다. 질문 처음에는 Set 자료형으로 요소를 추가하는 건 알았지만 아래의 궁금증이 생겼다. Q. 예시의 baekjoononlinejudge과 baekjoon처럼 해당 요소가 정확히 일치하지 않으면 count 하지 않을 수 있나? A. contains() 메서드가 알아서 count 하지 않는다(!) contains()의 예시 코드 var array = ["jellyfish", "cat", "dog", "bird"] var set = Set() for i in 0.. 2023. 4. 11.
[백준] (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) 1850번: 최대공약수 📌 문제 1850번: 최대공약수 📌 풀이 처음에는 입력값이 실제 정수가 아닌 1의 개수라서 이를 정수로 변환하는 함수를 만들었다. 하지만 그렇게 하면 입력값이 클 경우 시간이 너무 오래 걸리는 경우가 생겼다. 몇 번 실제로 값을 계속 넣어 보니 겉으로만 1의 개수이지, 1의 개수들끼리 최대공약수를 구하여 이를 정수로 변환만 하면 된다. 이를 눈치채지 못하면 계속 돌고 돌아 멘붕에 빠질 수 있다. 최대공약수를 구하는데 사용한 유클리드 호제법(Euclidean Algorithm)은 아래의 링크에서 자세히 설명해 두었다. [재귀] 유클리드 호제법과 최대공약수, 최소공배수 [재귀] 유클리드 호제법과 최대공약수, 최소공배수 유클리드 호제법을 배워 보고 재귀적으로(recursively) 구현한 것과 반복적으로(it.. 2023. 4. 3.
[백준] (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.
[백준] (Swift) 10769번: 행복한지 슬픈지 📌 문제 10769번: 행복한지 슬픈지 📌 풀이 주어진 입력을 배열로 변환한다. 배열에서 단어를 검사할 때 인덱스의 범위를 초과하면 안되므로, 1번 이전에 문자열에서 임의의 문자 2개를 추가한다. 배열의 인덱스를 접근하면서 행복한 이모티콘과 슬픈 이모티콘의 개수를 계산한다. 행복한 이모티콘과 슬픈 이모티콘의 개수를 비교하여 출력의 조건문에 따라 화면 출력한다. 📌 코드 // 행복한 얼굴과 슬픈 얼굴에 대한 개수를 변수로 할당 var happyStringCount = 0 var sadStringCount = 0 // 주어진 입력을 input에 문자열로 할당 var input = readLine()! // 인덱스 초과를 막기 위해 임의의 두 문자를 맨뒤에 추가 input += ".." // 문자열을 배열로 .. 2023. 3. 18.
반응형

티스토리툴바