Coding Test

알고리즘 문제 풀이

3085번: 사탕 게임

스위프트로 알고리즘 문제 푸는 법을 알아봅니다!

시간 복잡도와 공간 복잡도에 대해 알아봅니다.

10171번: 고양이이 문제의 포인트는 이스케이프 문자인 “\\”를 어떻게 출력하느냐입니다.이스케이프 문자는 다음 문자가 특수 문자임을 알리는 백슬래시()를 의미합니다.이스케이프 문자를 하나 출력하기 위해서는 백슬래시를 두번 입력합니다.

2884번: 알람 시계예외적인 케이스를 2개 이상 고려해야해서 살짝 복잡할 수 있습니다.h와 m를 계산할 때 각각 0 이하가 되는 케이스를 고려해서 예외처리 해주어야 합니다!

8393번: 합등차수열을 구하는 공식을 알고 있다면 쉽게 풀 수 있는 문제입니다.

2588번: 곱셈 정수의 각 자릿수에 접근하는 방법을 알 수 있는 문제입니다. 파이썬이 string[0]처럼 subscript를 통해서 random access가 가능한 것과는 달리 스위프트의 String은 해당 방법이 불가능합니다. 또한 스위프트의 String은

10950번 - A+B - 3 Test Case의 갯수를 입력 받아서 여러줄의 입력을 받는 방법입니다. 먼저 T를 입력 받아 정수로 타입을 바꾼 이후에 반복문을 활용하면 됩니다.

2742번: 기찍 N Collection을 거꾸로 만들고 싶을 때는 .reversed()를 사용하면 됩니다. 이 메소드는 String을 뒤집을 때도 사용할 수 있습니다.

🙏  아래 포스팅을 참고하여 작성했습니다. 문제 링크 2438번 - 별 찍기 - 1 방법 1. print의 terminator 활용하기 방법 2. 문자열의 ‘+’ 연산 사용하기 방법 3. String에 repeat를 사용해서 문자열 만들기

2439번 - 별 찍기 - 2 방법 1. String(repeat: ) 방법 2. 이중반복문

10871번: X보다 작은 수 고차함수 filter를 활용하면 Array 내의 조건에 맞는 element들만 골라낼 수 있습니다.

마지막 테스트 케이스의 조건이 주어질 때 10952번 - A+B - 5 마지막 테스트 케이스의 조건이 주어진 경우에는 일단 while true를 통해서 계속 input을 받도록 하고 중간에 마지막 input의 조건을 만족하는 경우 break문을 사용하면 됩니다.

1110번: 더하기 사이클 처음 풀이 2자리 수를 다루는 것인데 너무 코드가 복잡하다 일단 수행하고 나중에 조건을 따지는 반복문은 repeat-while문을 쓰는 것이 좋다. N이 10 이하일 때 예외조건인 것 같지만 따져보면 동일한 연산이다 개선된 풀이 각각의

[Swift] 10818 최소, 최대 - 백준 B3 시간 초과 시간 초과가 난 이유: components를 사용했기 때문 → .split을 사용하자❗️ 정답 split은 Foundation을 불러올 필요가 없고 속도도 더 빠르다. min()과 max()는 시간복

숫자의 개수 처음 풀이 Int: 특정 element를 n개 반복해서 만드는 메소드입니다. 개선된 풀이 forEach문을 사용하면 더 깔끔하게 반복문을 사용할 수 있다. forEach문을 사용하면 Array를 순회해야하는 동작을 더 편하게 할 수 있다. 10으로

4344번: 평균은 넘겠지 처음 풀이 popFirst를 사용하기 위해서는 SubSequence로 만들어야 한다! 만드는 방법은 [0...]을 붙이면 된다. 다른 사람들은 popFirst하지 않고 그냥 평균을 구할 때 [1...]의 방식으로 사용하는 경우도 있

8958번: OX퀴즈 처음 풀이 String을 반복문으로 돌면서 O이 나올 때 마다 현재 점수를 계산해서 최종 점수에 더하고 X가 나오면 현재 점수를 0으로 되돌려 놓는 방식 💡 String은 index로 접근은 안되지만 반복문은 사용할 수 있음! 숏코딩 O이

4673번: 셀프 넘버 풀이 ❗️ 처음에는 d(n) > 10001이면 반복문을 멈추도록 했는데 n이 증가하면 무조건 d(n)은 증가하는 것이 아니었다. → d(8999) > d(9000) 따라서 d가 index 범위에 들어가는지 확인하면서 n 자체는

1065번: 한수 한수의 정의에 맞추어서 판독하는 함수를 구현합니다. 등차수열 여부를 가리기 위해서는 자릿수로 접근해야 하므로 정수를 Array로 바꾸어 줍니다. 1자리수는 무조건 한수이므로 true를 리턴한다. 반복문을 통해 각 자릿수가 등차수

10809번: 알파벳 찾기 (알파벳의 아스키 코드) - (”a”의 아스키 코드)를 하면 a ~ z를 각각 0 ~ 25로 나타낼 수 있습니다. 입력된 문자열을 UInt8의 배열로 바꾸어 줍니다. check 배열에 처음 나온 index를 저장해줍시다. check

2675번: 문자열 반복 input을 “ “으로 구분해서 R과 S로 구분한다. R은 Int로 캐스팅 S는 문자열 그대로 놔둔다. String(repeat:)를 활용해서 R만큼 반복된 문자열을 출력한다. 반복문을 줄이기 위해서 사용 정확히

1157번: 단어 공부 입력 받은 단어를 소문자로 바꾸고 Character a ~ z를 각각 0 ~ 25의 정수로 바꾸어 배열로 저장한다. check 배열을 만들어서 a ~ z의 갯수를 저장한다. check[0] = (a의 갯수) 가장 많이 나온 문자의 갯수를

2908번: 상수 ⭐️ Array와 마찬가지로 String로 reversed를 사용해서 거꾸로 뒤집을 수 있다!

5622번: 다이얼 알파벳이 3개씩 묶여있었다면 아스키 코드를 써서 더 짧게 쓸 수 있었지만 중간에 4개씩 묶여있는 부분도 있기 때문에 그냥 일일이 구하는 방법 뿐이었습니다. 다른 분들의 풀이를 참고하니 Dictionary를 구현하는 방법 외에도 Switch문을 사용

2941번: 크로아티아 알파벳 .replacingOccurrences() 메소드를 사용하면 쉽게 풀 수 있습니다. 해당 메소드는 특정 문자열을 정해진 문자열로 바꾸어주는 메소드입니다. “dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로

1316번: 그룹 단어 체커 파이썬에서는 GroupBy라는 너무 편한 기능이 있었는데 스위프트에는 그런 기능이 없더라구요... 그래서 문자열을 순회하면서 하나하나 따져보는 방법을 사용합니다. 먼저 check라는 배열에 지금까지 나온 문자열을 저장하고 before라는

1712번: 손익분기점 처음에는 판매량을 1씩 더해가는 방법을 사용해야하나 생각했지만 A, B, C의 크기를 감안하면 시간초과가 날 가능성 100%입니다. 따라서 개당 판매 수익을 구한 후에 개당 판매 수익이 0 이하면 절대 손익분기점을 넘을 수 없으므로 -1

처음 풀이 2839번: 설탕 배달 그리디 알고리즘 문제이다. 다만 다른 그리디 알고리즘과는 다르게 설탕 봉지가 5, 3으로 서로 배수 관계가 아닙니다. 보통 가장 흔한 그리디 문제는 100원, 500원, 1000원으로 계산하기처럼 선택지들이 배수 관계를 가지

2292번: 벌집 수열 문제입니다. 알고리즘 문제라기 보다는 수학문제에 가깝습니다. 첫 단계를 단순히 1이 아니라 0 ~ 1로 볼 때 더 쉽게 풀 수 있습니다. 한 단계를 올라갈 때마다 육각형의 변이 하나씩 증가하므로 범위도 그만큼 커집니다. 전체 범위를 하나

1193번: 분수찾기 수열 + 범위가 혼합된 문제는 (ex. 벌집) 첫 단계의 범위에 0을 포함하면 좀 더 생각하기 쉬워집니다. 분수의 첫 단계를 0 ~ 1로 잡으면 규칙성을 더 쉽게 발견할 수 있습니다. 규칙성은 각 단계의 분수의 갯수가 1, 2, 3, 4,

2869번: 달팽이는 올라가고 싶다 미끄러지는 것을 감안했을 때 하루에 (A - B) 만큼 전진하는 달팽이입니다. 정상에 도달했을 때는 미끄러지지 않으므로 마지막날은 (A - B)가 아니라 무조건 A만큼 전진할 수 있습니다. 따라서 V가 아니라 (V - A)를 (A

10250번: ACM 호텔 나머지와 묷을 이용해서 호수를 구하면 됩니다. 층수를 구할 때는 나머지를 사용합니다. 하지만 그냥 n을 H로 나누는 경우 나머지가 0일 때 H층에 배정되는 것을 계산하기 쉽지 않습니다. 이런 경우에 (n - 1)에서 H를 나눈

2775번: 부녀회장이 될테야 2차원 배열을 사용하는 방법 k와 n의 최대 크기가 15밖에 안되므로 미리 모든 경우의 수를 구하고 시작했습니다. 2차원 배열을 이용한 문제입니다. 재귀함수를 사용하는 방법 다음 값을 구하기 위해 그 이전 값을 사용하는 방식 (ex

1011번: Fly me to the Alpha Centauri 문제 풀이 아이디어 풀이 전략 이동 횟수별 최대 이동거리를 구하고 x와 y 사이의 거리에 맞추어 최소 이동횟수를 구합니다. 규칙성 찾기 = 직접 적어보는게 최고! 이동 횟수별 최대 이동거리를 구해

10162번: 전자레인지 가장 기본적인 그리디 문제입니다. 가장 큰 버튼부터 최대한 많이 누르고 나머지를 작은 버튼을 누르면 됩니다. 마지막에 나머지가 아직 남아있다면 버튼 3개로 구현할 수 없는 조리시간이므로 -1을 출력합니다.

10162번: 전자레인지 가장 기본적인 그리디 문제입니다. 가장 큰 버튼부터 최대한 많이 누르고 나머지를 작은 버튼을 누르면 됩니다. 마지막에 나머지가 아직 남아있다면 버튼 3개로 구현할 수 없는 조리시간이므로 -1을 출력합니다.

1439번: 뒤집기 문자열을 모두 뒤집어보면서 구할 수는 없습니다. 규칙성을 찾아봅시다. 카드가 바뀌는 지점의 숫자와 그에 따른 뒤집기 횟수를 따져봅시다. 0번 바뀜 (0 / 1) = 0회 1번 바뀜 (111000) = 1회 → 0이나 1중 아무거나

5585번: 거스름돈 가장 기본적인 그리디 문제입니다. 주어진 경우의 수 (위 문제의 경우 동전)이 많을 경우에는 각각 변수를 설정하지 말고 Array에 넣어서 반복문을 활용합니다!

1789번: 수들의 합 문제가 너무 짧아서 이해하기 힘든... 그런 스타일입니다. “서로 다른” N개의 자연수의 합이 S인데 S가 주어졌을 때 N의 최댓값을 찾는 것이 문제입니다. N개의 자연수가 “서로 달라야"하므로 최대한 가장 작은 자연수인 1부터 꽉꽉 채

4796번: 캠핑 P기간 동안 최대 L만큼만 캠핑할 수 있으므로 일단 V에 들어갈 수 있는 P 길이의 기간을 구합니다. 거기에 L을 곱해 줍니다. ⭐️ 나머지를 처리하는 과정에 두 가지 분기가 있습니다 먼저 남은 날짜라 L보다 짧다면 = 남은 날은 전부 캠핑할 수 있습니다. 반면에 남은 날짜가 L보다 길다면 = 남은 날 중에 L만큼...

3009번: 네 번째 점 직사각형의 네 꼭지점의 특성을 보면 각각 두쌍의 같은 x, y 좌표로 이루어져 있습니다. 예를 들면 (1, 1), (1, 2), (2, 1), (2, 2)는 직사각형의 네 꼭지점인데요. x좌표만 따로 떼서 보면 1이 한쌍, 2가 한쌍이죠.

4153번: 직각삼각형 중학교 때 배웠던 피타고라스 정리가 빛을 발하는 문제입니다. 삼각형의 가장 긴 변의 제곱이 다른 두 변의 제곱의 합과 같다면 그 삼각형은 직각삼각형입니다. 가장 긴 변을 구하기 위해서 주어진 입력을 정렬했습니다. Array의 so

3053번: 택시 기하학 택시 기하학의 정의만 파악하면 코드 자체는 너무나 간단합니다. 아래 그림을 봅시다. 먼저 T1을 원점에 두고 T2는 x축 위에 R만큼 떨어진 점이라고 합시다. 택시 기하학에서 원의 정의는 유클리드 기하학과 동일하므로 동일한 거리

10872번: 팩토리얼 반복문을 활용한 방법 🤷‍♂️ 약간 덜 세련된(?) 방식입니다. 중간에 0이 입력되는 경우 예외처리를 따로 해주어야 합니다. (실행이 종료되도록) 1에 1 ~ n까지 곱해주고 출력합니다. 재귀함수를 활용하는 방법 🙆‍♂️ 탈출 조건은

2798번: 블랙잭 브루탈 포스 (모든 경우의 수를 따져보기)를 적용해야 하는 문제입니다. 카드를 고를 때 특정한 규칙이 없음 N이 100 밖에 안됨 (3중 반복문을 사용해도 1000000번의 연산 밖에 안됨) 파이썬은 combination이라는 유용한

2231번: 분해합 N의 분해합을 보고 N을 구할 수 있는 방법은 없습니다. 따라서 가장 작은 생성자를 구하기 위해서는 직접 분해합을 구해보는 방법 밖에는 없습니다. 다행히도 N의 최대 백만이기 때문에 직접 반복을 해도 시간 초과의 부담은 없습니다. 분

7568번: 덩치 자기 보다 덩치가 큰 사람의 수를 구하기 위해서는 무조건 모든 사람과 비교하는 수 밖에는 없습니다. (브루탈 포스) N이 50이므로 이중 반복문을 사용해도 안전합니다. 입력을 튜플의 형태로 받아서 몸무게와 키를 하나의 자료형에 저장할 수 있도

1018번: 체스판 다시 칠하기 주어진 입력에 특정한 규칙이 없으므로 모든 경우의 수를 계산해서 푸는 문제입니다. 다시 칠하는 칸을 계산하는 함수를 만듭니다. 체스판은 체스판은 BWBW로 반복되거나 WBWB로 반복되는 구조이므로 각각의 경우에 맞추어 다

1436번: 영화감독 숌 코드 안에 적어놓았지만 마찬가지로 영화제목에 일정한 규칙은 없습니다. 그리고 N이 10000보다 작으므로 모든 경우의 수를 따져보아도 긴 시간이 걸리지 않습니다. 666이 들어가는지 확인하는 함수를 만듭니다. 자릿수를 따질 때는

10448번: 유레카 이론 처음에는 수열의 관점에서 접근하려고 했으나 삼각수 3개의 합은 규칙적으로 증가하는 수열이 아니었습니다. k가 1000 밖에 되지 않으므로 모든 경우의 수를 다 찾아 놓고 입력값을 거기서 찾는 것이 가능합니다. 먼저 1000이하의 삼각수들을

1931번: 회의실 배정 그리디 문제의 특징 n이 제법 크다. → 이중 반복문 외의 프루탈 포스는 적용 불가능합니다. 시간의 범위는 엄청 넓다. → [0] * n 등 메모리에 저장하는 방식은 불가능합니다. 회의 시간이 주어지는 규칙은 없다 → 규

파이썬으로 순열 구현하기

2503번: 숫자 야구 문제 접근 아이디어 주어진 민혁의 물음, 영수의 대답으로 정답을 역으로 유추하는 것은 너무 어려운 일입니다. 하지만 어떤 임의의 숫자에 스트라이크와 볼 갯수를 구하는 것은 쉬운 일입니다. 그렇다면 모든 가능한 숫자의 스트라이크의 볼 갯수를 구

스위프트로 조합 구현하기

9012번: 괄호 Stack 활용하기 해당 문제는 순서가 존재하는 (여는 괄호 먼저, 닫는 괄호 나중에) 쌍을 매칭시켜서 순서와 갯수를 모두 확인하는 문제입니다. 이런 문제는 stack을 활용해서 먼저 오는 괄호를 push, 나중에 오는 괄호를 pop하는 방식을 통해서 순서와 갯수가 맞는지 모두 확인할 수 있습니다.

1935번: 후위 표기식2 후위 표기식 이란? 역폴란드 표기법 - 위키백과, 우리 모두의 백과사전 후위 표기식은 먼저 연산의 대상이 되는 두 수가 나오고 그 후에 연산자가 등장합니다. 즉 연산자를 만나면 최근에 나온 두 수를 해당 연산자로 연산을 하면 된다는 것입니다. 후위 표기식을 계산하기 위해서는 자료구조 Stack을 활용합니다. 수가 나오면 st...

2164번: 카드2 카드를 버리는 행위, 맨 아래로 보내는 행위는 전부 카드 뭉치의 위의 카드가 대상입니다. 새로운 카드는 맨 아래에 추가, 나가는 카드는 맨위 선입선출의 구조 따라서 자료 구조 큐를 사용하면 쉽게 풀 수 있는 문제입니다.

참고한 블로그 🙏 [Swift] 큐 큐를 구현하는 두 가지 방법 파이썬은 queue를 내장하고 있는 한편 Swift는 순열, 조합과 마찬가지로 직접 구현해서 사용해야 합니다. 🤔 그냥 Array을 사용하면? dequeue (큐에서 데이터 꺼내기)를 구현하기 위해 배열에 removeFirst를 사용하게 되면 시간초과가 날 가능성이 높습니다. de...

참고한 블로그 🙏 스위프트 | "(최소)힙 구현"하기 (Swift5 | Heap - MinHeap) Swift) 힙(Heap) 구현 해보기 힙의 정의 최댓값 혹은 최솟값의 연산을 빠르게 하기 위해서 고안된 완전이진트리를 기반으로 한 자료구조를 의미합니다. 힙

11286번: 절댓값 힙 풀이 절댓값 힙의 경우 일반적인 최소힙을 사용하는 경우 절댓값으로 만들기 전 값을 알 수 없으므로 절댓값과 원래 값을 묶어서 저장해야 합니다. Pair 구조체 만들기 절댓값과 원본값을 가지고 있는 구조체를 만듭니다. 해당 구조체는 Comparable Protocol을 준수해야 하는데요. 이 프로토콜은 func <를 구현함으로...

7785번: 회사에 있는 사람 추가 / 삭제가 O(1)인 자료형 주어진 문제는 어떤 자료형에 주어진 String을 넣었다가 빼는 일을 자주 수행해야 합니다. 많이 사용하는 Array의 경우 append는 O(1)이지만 remove의 경우 O(n)의 시간복잡도를 가지므로 시간초과가 날 가능성이 높습니다. Array는 index로 접근하는 것이 O(1)인...

1302번: 베스트셀러 사용할 자료형: Dictionary 입력이 들어올 때 마다 데이터에 접근해서 판매량을 + 1 해주어야 합니다. 따라서 데이터에 접근할 때 O(1)인 자료형을 찾아야 합니다. Dictionary와 Set이 있는데 그 중에서 key-value의 쌍으로 이루어져서 책이름-판매량으로 저장하기 좋은 Dictionary를 사용합니다. 풀이...

1021번: 회전하는 큐 🤔 어떻게 풀어야 할까? 써야할 자료구조 = deque : Double-Ended Queue = 앞뒤로 모두 pop할 수 있는 queue : 일단 맨 앞에서 원소를 뽑아내야 하므로 선입후출 방식을 큐를 써야 합니다. : 추가적으로 왼쪽 이동, 오른쪽 이동 연산도 원소를 pop 앞 or 뒤에 push한 것입니다. : 세 가지...

1158번: 요세푸스 문제 Queue를 활용해서 푸는 방법 나머지를 활용해서 푸는 방법 Swift에서는 Queue를 직접 구현해야하기 때문에 index를 추적해가면서 푸는 방식이 더 간단한 방식입니다. 시간 복잡도는 동일하게 O(n**2)입니다.

2346번: 풍선 터뜨리기 🤔어떻게 풀어야 할까? 풀이

1406번: 에디터 문제 풀이 아이디어 처음에는 문자열을 배열로 저장하고 커서의 위치를 index로 추적해가면서 문제를 풀려고 했습니다만 이렇게 하는 경우 커서를 이동하는 경우는 문제가 없습니다만 문자를 삭제하거나 문자를 입력하는 경우에 시간 복잡도가 O(n)입니다. 🚫 입력이 최대 500,000개이므로 시간초과가 날 가능성이 높습니다. 그렇다면 무...

15552번: 빠른 A+B 문제 풀이 아이디어 해당 문제를 풀기 위해서는 빠른 입출력을 구현해야 합니다. Swift에서 빠른 입출력을 구현하기 위해서는 별도의 클래스를 선언하고 사용해야 합니다. FileIO 클래스는 표준 입력 (= 키보드 입력)을 받아서 byte의 배열로 저장합니다. 그리고 나서 byte를 하나하나 읽어서 원하는 자료형으로 리턴합니다...

1874번: 스택 수열 문제 풀이 아이디어 수열에 숫자를 push, pop을 반복하면서 푸는 문제입니다. push는 무조건 1 ~ n의 오름차순으로 해야하고 pop의 주어진 순서대로 해야합니다. 이 경우 숫자를 오름차순으로 push하므로 stack 안에는 오름차순으로 정렬이 되어있습니다. 따라서 만약에 pop해야할 숫자가 stack의 마지막 (pop...

1764번: 듣보잡 문제 풀이 아이디어 Set을 활용한 풀이 참고) swift의 집합 연산 Dictionary (Hash table)을 활용한 풀이 삽입과 탐색이 O(1)인 Dictionary를 활용한 풀이입니다. 집합을 이용한 풀이와 시간 복잡도가 O(nlogn)으로 동일합니다.

10799번: 쇠막대기 문제 풀이 아이디어 따라서 이 문제를 풀기 위해서 주목한 점은 “)”가 나올 때마다 파이프 조각이 추가된다는 것입니다. “)”가 레이저를 의미하는 닫힌 괄호라면 현재까지 존재하는 파이프의 갯수만큼 새로운 조각이 생길 것입니다. “)”가 파이프를 의미하는 닫힌 괄호라면 파이프 꼭다리가 남으므로 새로운 조각이 1개 생길 것입니다. ...

17298번: 오큰수 문제 풀이 아이디어 풀이

2841번: 외계인의 기타 연주 문제 풀이 아이디어 풀이 코드

1966번: 프린터 큐 문제 풀이 아이디어 코드 중요도만 별도의 배열로 관리 어차피 출력되는 문서의 순서는 중요도가 높은 순입니다. 따라서 중요도만 오름차순으로 정렬된 별도의 배열로 관리를 하는 방법입니다. 현재 pop한 문서의 중요도가 중요도 배열의 있는 last (= 현재 남은 문서 중에서 가장 높은 중요도)와 일치하면 중요도 배열의 last를...

dfs 그래프 완전 탐색 알고리즘으로 주로 재귀함수를 통해서 구현합니다. 이 문제(https://www.acmicpc.net/problem/11724))의 입력을 받아서 구현하는 예시입니다. 인접 행렬로 dfs 구현하기 인접 행렬은 정점의 갯수만큼의 크기를 가지는 행렬을 선언한 후에 그 행렬에 간선을 저장하는 방식입니다. 어떤 정점에서 다른 정점으로...

11724번: 연결 요소의 개수 문제 풀이 아이디어 완전탐색을 활용해서 해당 정점에 연결된 모든 요소를 탐색하면 됩니다. 그래프 완전탐색 알고리즘은 dfs와 bfs가 있습니다. 여기서는 dfs를 사용해서 구현해보겠습니다. 코드

2178번: 미로 탐색 문제 풀이 아이디어 최단거리를 구하는 문제입니다. 최단 거리 문제를 풀기 위해서는 bfs를 사용해야 합니다. bfs는 한 node에서 갈 수 있는 모든 node를 방문하고 다음 node를 방문합니다. 따라서 거리를 저장하면서 node를 순차적으로 방문하면 최단거리를 구할 수 있습니다. 최단 거리를 저장하는 방법은 아래 3가지 방...

1743번: 음식물 피하기 문제 풀이 아이디어 코드 stack을 사용해서 dfs 구현하는 방법 이 문제는 특이하게 dfs를 수행할 때 방문하는 node의 숫자를 세야합니다. 따라서 stack을 사용하는 방법이 좀 더 직관적으로 이해하기 쉽습니다. 재귀함수를 이용해서 구현한 dfs로 문제를 푸는 방법 직관적으로 이해하기 쉽지않은 방법이지만 dfs를...

2667번: 단지번호붙이기 풀이 코드 아래 dfs에 대한 자세한 설명은 이 포스팅을 참고해주세요.

10026번: 적록색약 문제 풀이 아이디어 코드

3055번: 탈출 고슴도치의 queue만 사용하는 방법 문제 풀이 아이디어 최단 거리 문제이기 때문에 bfs를 사용해야 합니다. 하지만 1초 마다 지도의 상황이 바뀌므로 (물의 이동) bfs 도중에 1초가 지나면 지도를 업데이트한 후 bfs를 시행해야 합니다. queue에 위치를 넣을 때 시간을 같이 저장하고 pop 하다가 시간이 1초 지났다면 지도를...

7562번: 나이트의 이동 문제 풀이 아이디어 동서남북 대신 8방향을 탐색을 한다는 점을 제외하면 기존의 bfs로 최단경로 찾기와 동일한 원리입니다. 코드

1697번: 숨바꼭질 문제 풀이 아이디어 코드

9019번: DSLR 문제 풀이 아이디어 코드 참고한 블로그 🙏 백준 9019번 DSLR - 스위프트(Swift) 시간초과 해결

9095번: 1, 2, 3 더하기 문제 풀이 아이디어 점화식을 찾으면 쉽게 풀 수 있는 DP 문제입니다. 점화식은 아래와 같습니다. 코드

16397번: 탈출 문제 풀이 아이디어 코드 추가 코드 버튼 B 함수를 구현할 때 숫자를 String의 Array로 바꾸어서 처리할 수도 있습니다. (더 직관적이지만👍 속도는 느립니다👎) 입력을 받을 때 아래처럼 튜플 형태로 받을 수도 있습니다.

2748번: 피보나치 수 2 동적계획법 (Dynamic Programming) 피보나치 수열을 구하는 문제는 동적계획법으로 풀 수 있는 대표적인 문제입니다. 동적계획법은 작게 쪼개서 작은 문제의 답을 구하고 그 답을 바탕으로 더 큰 문제의 답을 구해가는 문제해결법입니다. 메모이제이션 작은 부분의 답을 구했으면 그 답을 메모리에 저장하고 더 큰 문제의...

2193번: 이친수 방법 1 문제 풀이 아이디어 이친수를 전체 하나로 보면 규칙성을 구하는 것이 쉽지 않습니다. 하지만 이친수의 특성을 생각해보면 0으로 끝나는 것과 1로 끝나는 것으로 나눌 수 있습니다. 즉 n 자리의 이친수를 구하기 위해 아래 2가지 방법을 사용할 수 있습니다. 1로 끝나는 n의 자리 이친수는 n - 2 자리의 이친수에 01을 ...

11051번: 이항 계수 2 이항 계수 - 위키백과, 우리 모두의 백과사전 이항계수의 점화식 반복문으로 DP 구현하기 초기 값 (1)을 미리 넣지 않고 아래처럼 반복문 안에서 넣을 수도 있습니다. 재귀함수로 DP 구현하기

11726번: 2×n 타일링 문제 풀이 아이디어 2xn의 직사각형을 만드는 방법은 2x(n - 1)의 직사각형에 1 x 2 타일을 하나 붙이는 방법과 2x(n - 2)의 직사각형에 2 x 1 타일 2개로 정사각형을 만들어 붙이는 방법이 있습니다. 따라서 점화식은 f(n) = f(n - 2) + f(n - 1)로 피보나치 수열과 동일합니다. 코드 ...

1904번: 01타일 문제 풀이 아이디어 길이가 N인 이진수열을 만들기 위해서는 길이가 N - 2인 이진수열에 “00” 붙이거나 길이가 N - 1인 이진수열에 “1”을 붙이는 방법이 있습니다. 따라서 점화식은 f(n) = f(n - 2) + f(n - 1)로 피보나치 수열과 동일합니다. 코드

11048번: 이동하기 BFS로 풀기 문제 풀이 아이디어 bfs로 완전 탐색을 해서 풀 수 있습니다. 큐에 저장할 때 지금까지 얻은 사탕의 수를 함께 저장합시다. 코드 결과 이 코드는 모든 예제는 통과했으나 메모리 초과로 실제 채점은 통과하지 못합니다. D

1003번: 피보나치 함수 문제 풀이 아이디어 코드 반복문을 사용한 방법 반복문을 사용해서 N의 최댓값인 40까지 일단 모든 값을 구해두고 출력만 하는 방법입니다. 재귀함수를 활용한 방법

11727번: 2×n 타일링 2 문제 풀이 아이디어 f(n)을 만드는 방법은 f(n - 2)에 (2 x 1)를 2개 붙인 정사각형 (2 x 2)의 정사각형을 붙이는 방법과 f(n - 1)에 (1 x 2)의 직사각형을 붙이는 방법이 있습니다. 따라서 점화식은 f(n) = f(n - 2) * 2 + f(n - 1)이 됩니다. 코드

9461번: 파도반 수열 문제풀이 아이디어 코드

1010번: 다리 놓기 문제 풀이 아이디어 다리는 겹치면 안된다는 특성이 있기 때문에 서쪽에 N에 M개의 사이트가 있을 때 일단 동쪽에 N개의 사이트를 정하면 N개의 각각 동쪽 사이트에 연결할 서쪽 사이트는 무조건 정해져있습니다. (서쪽 1번 사이트부터 동쪽의 1번 사이트와 연결) 따라서 이 문제는 동쪽의 N개의 사이트를 고르는 문제로 바뀌게 됩니...

1932번: 정수 삼각형 문제 풀이 아이디어 코드 Tip 합을 구하는 것이기 때문에 갈 수 없는 길을 예외 처리하지 않고 그냥 0을 더하면 됩니다. 이 때문에 초기값을 따로 넣지 않아도 자동적으로 초기값 + max(0, 0)이 되어서 자동적으로 초기값이 설정되었습니다.

2293번: 동전 1 문제 풀이 아이디어 처음에 푼 코드 코드 틀린 이유 아래 화면은 i를 순서대로 3가지 동전을 순환하면서 채웠을 때 1 ~ 4까지의 경우의 수를 모두 적은 것입니다. 이렇게 i를 순서대로 채우는 경우 동전을 더하는 순서가 달라지면 다른 경우로 중복 계산이 됩니다. 마치 dfs 완전 탐색과 같은 원리입니다. 올바른 풀이 코드...

9184번: 신나는 함수 실행 문제 풀이 아이디어 그냥 재귀함수만 구현하면 엄청나게 많은 함수를 중복으로 실행하므로 콜스택이 남아있지 않을 것입니다. 따라서 동적계획법을 활용해서 이미 구한 함수의 값은 3차원 배열의 cache에 저장해둡시다. 문제 자체에 모든 조건과 점화식이 있습니다. 함수를 구현하는 것 자체는 어렵지 않습니다. 코드

14697번: 방 배정하기 문제 해결 아이디어 N명을 남는 침대 없이 방을 배정하기 위해서는 N - A 혹은 N - B 혹은 N - C 명을 침대 없이 방을 배정할 수 있어야 합니다. 코드

2493번: 탑 문제 풀이 무대포 완전 탐색 (🚫 시간 초과) 처음으로 그냥 아무 생각없이 아래와 같이 구현할 수 도 있습니다. 정직하게(?) 각각의 탑 마다 레이저가 닿는 탑을 완전탐색으로 구하는 방법이죠. 하지만 이 문제의 N은 최대 500,000입니다. 반면에 아래 알고리즘은 O(N^2)이죠. 무조건 시간초과가 납니다. O(N)의 방법을 찾아...

9625번: BABBA 문제 풀이 아이디어 코드

10211번: Maximum Subarray 방법 1 문제풀이 아이디어 코드 방법 1의 단점 O(N^2)의 시간복잡도를 가진다. 방법 2: 시간 복잡도 O(N)으로 개선 문제 풀이 아이디어 코드

1389번: 케빈 베이컨의 6단계 법칙 문제 풀이 아이디어 어떤 유저에서 다른 유저까지 가는 단계 = 어떤 유저에서 다른 유저까지 가는 최단거리 최단 거리 문제는 bfs를 활용해서 풉니다. 각각의 유저마다 다른 모든 유저까지의 최단거리를 bfs로 구해서 다 더하면 됩니다. 코드

14888번: 연산자 끼워넣기 문제 풀이 아이디어 모든 경우의 수를 따져서 완전 탐색해야 합니다. 순열 혹은 dfs를 사용하면 됩니다. 대표적인 dfs 문제인 동서남북 이동 문제와 결국 동일한 구조입니다. 동서남북 문제처럼 연산자도 배열에 넣어두고 사용하면 코드가 보기 좋아집니다. 코드

2512번: 예산 문제 풀이 아이디어 완전탐색을 해도 답을 구할 수 있습니다. 시간복잡도: O(n) 하지만 이진탐색을 활용하면 더 빠르게 구할 수 있습니다. 시간복잡도: O(logn) 이진탐색을 활용해서 조건에 만족하는 최댓값 (혹은 최솟값)을 찾는 것을 파라메트릭 서치라고 합니다. 어떤 예산이 “총 예산 조건"을 만족하는 "최댓값...

2840번: 행운의 바퀴 문제 풀이 아이디어 코드

1107번: 리모컨 틀린 접근 1: bfs 채널을 바꾸는데 드는 최소 버튼 조작 수를 구하는 것이므로 당연히 최단거리 문제라고 생각을 했습니다. 그래서 아래처럼 버튼 하나하나 누를 때 마다 하나의 경우의 수를 만들어서 queue에 넣고 bfs로 최단거리를 구하고자 했습니다. 하지만 절대로 최단거리가 될 수 없는 불필요한 너무나 많은 경우의 수를 탐색하...

1205번: 등수 구하기 문제 풀이 아이디어 코드

2902번: KMP는 왜 KMP일까? 문제 풀이 아이디어 코드

1026번: 보물 문제 풀이 아이디어 어차피 A와 B의 숫자를 하나씩 짝 짓는 문제이기 때문에 B의 순서를 변경할 수 없다고 해서 B를 그대로 두고 문제를 풀 필요는 없습니다. S를 가장 작게 만들기 위해서는 A의 가장 큰 숫자를 B의 가장 작은 숫자와 짝지어서 곱하면 됩니다. 따라서 A를 오름차순으로 B를 내림차순으로 정렬해서 S를 구합시다. 코드...

2607번: 비슷한 단어 문제 풀이 아이디어 비슷한 단어의 경우 아래 3가지 케이스가 있습니다. 문자열의 길이도 동일하고 동일한 알파벳들을 사용하는 경우 문자열의 길이가 동일하고 1개의 알파벳만 서로 다른 경우 문자열의 길이가 1만큼 차이나지만 하나의 알파벳을 제외하면 나머지는 동일한 경우 3개의 케이스를 판별할 수 있는 함수를 구현해서 풀면 됩니다...

2167번: 2차원 배열의 합 이중 반복문으로 풀기 문제 풀이 아이디어 단순하게 모든 case의 입력을 받아 바로바로 이중 반복문을 통해 더해서 문제를 푸는 방식입니다. 아주 간단한 방법이지만 🚫 시간 초과를 받을 가능성이 큽니다. 코드 DP로 풀기 문제 풀이 아이디어 이 문제의 특징 중에 하나는 반복해서 이차원 배열의 합을 구하고 있다는 것...

14501번: 퇴사 문제 풀이 아이디어 보통 DP로 문제 해결을 할 때는 i가 작은 것 부터 해결하곤 하는데요. 이번 문제는 독특하게 i를 큰 수부터 구합니다. DP의 경우 점화식을 구할 때 그 이전까지는 어떻게 구했든지 관계 없이 i와 i + 1를 구하는 관계에만 집중해야 합니다. 하지만 이 문제를 앞에서 부터 접근할 경우 i까지는 퇴사날이 지나서 끝...

2920번: 음계 문제 풀이 아이디어 완전탐색을 통해 풉니다. N이 8이기 때문에 시간복잡도 문제는 고려하지 않아도 되고 알고리즘 자체도 O(N)입니다. 코드

2163번: 초콜릿 자르기 문제 풀이 아이디어 N * M 크기의 초콜릿을 자를 때 뭔가 중간부터 잘라야 더 빠르게 자를 것 같지만 그냥 어떻게 자르던지 간에 같은 횟수를 가집니다. 그렇다면 직관적으로 구하기 쉽게 세로 크기가 1 짜리 초콜릿으로 자르고 다시 그 초콜릿을 1 * 1인 초콜릿으로 쪼개 봅니다. 먼저 N * M의 초콜릿을 1 * M의 초콜릿...

2804번: 크로스워드 만들기 문제 풀이 아이디어 코드

1057번: 토너먼트 문제풀이 아이디어 현재 번호가 n번이라면 다음 번호는 (n + 1) / 2가 됩니다. 다음 번호가 같다면 이번에 대결합니다. 서로 대결하지 않는 경우는 -1을 출력하라고 되어있지만 함정(?)입니다. 토너먼트의 경우는 계속 이기고 올라간다면 무조건 대결할 수 밖에 없습니다. 코드

1015번: 수열 정렬 문제 풀이 아이디어 코드

1748번: 수 이어 쓰기 1 문제 풀이 아이디어 코드

5567번: 결혼식 문제 풀이 아이디어 코드

4963번: 섬의 개수 문제 풀이 아이디어 연결된 요소를 모두 찾아야 하는 전형적인 dfs 문제입니다. 주어진 조건에 의하면 8방향으로 이동할 수 있는 연결된 땅은 모두 하나의 섬으로 칩니다. 지도를 완전탐색하면서 땅이 나올 때마다 dfs를 통해서 연결된 땅을 모두 탐색해서 섬을 찾으면 됩니다. 코드

14889번: 스타트와 링크 dfs로 풀기 문제 풀이 아이디어 이 문제의 경우 모든 팀의 경우의 수를 따져야 합니다. 따라서 모든 경우의 수를 따질 수 있는 dfs를 통해서 풀어봅니다. 코드 조합으로 풀기 문제 풀이 아이디어 모든 팀의 경우의 수를 구할 때 조합을 사용하면 좀 더 직관적으로 풀 수 있습니다. (다만 코드가 좀 깁니다.) 짤 수...

2606번: 바이러스 문제 풀이 아이디어 연결된 node를 방문하며 세는 전형적인 dfs 문제입니다. 연결된 컴퓨터들을 인접리스트에 저장하고 1번 컴퓨터에서 시작하는 dfs를 실행합니다. 코드 전역에 cnt를 두고 갯수를 세기 dfs 내부에 cnt를 두고 갯수를 세기

1213번: 팰린드롬 만들기 dfs로 풀기 (시간초과 😭) 문제 풀이 아이디어 브루탈포스로 푸는 방법입니다. 주어진 문자열로 만들 수 있는 모든 문자열을 만들어보면서 그 중에 회문을 찾는 방식입니다. 하지만 이 방식은 테스트케이스는 통과할 수 있지만 채점을 해보면 시간 초과가 나옵니다. 코드 dictionary로 풀기 문제 풀이 아이디어 알...

10819번: 차이를 최대로 문제 풀이 아이디어 수열의 최대 길이는 8로 모든 경우를 구해서 계산해도 시간초과가 나오지 않을 크기 입니다. 문제를 처음 보면 순열을 구해서 계산하는 방법을 떠올릴 수도 있지만 Swift로 순열을 구하는 것은 번거로운 일이므로 간단하게 dfs를 통해서 모든 경우의 수를 탐색하는 방법으로 해봅시다. 코드

1189번: 컴백홈 문제 풀이 아이디어 이 문제는 전형적인 bfs 문제처럼 생겼습니다. 하지만 어디에도 최단거리라는 조건은 없습니다. 단지 왔던 길을 다시 가지 않고 거리가 K인 길만 찾으면 됩니다. 따라서 최단거리에 연연하지 않고 모든 목적지까지 가는 경우의 수를 따져서 거리가 K인 경우만 찾으면 됩니다. 즉 dfs나 bfs에 관계 없이 어떤 완전...

4949번: 균형잡힌 세상 문제 풀이 아이디어 기본적인 stack 문제로 여는 괄호와 닫는 괄호를 짝짓는 문제입니다. 이 포스팅(https://velog.io/@comdongsam/Swift-%EB%B0%B1%EC%A4%80-9012-%EA%B4%84%ED%98%B8))을 참고해주세요. 다만 이 경우의 경우 괄호가 소괄호와 대괄호로 두 가지입니다. 닫...

2504번: 괄호의 값 문제 풀이 아이디어 괄호의 짝을 맞추는 문제로 전형적인 stack을 활용해서 풀어야 하는 문제입니다. 하지만 이 문제의 복잡한 점은 stack에 괄호만 들어가는 것이 아니라 괄호의 값을 넣어서 계산해주어야 한다는 것인데요. 여는 괄호를 push하고 닫는 괄호일 때 pop해서 짝을 맞추어보는 것은 동일하지만 중간에 짝을 이룰 때마다...

10773번: 제로 문제 풀이 아이디어 스택을 활용해서 푸는 문제입니다. 입력이 0이면 스택에서 pop하고 0이 아니라면 그 수를 push해주면 됩니다. 입력이 0일 때 항상 지울 수 있다고 했으므로 예외처리는 하지 않아도 됩니다. 코드

13458번: 시험 감독 문제 풀이 아이디어 계산 자체는 간단한 문제입니다. 하지만 한명의 주감독관이 모두 감독을 할 수 있을 때 1을 출력하는 경우와 주감독관이 감독하고 남은 학생들(A[i] - B)이 부감독관이 감독할 수 있는 수 (C)로 나누어 떨어지지 않는 경우 + 1을 해주는 2가지 예외를 신경 써주어야 합니다. 코드

12789번: 도키도키 간식드리미 문제 풀이 아이디어 원래 줄과 추가 대기열을 통해서 간식을 받을 순서에 따라 간식을 줘야하는 문제입니다. 추가 대기열을 사용해서 간식을 제대로 줄 수 없다면 실패입니다. 추가 대기열은 입구과 출구가 한쪽 밖에 없으므로 stack 자료구조를 사용하면 됩니다. 줄 맨 앞에 서 있는 사람이 현재 순서라면 간식을 주고 번호표...

2669번: 직사각형 네개의 합집합의 면적 구하기 문제 풀이 아이디어 입력으로 들어온 직사각형 4개를 좌표에 옮기면 되는 간단한 문제입니다. 좌표평면을 이차원 배열로 구현한 뒤 각 직사각형이 차지하는 영역을 좌표에 표시합니다. 이렇게 하면 겹치는 영역을 복잡하게 계산하지 않고 이차원 배열 전체를 순회하면서 표시된 영역의 갯수만 세면 됩니다. 코드

6603번: 로또 문제 풀이 아이디어 조합의 개념을 적용해서 풀면 되는 문제입니다. 파이썬 같이 내부적으로 combination을 지원하는 언어라면 훨씬 쉽게 풀 수 있겠지만 Swift는 지원하지 않기에 직접 구현하거나 다른 경우의 수를 다루는 알고리즘을 사용해서 풀어야 합니다. 여기서는 dfs를 활용해서 풀어보도록 하겠습니다. dfs는 완전탐색 알...

10971번: 외판원 순회 2 문제 풀이 아이디어 모든 도시를 방문해야 하므로 완전탐색으로 접근해야 합니다. dfs를 활용해서 풀어보도록 하겠습니다. 하지만 정말로 모든 경우를 탐색하게 되는 경우 시간 초과가 나게 됩니다. 따라서 백트래킹을 활용해서 정답이 될 수 없는 경로는 중간에 제거해주어야 합니다. 제거해야 하는 경로의 조건은 아래와 같습니다. ...

1063번: 킹 문제 풀이 아이디어 특정한 알고리즘을 사용하는 것이 아닌 문제에서 나온 조건 그대로 코딩하면 되는 구현 문제입니다. 알파벳으로 좌표를 표현한 경우 아스키 코드를 사용하면 정수로 바꾸어 활용할 수 있습니다. 코드

1080번: 행렬 문제 풀이 아이디어 브루탈 포스? 아마 맨 처음에 문제를 보면 dfs 같은 완전탐색 알고리즘을 통해서 모든 경우의 수를 계산해야하는 것이 아닌가라는 생각이 들 수 있습니다. 하지만 N과 M이 최대 50이고 이렇게 되면 행렬의 원소의 사이즈는 최대 2500이 됩니다. 그리고 행렬의 원소 마다 연산을 실행하거나 안하는 경우의 수까지 고려...

11403번: 경로 찾기 문제 풀이 아이디어 기본적으로 dfs를 통해서 출발점에서 방문할 수 있는 모든 node를 찾아주면 됩니다. 주의! 이 문제는 dfs를 재귀함수로 구현할 때 아래처럼 방문체크를 하고 재귀 함수를 구현하고 다시 방문체크를 취소하는 경우에는 “🚫 시간초과"가 나게 됩니다. 이 문제는 출발점을 기준으로 다른 node에 갈 수 있...

2872번: 우리집엔 도서관이 있어 문제 풀이 아이디어 처음에는 맨 위에만 책을 올릴 수 있다고 했기 때문에 stack이라고 생각했습니다. 하지만 맨 위에서만 pop할 수 있는 stack과는 달리 이 문제에서는 책을 어느 위치에서 관계 없이 어느 위치에서나 뺄 수 있습니다. 물론 시뮬레이션을 통해서 구현할 수도 있을 것입니다. 직접 책들을 Array에...

6236번: 용돈 관리 문제 풀이 아이디어 특정 범위에서 하나의 값을 찾는 문제를 연속된 O / X 문제의 개념으로 접근해서 푸는 파라메트릭 서치를 사용하는 문제입니다. 파라메트릭 서치는 이진 탐색을 활용해서 구현하면 됩니다. 파라메트릭 서치를 구현할 때 대부분 이진탐색의 시작과 끝으로 설정할만한 값이 문제에서 주어지지 않는데요. 이 값들을 잘 설정해...

2343번: 기타 레슨 문제 풀이 아이디어 특정 범위 내에서 최적화된 값을 찾는 문제입니다. 이런 문제는 이진탐색을 활용한 파라메트릭 서치를 사용해서 풀 수 있습니다. 특정 값이 조건에 만족하는지 알 수 있는 함수를 구현한 뒤 이진탐색과 이 함수를 활용해서 최적화된 값을 찾아내면 됩니다. 코드

1654번: 랜선 자르기 문제 풀이 아이디어 전형적인 파라메트릭 서치 문제입니다. 어떤 길이로 만들 수 있는 최대 랜선의 갯수를 구하는 함수를 만들고 그 함수와 이진탐색을 활용해서 파라메트릭 서치를 구현합시다. 코드

15649번: N과 M (1) 문제 풀이 아이디어 모든 경우의 수를 구해야 하는 문제입니다. 순열을 구하는 것과 동일합니다. 이런 문제는 dfs를 재귀함수로 구현하면 쉽게 풀 수 있습니다. 방문체크, 탈출조건 그리고 출력 양식에 유의해서 문제를 풉니다. 코드

15650번: N과 M (2) 문제 풀이 아이디어 모든 경우의 수를 찾을 때는 역시 재귀함수를 통해 구현하는 dfs를 사용합니다. 중복 없이 + 오름 차순의 조건에 주의해서 코드를 짭니다. 오름차순으로 출력하기 위해서는 반복문 안에서 dfs(i + 1)로 탐색하면 됩니다. 이러면 자연스럽게 중복도 없앨 수 있습니다. 다만 now가 N + 1이 될 수...

15651번: N과 M (3) 문제 풀이 아이디어 기본적으로 모든 경우의 수를 구하는 것은 재귀함수를 이용해서 dfs를 구현해야 합니다. 다만 주어진 조건을 잘 봐야 합니다. 이번 N과 M의 경우 중복을 허용합니다. 따라서 중복 체크 없이 dfs를 수행하면 됩니다. 코드

15652번: N과 M (4) 문제 풀이 아이디어 dfs를 통해 모든 경우의 수를 찾는 N과 M 문제입니다. 이 문제는 비내림차순이라는 조건이 있는데요. now ~ N을 순환하면 자연스럽게 비내림차순을 구현할 수 있습니다. 코드

15654번: N과 M (5) 문제 풀이 아이디어 또 다른 N과 M 문제입니다. 이번에는 그냥 1 ~ N 까지 증가하는 정수로 수열을 만드는 것이 아니라 주어진 배열로 만들어야 합니다. index를 사용하면 되니까 큰 문제는 없습니다. 숫자가 중복되면 안되니까 방문배열을 활용합시다. 그리고 수열을 사전순으로 출력해야 하니까 입력 받은 배열을 정렬하는...

15655번: N과 M (6) 문제 풀이 아이디어 고른 수열이 오름차순이어야 하므로 입력 받은 배열을 정렬합니다. 그리고 반복문 안에서 dfs에 넘길 때 dfs(i + 1)로 해주어야 중복 없이 오름차순의 수열을 만들 수 있습니다. 코드

15656번: N과 M (7) 문제 풀이 아이디어 모든 수열을 구하는 N과 M 문제입니다. 완전탐색을 위한 dfs를 재귀함수로 구현하면 됩니다. 중복이 가능하므로 중복을 체크하는 배열을 사용하지 않고 dfs를 돌리면 됩니다. 다만 입력이 오름차순이라는 보장이 없으므로 사전 순으로 출력하기 위해서 오름차순으로 정렬합시다. 코드 🚫  Print와 시...

15657번: N과 M (8) 문제 풀이 아이디어 중복은 가능하지만 비오름차순의 조건이 있습니다. 이런 경우 입력 받은 숫자들을 오름차순으로 정렬하고 현재 index 부터 순회하면 자동으로 비오름차순으로 수열을 만들 수 있습니다. 중복이 가능하므로 dfs(i + 1)이 아니라 dfs(i)입니다. 코드

15663번: N과 M (9) 문제 풀이 아이디어 N과 M이 숫자가 올라갈 수록 조금씩 복잡해지고 있습니다. 고지가 멀지 않았네요. 이번 문제는 중복체크를 구현해야 합니다. 다양한 중복체크 방법이 있겠지만 저는 Set을 활용해서 중복체크를 해보겠습니다. 코드

15664번: N과 M (10) 문제풀이 아이디어 비내림차순을 적용해야 합니다. 입력된 숫자들을 정렬하고 dfs(i + 1)을 하면 자연스럽게 중복이 없는 비내림차순을 적용할 수 있습니다. 코드

15665번: N과 M (11) 문제 풀이 아이디어 중복을 허용하므로 중복체크 배열 없이 dfs를 수행하면 됩니다. 다만 수열 자체의 중복은 체크해주어야 합니다. 코드

15666번: N과 M (12) 문제 풀이 아이디어 사용한 수를 또 사용해도 되므로 중복 체크를 사용할 필요가 없습니다. 입력 array를 정렬하고 index ~ N을 완전탐색하면 자연스럽게 비오름차순을 구현할 수 있습니다. 코드

코딩테스트 연습 - 최소직사각형 문제 풀이 아이디어 지갑을 최소한의 크기로 만들려면 가로와 세로 길이를 최대한 작게 만들어야 합니다. 하지만 모든 명함을 수납할 수 있어야 하므로 명함의 가로, 세로 길이의 최댓값을 지갑의 크기로 해야 합니다. 하지만 명함을 돌릴 수 있으므로 지갑의 크기를 최소로 만들기 위해서는 명함을 돌려서 가로, 세로 중에 긴 변을...

코딩테스트 연습 - 체육복 문제 풀이 아이디어 전체 아이디어: 그리디 알고리즘 체육복을 빌릴 수 있는 사람이 번호가 -1 혹은 +1인 사람이기 때문에 체육복을 빌려야하는 사람 입장에서는 빌릴 수 있는 대상이 정해져있습니다. 체육복을 잃어버린 사람이 오름차순으로 정렬되어 있다고 할 때 n번 사람은 체육복을 n - 1 혹은 n + 1에게 빌릴 수 있습니...

코딩테스트 연습 - K번째수 문제 풀이 아이디어 주어진 연산을 그대로 코드로 옮기기만 하면 되는 문제입니다. Array를 slice하는 방법을 알고 있어야 합니다. subscript와 range를 조합해서 사용하면 됩니다. 코드

코딩테스트 연습 - 올바른 괄호 문제 풀이 아이디어 괄호 문제 (뭔가 짝을 맞추어야 하는 모든 문제)는 전형적인 Stack 문제입니다. 여는 괄호가 들어오면 push, 닫는 괄호가 들어오면 pop이 원칙입니다. false를 리턴해야 하는 상황은 아래 3가지 입니다. pop해야 하는데 stack이 비었을 때 문자열을 모두 순회했는데 stack이 비어있지...

코딩테스트 연습 - 위장 조합으로 풀기 문제 풀이 아이디어 들어오는 입력을 보면 [옷, 카테고리]의 배열이라고 볼 수 있습니다. 우리는 이 입력을 [카테고리:카테고리에 속한 옷의 갯수]의 형태로 바꾸어 주어야 문제를 해결할 수 있습니다. 이렇게 바꾼 이후에 조합을 통해서 1개의 카테고리에서만 옷을 고른 경우 ~ 모든 카테고리에서 옷을 고른 경우의 각...

코딩테스트 연습 - 타겟 넘버 문제 풀이 아이디어 완전탐색을 통해서 모든 경우의 수를 찾아야 합니다. dfs로 구현할 수 있습니다. 다만 주의할 점은 dfs를 할 때 기계적으로 반복문을 사용하려는 경향이 있습니다. (저만 그런가요;;;) 하지만 이 문제의 경우 숫자의 순서를 그대로 유지해야 합니다. 따라서 반복문 없이 그냥 다음 index만 dfs를 ...

코딩테스트 연습 - 모의고사 문제 풀이 아이디어 주어진 찍는 패턴과 입력을 모두 일일히 비교해주어야 합니다. 풀이 방법은 간단합니다. 다만 찍는 패턴이 반복되므로 답을 체크할 때 마지막 index가 지나면 다시 0으로 올 수 있도록 나머지 연산을 활용해주는 것에 유의해야 합니다! 코드 우리가 생각한대로 그대로 코드로 옮기기만 하면 됩니다. 코드 ...

코딩테스트 연습 - 기능개발 문제 풀이 아이디어 작업이 완료가 되었다고 하더라도 앞에 작업이 완료가 되지 않으면 배포가 되지 않는 조건이 있습니다. 따라서 선입선출의 자료형인 Queue를 활용해서 풀어봅니다. 일반적인 array를 사용해도 문제는 풀리지만 array에서 element를 삭제할 때 시간복잡도는 O(N)입니다. 반면에 Queue에서 elem...

코딩테스트 연습 - 입국심사 문제 풀이 아이디어 저만의 습관인지는 모르겠지만 저는 문제를 읽자마자 문제에 나온 그대로 코드로 옮기고자 하는 버릇이 있습니다. 이 문제 역시 예시가 주어진대로 시간이 흐름에 따라 심사관이 한명한명 처리하는 것을 그대로 코드로 옮기는 것 (시뮬레이션)으로 문제를 풀려고 했었습니다. 하지만 문제를 풀 때는 더 효과적인 방법은...

코딩테스트 연습 - 조이스틱 🚫 처음 풀이 이 문제가 유형이 그리디로 분류되어 있어서 처음에는 그리디로 풀기 위해 노력을 했습니다. 일종의 시뮬레이션 코드를 만들어놓고 현재 cursor의 위치에서 가장 A가 아닌 글자로 이동하는 것을 반복하는 식으로 문제를 해결하려고 했습니다. 하지만 일부 테스트 케이스만 통과할 수 있었습니다. 참고한 블로그 🙏 ...

코딩테스트 연습 - 네트워크 문제 풀이 아이디어 전형적인 dfs 문제입니다. 모든 node를 탐색하면서 아직 방문하지 않은 node가 있으면 dfs를 통해 연결된 node들을 전부 방문 처리해주면 됩니다. 입력이 행렬 형태로 주어집니다. 코드

코딩테스트 연습 - 단어 변환 문제 풀이 아이디어 주어진 배열에서 begin에서 변형할 수 있는 단어를 찾아서 변형하고 다시 변형된 단어에서 변형할 수 있는 단어를 찾아서 변형하는 과정을 반복해야 합니다. 이 과정에서 특별한 패턴이 없고 배열 안의 단어들을 전부 일일히 대조해야 하므로 완전 탐색 알고리즘을 사용해야 합니다. 완전 탐색을 통해서 begi...

코딩테스트 연습 - N으로 표현 문제 해결 아이디어 이 문제를 DP로 접근할 때 f(i)를 무엇으로 정의할 때부터 정의해야 합니다. 🤔 f(i) = “i를 만들 수 있는 최소의 N의 갯수” 맨 처음 떠올리는 정의는 위의 정의일 것입니다. 하지만 위 처럼 f(i)를 정의하면 점화식을 만들기가 쉽지 않습니다. 일단 N으로 사칙연산을 할 수 있기 때문...

코딩테스트 연습 - 베스트앨범 문제 풀이 아이디어 문제에서 시키는 그대로 구현하면 되는 문제입니다. 1번 조건인 “속한 노래가 많이 재생된 장르를 먼저 수록합니다.”를 구현하기 위해서 Dictionary를 사용해야 합니다. 장르의 이름은 String으로 제시되어 있고 재생 횟수는 Int이므로 [String : Int]를 사용하면 됩니다. 나머지 과정...

코딩테스트 연습 - 소수 찾기 문제 풀이 아이디어 완전탐색 알고리즘 (dfs)를 통해서 주어진 숫자로 만들 수 있는 모든 경우의 수를 탐색하고 해당 숫자가 소수인지 판정해서 소수이면 숫자를 세면 됩니다. 카드를 일부만 사용할 수도 있으므로 별도의 탈출 조건 없이 dfs를 통해 탐색할 때 마다 모든 숫자가 소수인지 아닌지 판정을 합니다. “011”과 ...

코딩테스트 연습 - 카펫 문제 풀이 아이디어 완전탐색 문제입니다. brown은 (너비 + 높이) * 2 - 4 이므로 높이를 알면 너비를 구할 수 있습니다. 높이가 너비보다 작으므로 높이를 1부터 탐색합시다. 높이가 정해지면 brown을 통해 너비를 구합니다. 너비 = (brown + 4) / 2 - 높이 입니다. 높이와 너비가 나오면 넓이를 구할...

코딩테스트 연습 - 피로도 문제 풀이 아이디어 정렬? 처음에 문제를 봤을 때는 정렬을 통해서 던전을 최소 필요 피로도 순 혹은 소모 피로도 순으로 정렬하면 되지 않을까라는 생각을 했습니다. 하지만 두 가지 변수 중에 한 가지를 기준으로 정렬해도 최적의 경로를 구할 수는 없습니다. 완전탐색! 그렇다면 방법은 하나 뿐입니다. dfs를 통해서 모든 경로...

참고한 블로그 (Swift) 백준 1743 음식물 피하기 제가 만든 포스팅입니다ㅎㅎ 아래에서 사용하는 연결된 node 갯수를 세는 dfs에 대한 자세한 설명이 있습니다. 문제 풀이 아이디어 문제에서 시키는 대로 하면 됩니다. 주어진 wire를 완전탐색하면서 하나하나 끊어보고 dfs를 통해 두 전력망의 송전탑의 수를 세면 됩니다. 말은 쉬운데 구현은 ...

코딩테스트 연습 - 프린터 문제 풀이 아이디어 문제에서 주어진 프린터의 구조를 보면 맨 앞에 있는 문서부터 출력하는 것을 하지만 맨 앞의 문서가 최우선 중요도가 아니라면 프린터의 맨 뒤로 보냅니다. 즉 FIFO (First In First Out)의 자료구조인 Queue와 동일한 원리입니다. 따라서 해당 문제는 Queue로 구현해야 합니다. 하지만 Q...

코딩테스트 연습 - 큰 수 만들기 🚫  처음 접근법 문제 풀이 아이디어 저의 고질병(?)인 무조건 구현, 무조건 완전탐색으로 구현한 코드입니다. 물론 구현하면서도 Int ↔  String 연산도 엄청나게 많고 O(N * k) = O(N^2)의 시간복잡도를 가지고 있기 때문에 아마 안되겠지라고 생각하고 구현했고 실제로 안풀립니다😭 하지만 코드에 S...

코딩테스트 연습 - H-Index 문제 풀이 아이디어 전형적인 파라메트릭 서치 문제입니다. 파라메트릭 서치는 특정한 하나의 값을 찾는 문제를 연속된 O / X 문제로 바꾸어서 이진탐색을 통해 그 값을 찾아나가는 알고리즘입니다. 어떤 값은 범위가 주어지면 그 값을 찾는 범위를 절반씩 줄여가면서 최적의 값을 찾아나가는 과정입니다. 이 문제는 h-inde...

코딩테스트 연습 - 모음사전 문제 풀이 아이디어 사전이 진행되는 방식을 보면 딱 DFS가 떠오릅니다. 각 모음을 하나의 경로로 보면 “A” → “AAAAA”의 최대 깊이까지 경로 탐색을 하고 “AAAAE”로 최대 깊이에서 다음 경로를 탐색합니다. 그리고 나서 “AAAAX”를 모두 탐색하고 나서 “AAAE”부터 다시 탐색을 시작합니다. DFS, 즉 “깊이...

코딩테스트 연습 - 여행경로 문제 풀이 아이디어 전형적인 완전 탐색 문제로 보입니다. 하지만 기본에 풀었던 문제들과는 조금씩 다른 부분들이 있습니다. 모든 “공항"을 방문해야 하는 것이 아니라 모든 “티켓"을 사용해야 합니다. 따라서 방문 체크 배열이 아니라 티켓 사용 배열을 만들어서 체크해야 합니다. 알파벳 순으로 가장 앞선 경로를 찾아야 하므로 목...

코딩테스트 연습 - 사칙연산 문제 풀이 아이디어 처음에는 완전탐색을 통해 풀까도 생각했습니다만 아마 무조건 시간초과가 날 만한 사이즈의 문제입니다. DP를 활용해서 풀어보겠습니다. 최댓값과 최솟값 DP를 둘 다 만들어야! 점화식을 만들기 전에 주의할 점을 하나 언급하고 가겠습니다. 현재 우리가 구하고자 하는 값은 (0번째 수 ~ 마지막 수)를 연산한...

코딩테스트 연습 - 퍼즐 조각 채우기 문제 풀이 아이디어 많이 어려운 문제입니다… 저도 거의 1시간 30분 이상 걸린 것 같네요. (그 중에 한 사용한 블록 체크 위치를 잘못해서 1시간 잡아먹음…) 아래 3단계에 걸쳐서 문제를 풀어보겠습니다. 1. 퍼즐 찾기 일단 퍼즐 조각을 찾아야 합니다. 퍼즐 조각을 찾는 것이야 그냥 dfs를 사용하면 쉽게할 수...

코딩테스트 연습 - 징검다리 문제 풀이 아이디어 완전탐색? 문제만 딱 보면 바위 중에 n개를 뽑아서 제거하고 간격을 구하는 조합 문제로 풀면 딱 좋을 것 같습니다. 하지만 바위가 50,000개나 있습니다. 이거를 조합으로 풀면…. 100% 시간 초과입니다. 이분탐색 이 문제는 이분 탐색으로 풀어야 합니다. 파라메트릭 서치로 풀어야 하죠. 파라메트릭...

코딩테스트 연습 - 가장 먼 노드 문제 풀이 아이디어 최단 경로 == bfs 최단 경로를 구하는 문제는 bfs를 사용하면 됩니다. 인접 리스트를 활용해서 성능을 높이자! 입력으로 주어지는 edge를 사용해서 bfs를 하면 한 node에서 다른 node로 가는 간선을 찾기위해서 매번 O(N)의 탐색을 해야합니다. 인접리스트를 사용하면 O(1)로 성능...

코딩테스트 연습 - 순위 집합으로 풀기 처음에 플로이드 와샬 알고리즘을 모를 때 푼 방법입니다. 문제 풀이 아이디어 문제의 조건에 의하면 기존에 주어진 경기 결과를 통해서 나머지 경기 결과를 유추할 수 있습니다. a 선수가 b 선수를 이겼다면 b 선수가 이긴 선

코딩테스트 연습 - 디스크 컨트롤러 문제 풀이 아이디어: Heap 가장 적게 기다려야 한다! 작업이 걸리는 시간은 2가지 부분으로 나뉘어 있습니다. (요청 ~ 작업이 수행되기까지 대기하는 시간) + (작업을 수행하는 시간)입니다. 각각의 작업에서 작업을 실제 수행하는 시간은 fix 되어 있으니 우리가 조정할 수 있는 시간은 요청 ~ 작업이 수행되기까지...

코딩테스트 연습 - 이중우선순위큐 문제 풀이 아이디어 중간에 입력이 주어질 때마다 정렬을 해야 하는 문제이므로 힙으로 구현해야 하는 문제입니다. 다만 문제점이 힙은 최소힙 아니면 최대힙으로 정렬을 내림차순 혹은 오름차순 중에 하나로만 구현할 수 있는데 이 문제의 경우 최소, 최대 값을 오가면서 구해야 하는 문제입니다. 힙을 하나 사용하는 경우 일단 ...

코딩테스트 연습 - JadenCase 문자열 만들기 문제 풀이 아이디어 공백 문자가 여러개 간단하게 보이는 문제이지만 함정이 하나 있습니다. 입출력 예시에서는 드러나있지 않지만 공백 문자가 연속적으로 나올 수 있다는 점입니다. 따라서 아래 코드 처럼 단어 하나하나를 split으로 공백문자를 기준으로 나눈 다음에 join으로 다시 합치려고 하면 연속된 ...

코딩테스트 연습 - 오픈채팅방 문제풀이 아이디어 이 문제를 보면 중간에 바뀔 수 있는 닉네임을 계속 바꾸어가며 저장해야 합니다. 닉네임은 uid와 1:1로 연결되어 있으므로 Hash Table (dictionary)를 사용하면 O(1)로 접근 & 수정이 가능합니다. 닉네임을 Hash Table에 저장해야 하는 이벤트는 2가지입니다. 처음에 채팅방에 입...

문제 풀이 아이디어 규칙성을 찾아라? 처음에는 아래 처럼 쭉 써놓고 규칙성을 찾기 위해 노력해봤습니다만… 상당히 복잡하고 조건이 까다로워서 구현하기가 쉽지 않았습니다. dfs나 순열을 사용해볼까도 생각을 했습니다만 n이 최대 1,000,000입니다. 2진수로 변환하면 그 길이는 어마어마할 것입니다… 브루탈 포스! 해결책은 브루탈 포스였습니다. 다음 ...

코딩테스트 연습 - 최댓값과 최솟값 문제 풀이 아이디어 String을 [Int]로 바꾸는 방법만 알면 아주 쉬운 문제입니다. 코드를 참고해주세요. 코드

코딩테스트 연습 - 최솟값 만들기 문제 풀이 아이디어 곱셈은 큰수끼리 곱할 때 더욱 커지는 성질을 가지고 있습니다. 따라서 (A의 원소) * (B의 원소)를 구할 때 가장 작은 수끼리 곱한다면 당장의 그 곱셈의 결과는 최솟값이 되겠지만 남은 원소들을 곱해서 나온 값이 너무 커서 최종적으로 합했을 때 최솟값이 되지 않을 것입니다. 따라서 “(A의 원소)...

코딩테스트 연습 - 징검다리 건너기 문제 풀이 아이디어 stone 배열의 크기를 M이라고 하고 stone 배열 원소의 크기를 N이라고 하고 시간복잡도를 설명하겠습니다. 예시에 나온대로 순차적으로 탐색하면? 처음에는 예시에 나온대로 1명씩 다리를 건너면서 cnt

코딩테스트 연습 - 2개 이하로 다른 비트 🚫 Brutal Force 처음 풀이 처음에는 아래와 같이 브루탈 포스로 풀었습니다. fn을 n에서 부터 1씩 증가시켜 가면서 조건에 만족하는 fn을 찾는 것입니다. 하지만 이렇게 풀면 무조건 시간초과가 나게 되어있습니다. numbers의 길이가 최대 100,000이고 number의 최댓값은 무려 10의 1...

코딩테스트 연습 - 영어 끝말잇기 문제 풀이 아이디어 구현 문제입니다. 배열의 크기가 최대 100이므로 시간복잡도 걱정 없이 완전 탐색을 해도 관계 없습니다. 아래 3가지 케이스에 대해서 분기문으로 구현하면 됩니다. 앞에 이미 말한 단어를 말한 경우 앞에 말한 단어의 마지막 글자와 나중에 말한 단어의 첫 글자가 다른 경우 1, 2의 경우가 아닌 경우 ...

코딩테스트 연습 - 피보나치 수 문제풀이 아이디어 백준에서도 풀었던 문제를 만났습니다. 피보나치 수에 대한 자세한 내용은 이 포스팅을 참고해주세요! 이번 포스팅에서는 코드만 올리겠습니다! 동적계획법과 재귀함수를 조합하여 풀었습니다! 코드

코딩테스트 연습 - 괄호 변환 문제 풀이 아이디어 “이게 Level 2라고???”라는 생각이 들 정도로 문제가 길고 복잡합니다. 문제 조차도 한 번에 이해하기가 어려웠어요. 하지만 하나하나 분리해서 구현해보면 복잡한 알고리즘은 없습니다. 어쩌면 단순한 구현에 불과한 문제인지도 모릅니다. 하나하나 구현해야 하는 부분을 쪼개는게 핵심이라고 생각합니다. 올...

코딩테스트 연습 - N개의 최소공배수 처음 풀이: 완전탐색 🚫 처음에는 완전탐색을 활용해서 arr의 최댓값에서 1씩 늘려가면서 arr 안에 모든 수와 나누어 떨어지는 가장 작은 수를 구했습니다. 문제를 풀기는 풀었지만 실행시간이 꽤 길게 걸리는 케이스들이 있었습니다. 사실 이 문제를 이렇게 푸는 것이 아니라 최대공약수와 최소공배수의 정의를 활용해야 ...

코딩테스트 연습 - 짝지어 제거하기 문제 풀이 아이디어 N이 최대 1,000,000 일단 문제에 나온 예시대로 구현한다면 매번 문자열을 완전탐색해야 하므로 O(N)의 시간복잡도가 필요합니다. 문자열을 Array로 바꿔서 구현한다면 element를 삭제하는데 O(N)의 시간복잡도가 필요합니다. 추가적으로 할 수 있을 때까지 짝지어 제거해야 하므로 O(N...

코딩테스트 연습 - 예상 대진표 문제 풀이 아이디어 백준에서 풀었던 동일한 문제를 이 포스팅에 정리한 적이 있는데요. 이번에도 같은 방법으로 풀어봤습니다. 다음 라운드에 부여받는 번호는 현재 번호가 홀수라면 1을 더하고 2로 나누어서 구하고 짝수라면 2로 그냥 2

코딩테스트 연습 - 점프와 순간 이동 Bottom-up 방식 (정확성✅ 효율성🚫) 문제 풀이 아이디어 문제의 조건에 의하면 순간이동은 비용이 들지 않으므로 최대한 순간이동을 활용해서 이동해야 합니다. n 위치에 도달하는 가장 효율적인 방법은 n / 2 위치에서 순간이동하는 것입니다. 만약 n이 홀수라면 (n - 1) / 2 위치에서 순간이동을 해서 ...

2887번: 행성 터널 문제 풀이 아이디어 크루스칼 알고리즘 행성과 행성 사이를 N - 1개의 간선 만을 사용해서 최소 비용으로 연결해야 합니다. 최소 신장 트리를 만드는 크루스칼 알고리즘을 사용해야 하는 것을 알 수 있습니다. 간선을 어떻게 구할 것인가? 모

3665번: 최종 순위 위상 정렬 알고리즘 (Topology Sort) 정의 이 문제를 위상정렬 알고리즘을 활용해서 풀어야 합니다. 위상 정렬 알고리즘은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘입니다. 위상 정

코딩테스트 연습 - 땅따먹기 🚫 dfs를 활용한 풀이 → 시간초과 처음에 생각한 풀이는 dfs를 활용해서 모든 경우의 수를 구해보는 것이었습니다. 물론 완전 탐색이기 때문에 테스트 케이스는 통과했습니다만 행이 최대 100,000이고 열이 4이므로 모든 경우를 따지

코딩테스트 연습 - 스킬트리 문제 풀이 아이디어 일단 문제를 읽자마자 편안한 것이 String인 skill의 길이는 최대 26, Array인 skill_trees의 길이는 최대 20에 불과합니다. 시간 초과에 대한 걱정 없이 원하는 대로 구현하면 되는 것이죠. Swift에서 문자열을 다루는 것은 파이썬 같은 언어에 비해서는 살짝 복잡하고 비용도 더 높...

코딩테스트 연습 - [1차] 캐시 문제 풀이 아이디어 LRU 문제에서 주어진대로 그대로 구현하면 되는 문제입니다. 다만 LRU(Least Recently Used)가 무엇인지 알고 있어야 하는데요. LRU는 OS를 배울 때 나온 페이지 교체의 기법 중에 하나로 캐

코딩테스트 연습 - 행렬의 곱셈 문제 풀이 아이디어 행렬의 곱셈의 원리를 코드로 구현해야 합니다. a x b 행렬과 b x c 행렬을 곱하는 경우 a x c 행렬이 됩니다. 그리고 각 첫 번째 행렬의 n행과 두 번째 행렬의 m열의 모든 원소를 순서대로 곱해서 더한 값이 결과 행렬의 n행 m열의 값이 됩니다. 코드로는 3중 반복문으로 구현할 수 있습니다...

코딩테스트 연습 - 괄호 회전하기 문제 풀이 아이디어 괄호의 짝을 맞추는 문제는 아주 전형적인 Stack을 활용한 문제입니다. 여는 괄호가 나왔을 때 stack에 push하고 닫는 괄호가 나오면 stack에서 pop해가면서 짝을 맞추면 됩니다. pop했을 때 stack이 비어 있거나 짝이 맞는 괄호가 아니라면 올바른 괄호 문자열이 아닙니다. 마지막에 s...

코딩테스트 연습 - 튜플 문제 풀이 아이디어 문제의 이름은 튜플이지만 사실 튜플과는 크게 관련이 없는 문제입니다.😅  문자열을 어떻게 다룰 것인가가 가장 메인입니다. 문자열을 숫자의 배열로 일단 문제를 풀기 위해서는 주어진 문자열을 통해서 집합을 n개 구해야 합니다. 즉 String을 [[Int]]로 변경해야 하는 것이죠. 단계별로 해보도록 하겠습...

코딩테스트 연습 - n^2 배열 자르기 문제 풀이 아이디어 함정… 여러 개의 코테 문제를 풀어봤지만 문제에서 애니메이션까지 보여주면서 친절하게 설명하는 경우는 처음 봤습니다. 애니메이션에 나온대로 2차원 배열을 구현하고 각 행을 이어붙여서 1차원 배열을 만들고 subscript를 활용해서 left ~ right까지 잘라서 리턴하면 해결입니다. 하지만...

코딩테스트 연습 - [1차] 뉴스 클러스터링 문제 풀이 아이디어 다중 집합? 문제를 읽어보면 교집합과 합집합이라는 키워드가 나오기 때문에 Set 자료형을 사용하면 좋을 것 같지만 다중 집합에 대해서 확장이 가능하다는 조건이 있습니다. 다중집합은 중복을 허용하기 때

코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 풀이 아이디어 k진수로 변경하기 다른 언어의 경우 아래처럼 n을 k로 나눈 나머지를 가지고 구하는 경우가 많습니다. 하지만 Swift의 경우에는 Int를 k진수로 바꾸어서 String으로 리턴해주는 String initializer가 있습니다. 훨신 편리합니다. 소수 구하기 처음에는 그냥 간단...

코딩테스트 연습 - 주차 요금 계산 문제 풀이 아이디어 문제가 상당히 복잡해 보이지만 문제를 하나하나 떼어놓고 보면 그렇게 어려운 문제는 아닙니다. 입차, 출차 시간을 어떻게 기록하고 전체 주차장에 머문 시간을 어떻게 계산할 것인가가 가장 중요한 부분인데 저는 Di

코딩테스트 연습 - [3차] 압축 문제 풀이 아이디어 문제에서 나온 그대로 구현하기만 하면 됩니다. 예시에 나온 변수명 w와 c를 그대로 사용해서 구현해보았습니다. i는 c의 index입니다. 주의할 점은 두 가지입니다. 먼저 마지막에 반복문을 탈출하고 나서 di

코딩테스트 연습 - [3차] n진수 게임 문제 풀이 아이디어 백준을 풀 때는 거의 풀어본 적이 없는데 프로그래머스에서는 진법에 관련된 문제가 많이 나오는 것 같습니다. 0 ~ ?까지의 숫자를 n진수로 바꾸고 나열해야 합니다. 매번 튜브가 말할 때마다 숫자를 구하기

코딩테스트 연습 - 방문 길이 문제 풀이 아이디어 Level 2 문제인데 배울 내용이 상당히 많은 문제였습니다. 이 문제의 포인트는 “길”을 어떤 자료형으로 어떤 자료형에 저장할 것인가입니다. “길 = (선)”을 어떻게 저장할 것인가? 보통 문제에서 이렇게 좌표

코딩테스트 연습 - [3차] 파일명 정렬 문제 풀이 아이디어 복잡하게 보이지만 결국 문자열을 다루는 단순한 문제 중에 하나입니다. 문제에 나온대로 그래도 구현해주면 됩니다. 참고로 parse 함수를 sort 안에서 실행하면 최대 NlogN회 실행하게 되므로 미리 파

코딩테스트 연습 - 연속 부분 수열 합의 개수 문제 풀이 아이디어 문제 이해하기 문제에서 제시한 원형 수열과 연속 수열의 개념을 먼저 이해해야 합니다. 원형 수열은 문제의 그림처럼 수열이 원형으로 표현한 것입니다. 특정한 시작과 끝이 없는 것이 특징입니다. 연속

코딩테스트 연습 - 숫자 게임 문제 풀이 아이디어 삼사법 삼사법이라는 고사를 아시나요? 손빈병법이라는 병법서에서 나온 말로 알고 있는데요. 말 3마리씩 각각 경주를 시킬 때 강 vs 강, 중 vs 중, 약 vs 약으로 경주를 시키는 대신, 강 vs 약, 중 vs 강, 약 vs 중으로 각각 경주를 시켜서 2:1의 승리를 노리는 전략입니다. 즉 약한 말을...

코딩테스트 연습 - 할인 행사 문제 풀이 아이디어 문제가 좀 길어서 파악하기 힘들었지만 결국 문제의 본질은 주어진 discount 배열에서 연속된 10개의 상품이 want와 number에 주어진 상품의 종류와 갯수와 일치하는 것인지 묻는 것입니다. 파이썬에서는 counter라는 내장 함수가 있는데요. 이 메소드는 배열의 어떤 원소가 몇개 있는지 dic...

코딩테스트 연습 - 귤 고르기 문제 풀이 아이디어 겉보기에는 어떻게 보일지 모르지만 문제를 차분하게 읽어보면 그렇게 어려운 문제가 아닙니다. 가장 적은 귤의 “종류”로 한 상자를 채우면 됩니다. 이렇게 하기 위한 가장 간단한 방법은 바로 귤의 크기의 종류별로 몇개씩 있는지 구하고 가장 많은 귤의 크기부터 상자를 채워나가면 됩니다. 그리디 알고리즘을 사용...

코딩테스트 연습 - 쿼드압축 후 개수 세기 문제 풀이 아이디어 쿼드 압축의 과정을 보면 이차원 배열을 압축할 수 없으면 해당 배열을 1/4한 이후에 같은 과정을 반복하면서 압축을 하고 있습니다. 그리고 이차원 배열의 크기가 1 x 1가 되어서 더 이상 압축할 수 없

코딩테스트 연습 - 메뉴 리뉴얼 문제 풀이 아이디어 주어진 주문을 가지고 세트 메뉴를 만들어야 하는데요. 세트 메뉴를 만들 때는 순서는 관계 없으니까 조합을 사용해서 세트 메뉴를 구현하면 됩니다. 각각의 주어진 order를 가지고 세트 메뉴가 될 수 있는 세트 후보

코딩테스트 연습 - 기지국 설치 아파트를 순회하는 풀이: O(N), N은 최대 200,000,000 문제 풀이 아이디어 1번 아파트부터 순회하면서 그리디 알고리즘을 활용해서 풀면 됩니다. 총 4가지 케이스가 있습니다. 현재의 아파트가 전파가 닿지 않을 때

코딩테스트 연습 - 삼각 달팽이 문제 풀이 아이디어 처음에 문제를 보았을 때는 이차원 배열을 사용하지 않고 할 수 있는 방법도 있지 않을까 생각을 했습니다만, 삼각 달팽이를 직접 구현하지 않고 푸는 것은 불가능합니다. 따라서 이차원 배열로 삼각 달팽이를 직접 구현한

코딩테스트 연습 - 불량 사용자 문제 풀이 아이디어 문제의 조건과 예시를 보면 불량 사용자를 의미하는 “*”이 들어간 불량 id는 여러 개의 id와 매칭이 될 수 있습니다. 반대로 하나의 id가 여러 개의 불량 id와 매칭이 될 수 있습니다. id와 불량 id는 1

코딩테스트 연습 - 보석 쇼핑 문제 풀이 아이디어 Two Pointer 이 문제를 처음 봤을 때는 gems를 dfs 등을 사용해서 gems 내에 모든 범위를 구하고 그 범위가 주어진 조건에 부합하는지 확인하는 방법을 생각했습니다만, gems 배열의 크기가 최대 1

코딩테스트 연습 - 수식 최대화 문제 풀이 아이디어 문제를 보면 상당히 복잡한 것 같지만 단계를 쪼개서 보면 각각의 해결 방안은 생각보다 쉽습니다. 총 3파트로 나누어서 문제를 해결해보도록 하겠습니다. String으로 주어진 식을 연산자와 피연산자로 분리하기 주

코딩테스트 연습 - [3차] 방금그곡 문제 풀이 아이디어 복잡한 알고리즘이 필요한 문제는 아닙니다만 주어진 String을 파싱하여 필요한 정보를 추출하는 과정이 필요합니다. #을 어떻게 처리할 것인가? 일단 #을 어떻게 처리할 지 생각을 해봅시다. 일반적인 음계

코딩테스트 연습 - 스티커 모으기(2) 문제풀이 아이디어 문제의 유형 자체는 DP에서 많이 본 문제입니다. i번째까지의 스티커를 떼었을 때의 최대값을 dp를 통해 0부터 구하고 마지막 스티커의 최댓값까지 구했을 때 그 값을 리턴하면 됩니다. i번째 스티커까지의 최댓

코딩테스트 연습 - 행렬 테두리 회전하기 문제 풀이 아이디어 처음에 문제를 읽었을 때는 뭔가 규칙이 있을거라고 생각을 했는데요. 하지만 테두리를 회전이 다음 회전에 영향을 미치므로 규칙을 찾는 것이 불가능합니다. 따라서 직접 행렬을 이차원 배열로 구현하고 회전해서 답을 구해보도록 하겠습니다. 회전하는 코드는 조금 복잡해보이지만 결국에는 회전 방향에 따...

코딩테스트 연습 - 두 큐 합 같게 만들기 문제 풀이 아이디어 그리디 알고리즘 문제의 목적은 두 “큐”의 합을 같게 하는 것입니다. 한 큐의 합이 다른 큐의 합과 다른 경우 두 큐의 차이를 줄일 수 있는 방법은 큰 큐에서 pop한 수를 작은 큐에 push하는 방법

코딩테스트 연습 - 배달 문제 풀이 아이디어 플로이드 와샬 알고리즘 문제를 풀기 위해서는 일단 1번 마을과 다른 마을 사이의 최단경로를 구해야 합니다. 1번 마을과 직접 연결된 도로 뿐만이 아니라 다른 마을을 건너서 가는 경로가 최단 경로가 될 수도 있습니다. 따

코딩테스트 연습 - 가장 큰 정사각형 찾기 문제 풀이 아이디어 🚫 Brutal Force 맨 처음에 문제를 풀 때는 row, column의 최댓값이 1,000 정도이므로 아래와 같은 코드로 정사각형을 최대 크기부터 하나하나 찾으면서 푸는 방법을 사용했는데요. 정

코딩테스트 연습 - 롤케이크 자르기 문제 풀이 아이디어 시간 복잡도 롤케이크의 최대 길이는 1,000,000입니다. 즉 이중반복문을 사용하면 안되고 무조건 O(N)의 알고리즘으로 답을 구해야 합니다. 또한 케이크를 자르는 것에 착안해서 Array의 subscri

코딩테스트 연습 - 합승 택시 요금 플로이드 와샬 알고리즘 문제 풀이 아이디어 플로이드 와샬 알고리즘은 모든 노드에서 다른 노드까지 가는 최적의 루트를 구하는 알고리즘입니다. 이 최적의 루트를 구하는 과정에서 i에서 j로 바로 가는 루트보다 다른 k를 거쳐서 가는

코딩테스트 연습 - 멀쩡한 사각형 문제 풀이 아이디어 ❗️w, h는 1억 이하의 자연수 처음에 이 문제를 봤을 때는 Dynamic Programming을 생각했습니다만, w와 h가 최대 1억이라는 것은 동적계획법으로 풀 경우 1억 * 1억의 엄청나게 큰 Cache

문제 풀이 아이디어 numbers의 길이가 최대 1,000,000이기 때문에 일일히 완전탐색을 통해서 뒷큰수를 구할 수는 없습니다. stack을 사용해서 stack.last보다 크면 pop, 작으면 push를 하면 stack 내부가 오름차순으로 정렬되는 원리를 사용

문제 풀이 아이디어 문제의 정의 유일성 해당 속성들로 key를 만들었을 때 모든 row들이 각각 유일하게 식별되어야 합니다. 이를 코드로 옮기면 해당 속성으로 key를 만들어서 set에 넣고 (중복 제거를 위해서) 해당 set의 길이와 row의 갯수가 동일하면 유일성을 가진다고 볼 수 있습니다. 최소성 유일성을 가진 키를 구성하는 속성 중에 하...

https://school.programmers.co.kr/learn/courses/30/lessons/154538 문제 풀이 아이디어 딱 보면 알 수 있는 것은 아니지만 읽어보면 결국은 최단 경로 문제입니다. x에 n을 더하기, 2를 곱하기, 3을 곱하기의 3가지

문제 풀이 아이디어 문제에서 주어진대로 구현하기만 하면 됩니다. 보조벨트는 선입선출의 방식이므로 stack을 활용합시다. 다만 정말 현실을 “그대로” 구현하기 되면 아래와 같은 실수를 하게 됩니다. 이중 while 문으로 복잡한 if문을 대체하는 테크닉을 익혀두도록

문제 링크 문제 풀이 아이디어 places의 길이가 최대 5이고 place는 각각 5 * 5의 행렬입니다. 따라서 완전탐색을 해도 125번의 연산 밖에 하지 않습니다. 시간 복잡도에 대해서는 걱정할 필요가 없습니다. 두 “P” 지점에 대해서 맨해튼 거리 2 이하의

문제 링크 문제 풀이 아이디어 최단 거리 경로 = bfs 일종의 최단 거리 경로 문제의 응용형입니다. 따라서 bfs를 기반으로 문제를 풀어야 합니다. 물론 dfs로 문제를 풀 수도 있습니다만 불필요한 경로를 지나치게 탐색하기 때문에 시간초과가 날 가능성이 큽니다.

문제 풀이 아이디어 문제의 길이와 복잡한 예시에 약간 쫄을(?) 수도 있으나 풀어보면 평범한 그리디 문제입니다. 애초에 n이 최대 0,000이므로 O(n) 이하의 시간 복잡도를 가진 알고리즘으로 풀어줘야 합니다. 1번 구역부터 순회하면서 덧칠이 필요한 구역을 만나면

문제 풀이 아이디어 문제의 길이와 복잡한 예시에 약간 쫄을(?) 수도 있으나 풀어보면 평범한 그리디 문제입니다. 애초에 n이 최대 0,000이므로 O(n) 이하의 시간 복잡도를 가진 알고리즘으로 풀어줘야 합니다. 1번 구역부터 순회하면서 덧칠이 필요한 구역을 만나면

문제 풀이 아이디어 문제의 길이와 복잡한 예시에 약간 쫄을(?) 수도 있으나 풀어보면 평범한 그리디 문제입니다. 애초에 n이 최대 0,000이므로 O(n) 이하의 시간 복잡도를 가진 알고리즘으로 풀어줘야 합니다. 1번 구역부터 순회하면서 덧칠이 필요한 구역을 만나면

문제 풀이 아이디어 🚫 브루탈 포스 1에서 s.count까지 모든 길이의 subString을 브루탈 포스를 통해서 확인하는 것은 불가능합니다. s의 최대 길이가 2500이기 때문입니다. ✅ DP 펠린드롬에는 규칙이 있다! 펠린드롬에는 규칙이 있기 때문에 규칙이 없는 경우에 사용하는 브루탈 포스를 사용할 필요가 없습니다. 길이가 3인 펠린드롬을 ...

문제 풀이 아이디어 🚫 브루탈 포스 가능한 모든 a와 b를 탐색하면서 원 안에 들어오는지 탐색하는 방법이 가장 먼저 떠오릅니다. 하지만 k가 최대 1,000,000, d도 최대 1,000,000입니다. 이중 반복문을 사용하면 100% 시간 초과입니다. ✅ 원의

문제 풀이 아이디어 하노이의 탑은 전형적인 재귀함수 문제입니다. 먼저 n을 1부터 늘려가면서 규칙을 찾아보도록 하겠습니다. n이 1일 때는 바로 1에서 3으로 1번 옮기면 됩니다. ([[1, 3]]) n이 2일 때는 작은 블록을 잠시 2로 옮겨두었다가, 큰 블

문제 풀이 아이디어 전형적인 dfs로 node의 갯수를 세는 문제입니다. 다만 이 문제는 node의 갯수가 아니라 node에 적힌 식량의 갯수를 더해야 합니다. 하지만 원리는 동일합니다. 아래 두 포스팅을 참고해주세요! (Swift) 백준 1743 음식물 피하기

문제 풀이 아이디어 콘의 목표 콘의 목표는 가장 늦게 버스를 타는 것입니다. 즉 콘의 목표를 만족하기 위해서는 아래의 조건이 만족 되어야 합니다. 무조건 막차를 타야한다. (가장 늦게 오는 버스이므로) 여러 명이 막차를 탄다만 가장 늦게 타야한다. (최대한 늦게

문제 풀이 아이디어 점프와 순간이동과 유사한 문제입니다. 수를 바꾸는 몇가지 선택지를 가지고 원하는 숫자까지 도달하는 문제입니다. 완전 탐색? 이 문제의 N은 최대 100,000,000입니다. 버튼의 종류는 최대 16종류가 되겠습니다. 따라서 완전 탐색을 하게

문제 풀이 아이디어 (그리디) 체크인과 체크아웃을 나눈다. 현재의 입력은 체크인과 체크아웃이 하나의 배열 안에 묶어서 제공합니다. 필요한 방의 갯수를 구하기 위해서는 해당 입력을 체크인과 체크아웃으로 각각 나눌 필요가 있습니다. 그리고 해당 입력을 “시간 순”으로

문제 풀이 아이디어 공약수를 통해서 푸는 문제입니다. 먼저 배열 A와 배열 B의 모든 수를 나눌 수 있는 가장 큰 수, 즉 최대 공약수를 구해야 합니다. 그리고 나서 해당 최대공약수가 다른 배열의 수를 모두 나눌 수 있는지 확인해야 합니다. 서로의 배열을 나누는

문제 풀이 아이디어 구현 문제를 풀기 위해서 특별한 알고리즘은 필요가 없는 구현 문제입니다. Dictionary 활용 문제 전반에 걸쳐서 사람을 구분하기 위해서 index와 이름 (String)을 혼용해서 사용하고 있습니다. 그리고 마지막에 답을 출력할 때는

문제 풀이 아이디어 1번 상자 그룹, 2번 상자 그룹? 문제의 설명을 읽어보면 혼자 노는 방법이 자세히 적혀있습니다. 게임은 총 2번의 시도로 나뉘어지고 각각의 시도를 통해서 얻은 상자의 갯수를 곱해서 구하는 것으로 되어있습니다. 이 방법에 따라서 랜덤으로 상자를

문제 풀이 아이디어 구현 문제를 읽어보면 뭔가 복잡한 과정에 대해 설명하고 있습니다. 하지만 부분부분 쪼개서 읽어보면 단지 주어진 입력을 주어진 문제 그대로 코드로 구현하면 되는 문제입니다. 복잡한 풀이 방법, 알고리즘에 대해 고민할 필요가 1도 없습니다. 딱 원

문제 링크 문제 풀이 아이디어 풍선 터뜨리기 프로세스 다른 풍선부터 싹 터뜨리자 조건에 의하면 인접한 풍선만 짝을 지어 터뜨릴 수 있습니다. 따라서 최후의 풍선이 되기 위해서는 다른 풍선들이 다 터지고 마지막으로 남은 풍선과 최후의 풍선이 나란히 있어야 합니다.

문제 링크 문제 풀이 아이디어 시간복잡도 weights의 길이가 최대 100,000입니다. 따라서 weights의 모든 사람을 짝지어서 (nC2) 짝꿍이 되는지 확인하는 방식으로 해서는 안되고 O(N) 안에 해결을 봐야 합니다. Dictionary 활용 문제에

문제 링크 문제 풀이 아이디어 2개의 bfs 문제를 읽어보면 전형적인 최단거리 문제 따라서 전형적인 bfs 문제입니다. 시작점에서 레버까지의 최단거리, 레버에서 출구까지의 최단거리를 구하면 됩니다. 2개의 bfs를 사용해서 풀면 되는 것이죠. 같은 공간을 여러번

문제 링크 문제 풀이 아이디어 부분합 N이 최대 500,000입니다. O(N)의 시간복잡도를 가진 알고리즘을 사용해야 합니다. 연속된 부분 수열의 합 문제는 부분합을 사용할 경우 O(N)의 시간복잡도로 문제를 해결할 수 있습니다. 펄스 수열 다만 이 문제는 단

완전 탐색 문제 풀이 아이디어 곡괭이의 종류는 총 3가지이고 광물은 50개입니다. 5개씩 캐니까 10가지의 경우의 수가 있을 수 있습니다. 따라서 완전탐색을 한다고 해도 3^10 = 59,049에 불과합니다. 따라서 dfs를 활용한 완전 탐색을 하더라도 시간 제한

완전 탐색 문제 풀이 아이디어 곡괭이의 종류는 총 3가지이고 광물은 50개입니다. 5개씩 캐니까 10가지의 경우의 수가 있을 수 있습니다. 따라서 완전탐색을 한다고 해도 3^10 = 59,049에 불과합니다. 따라서 dfs를 활용한 완전 탐색을 하더라도 시간 제한

문제 링크 이진 트리 순회 정의 문제에 나온 순회의 방식은 전위 순회와 후위 순회입니다. 이 외에도 2가지 더 있는데요. 각각의 정의를 설명드리겠습니다. 전위 순회: 루트 우선 (루트를 다 방문하고 나서 다른 노드로) 후위 순회: 하위 트리 우선 (하위 트리를

문제 링크 문제 풀이 아이디어 😅 완전 탐색 처음에 문제를 읽자마자 바로 손 가는대로 풀면 아래와 같은 코드가 됩니다. skill에 주어진 범위를 전부 순회하면서 일일히 데미지 혹은 힐량을 누적하고 마지막에 파괴되지 않는 건물을 세는 방법입니다. 아주 직관적인

문제 풀이 아이디어 구현? 문제를 읽어보면 기본적인 구현 문제처럼 보입니다. 문제에서 요구하는 바를 코드로 바로 옮기면 되는 것이죠. 하지만 문제를 보면 연속된 데이터의 중간 부분을 삭제하고 삽입하는 작업을 여러번 반복해야 합니다. 보통의 Array를 사용하게

문제 링크 문제 풀이 아이디어 백트래킹 알고리즘을 배울 때 가장 먼저 풀어보는 문제입니다. 저도 거의 1년 만에 다시 풀어보는 것 같은데요. 각 행의 각 열에 퀸을 직접 놓아보면서 완전 탐색을 하면 됩니다. 저는 재귀함수를 활용해서 풀어보도록 하겠습니다. 코드

문제 링크 문제 풀이 아이디어 콜라츠 추측, 정적분… 문과출신인 저로서는 보자마자 움츠러들게 되는 복잡한 개념들인데요. 겉모습에 쫄(?) 필요는 없습니다. 결국 시키는대로 그대로 하면 풀리는 구현문제입니다. 시간복잡도 같은 것도 크게 신경쓰지 않아도 됩니다. 콜라

문제 링크 문제 풀이 아이디어 이번 문제는 흔한 최단 거리 문제처럼 보입니다. 어떤 최단 거리 알고리즘을 사용해서 풀어볼까요? 플로이드 와샬? 어딘가를 들러서 다른 곳을 갈 때 최단거리를 구하는 대표적인 알고리즘으로 플로이드 와샬 알고리즘이 있습니다. 플로이드

문제 링크 문제 풀이 아이디어 아주 전형적인 동서남북 bfs 최단경로 문제입니다. 동서남북 방향으로 말을 이동시키면서 bfs를 실시하면 됩니다. 하지만 살짝 다른 점은 동서남북 1칸 씩 이동하는 것이 아니라 동서남북으로 미끄러진다는 것입니다. 즉, 경계선 혹은 장애

문제 링크 처음 풀이 😅 문제 풀이 아이디어 처음에 문제를 풀 때는 문제의 조건에 맞게 정직하게(?) 큰 원 안에 있는 점을 모두 구하고, 작은 원 안에 있는 점을 모두 구하고 그 둘을 뺐습니다. 심지어 작은 원의 경계에 있는 점들은 모두 들어야 가야하기 때문에

문제 링크 문제 풀이 아이디어 문제는 크게 2가지 작업을 수행해야 합니다. 먼저 인센티브를 받지 못하는 사람을 찾고 그 사람을 제외한 사람들 중에 완호의 순위를 찾아내야 합니다. 인센티브를 못 받는 사람 찾기 일단 N이 최대 100,000입니다. 따라서 이중 반

문제 링크 문제 풀이 아이디어 문제에서 요구한 사항 그대로 구현하면 되는 구현문제입니다. 다만 과제의 진행 시간과 다음 과제의 시작 시간을 비교해서 케이스 별로 나누는 것이 살짝 복잡합니다. “시간:분” → “분” “시간:분”의 형태로 되어 있으면 시간 계산이

문제 링크 문제 풀이 아이디어 수직선 + 누적합 👍 이렇게 연속된 시간 or 공간에 대해서 다룰 때는 이 포스팅(시간) 혹은 이 포스팅(공간)에서 사용한 수직선 + 누적합을 활용하면 시간복잡도를 O(N^2)에서 O(N)로 줄일 수 있습니다. 수직선의 길이인 pl

문제 링크 문제 풀이 아이디어 시간 복잡도 틱택토는 3 * 3 배열 안에서 이루어지는 게임이므로 시간복잡도는 고려할 필요가 전혀 없습니다. 0을 리턴하는 케이스 나누기 우리에게 주어진 정보는 틱택토가 끝난 결과입니다. 따라서 O와 X가 놓여진 순서는 따지지 않

문제 링크 문제 풀이 아이디어 시간복잡도 0 ≤ s < e ≤ 100,000,000의 조건을 보면 절대로 수직선 위에 미사일을 표시한다거나 해서 N을 100,000,000만들어서 풀면 안됩니다. 이렇게 하면 O(N)만 해도 시간초과가 바로 날 것입니다. 따라서 s

문제 링크 문제 풀이 아이디어 완전 탐색 users의 길이 최대 100, 할인 비율 종류 4개 (10%, 20%, 30%, 40%), 이모티콘의 종류가 최대 7가지로 단촐한 N을 가진 문제입니다. 이모티콘 x 할인의 모든 케이스를 구해도 4^7이고 여기에 user

문제 링크 문제 풀이 아이디어 시간복잡도 info의 길이가 최대 50,000 그리고 query의 길이가 최대 100,000입니다. 따라서 각각 N과 M이라고 하겠습니다. 일단 M이 굉장히 크므로 딱 1번만 순회해야 합니다. 그리고 N의 길이도 작지 않습니다. O(

문제 링크 문제 풀이 아이디어 트리? 해당 구조물은 트리로 되어 있습니다. 따라서 자연스럽게 class로 Node를 만들고 일단 트리 자료구조를 만들어 놓고 문제를 풀기 시작하는 분들 계실 것 같습니다. (저도 그랬습니다;;;) 하지만 일반적은 DFS로 풀 수 있

문제 링크 문제 풀이 아이디어 이 문제는 일단 화살이 최대 10개에 과녁에 11개 밖에 없습니다. dfs를 통해서 완전탐색을 해도 시간에 구애 받지 않고 풀 수 있는 입력 값입니다. 탈출조건과 정답조건에 유의해서 풀면됩니다. 자세한 풀이는 코드를 참고해주세요. 코

문제 링크 문제 풀이 아이디어 문제에서 주어진대로 그대로 구현하면 되는 문제입니다. 두 직선의 교점을 구하는 공식, 교점이 생기지 않는 두 직선의 특징까지 모두 주어졌습니다. 교점 구하기 일단 x, y 좌표가 모두 정수인 교점부터 구해야 하는데요. 조합을 활용해

문제 링크 문제 풀이 아이디어 완전탐색 주어진 친구들의 이동 거리 및 취약 지점의 위치에 일정한 규칙이 없습니다. 일단은 모든 케이스를 따져봐야 합니다. 따라서 기본적인 문제 풀이 방법은 완전탐색입니다. 하지만 무작정 완전 탐색을 하면 시간초과가 날 수 있습니다

문제 링크 문제 풀이 아이디어 Greedy! 제가 생각하는 이번 문제의 핵심은 “각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.”라는 표현입니다. 문제에서도 볼드 처리가 되어 있는데요. 이 말은 즉 “같은 집에 1번 이상 방문해

문제 링크 문제 풀이 아이디어 사전 순 문제에서 제시한 목표는 110과 111의 위치를 바꾸어서 사전순으로 가장 앞에 오는 문자열을 찾아서 return 하는 것입니다. 같은 갯수의 0과 1로 사전 순으로 가장 앞에 오는 문자열을 만들기 위해서는 0을 최대한 앞에

지난 번 포스팅까지 프로그래머스에 있는 문제를 풀어보았는데요. 이번 포스팅 부터는 리트코드의 문제들을 풀어보도록 하겠습니다. 문제 링크 문제 풀이 아이디어 아주 간단한 유형의 문제입니다. 다만 주어진 문자열을 바로 뒤집어서 비교하면 안되고 약간에 가공을 거쳐야 합

문제 링크 문제 풀이 아이디어 String 미리 파싱 해두기 주어진 조건 그대로 정렬하는 함수를 구현하면 된다. String을 그대로 사용하면서 별도의 함수를 구현하는 방법도 있겠으나 그러면 String을 id와 log 내용으로 나누는 작업을 매번 해야한다. Sw

Most Common Word - LeetCode 문제 풀이 아이디어 특별하게 필요한 알고리즘은 없다. 단지 문자열을 원하는 조건에 맞게 다루기만 하면 된다. 원하는 조건은 다음과 같다. 대소문자를 무시할 것 (= 소문자로 변경할 것) 구두점을 제외할 것 (= 알

Group Anagrams - LeetCode 문제 풀이 아이디어 하나의 단어에 쓰인 알파벳의 순서를 바꾸었을 때 다른 단어를 만들 수 있다면 두 단어는 아나그램의 관계라고 정의할 수 있다. 따라서 동일한 알파벳 구성을 가진 두 단어를 의미한다. 따라서 아나그램을

Longest Palindromic Substring - LeetCode 문제 풀이 아이디어 Palindrome의 속성과 투 포인터 투 포인터 연속된 데이터를 다룰 때 시작점과 끝점 2개의 포인터를 가지고 다루는 기법이다. Palindrome (이하 펠린드럼)의

Two Sum - LeetCode 문제 풀이 아이디어 브루탈 포스? 브루탈 포스 (완전 탐색)은 이 문제를 가장 쉽게 푸는 방법이다. 그냥 이중반복문으로 두 수를 더해가면서 target이 나오면 리턴하면 된다. 하지만 시간복잡도가 O(n^2)가 된다. 더 빠른 방

Trapping Rain Water - LeetCode 문제 풀이 아이디어 순차 탐색? 내가 처음에 떠올린 풀이는 왼쪽부터 탐색을 하다가 기존의 벽 중에 가장 높은 벽 보다 높은 벽이 나오면, (즉 물 웅덩이가 형성되면) 물의 양을 계산하고 다음으로 넘어가는 것이

3Sum - LeetCode Brutal Force? 가장 처음에 떠오르는 생각은 완전탐색 브루탈 포스를 활용하는 것이다. 하지만 3개의 수의 합을 구하는 문제에서 완전탐색을 사용하면 O(N^3)이다. 너무 오래 걸릴 것이다. 실제로 채점을 해보면 타임 아웃이 된다

Array Partition - LeetCode 문제 풀이 아이디어 문제가 일견 복잡하게 보이는 부분도 있지만 찬찬히 읽어보면 상당히 간단한 문제이다. 주어진 배열의 길이는 무조건 짝수로 따라서 앞에서 부터 인접한 숫자끼리 짝으로 묶을 수 있다. 각각의 묶음에서

LeetCode - The World's Leading Online Programming Learning Platform 문제 풀이 아이디어 문제의 제약 문제의 제약 중에 “You must write an algorithm that runs in O(n) time

LeetCode - The World's Leading Online Programming Learning Platform 문제 풀이 아이디어 문제의 조건 이 문제가 요구하는 조건을 정리하면 아래와 같다. 주식이 싼 시점 i와 주식이 비싼 지점 j를 찾을 것 (단

LeetCode - The World's Leading Online Programming Learning Platform Array를 활용한 풀이 문제 풀이 아이디어 주어진 링크드리스트가 Palindrome인지 확인하기 위해서는 링크드리스트를 거꾸로 탐색할 수 있

LeetCode - The World's Leading Online Programming Learning Platform 하나하나 붙이는 방법 문제 풀이 아이디어 가장 직관적인 방법이다. 그냥 새로운 링크드리스트를 하나 만들고 l1과 l2를 완전탐색해서 새로운 링

LeetCode - The World's Leading Online Programming Learning Platform 문제 풀이 아이디어 처음에 이 문제를 읽으면 가장 간단한 방법으로 떠올리는 것이 링크드리스트를 Array로 바꾼 다음 그 Array를 뒤집어서

LeetCode - The World's Leading Online Programming Learning Platform 문제 풀이 아이디어 digit를 숫자로 바꾸어서? 문제에 보면 digits가 reversed order로 되어 있다는 부분이 있다. 이 부분을

LeetCode - The World's Leading Online Programming Learning Platform 문제 풀이 아이디어 문제의 조건 떠올릴 수 있는 가장 쉬운 방법은 node들의 순서를 조정하지 않고 그냥 node 안에 값만 바꾸는 것이다.