코딩테스트

문제중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라  · 입출력 예stringreturn"abcabcbb"3 (abc)"bbbbb"1 (b)"pwwkew"3 (wke)풀이1. 슬라이딩 윈도우와 투 포인터 사이즈 조절def lengthOfLongestSubstring(s: str) -> int: used = {} max_length = start = 0 for index, char in enumerate(s): if char in used and start 투 포인터로 문제를 풀이하였는데, 포인터 2개 모두 왼쪽에서 출발한다. 두 번째 포인터 (index)를 오른쪽으로 확장시켜 나가며 문자열을 검사한다. 문자가 앞서 등장했는지 여부를 판단하고, 등장했을 경우 시작점을..

문제자연수 N이 주어진다. N을 이진수로 바꿔서 출력하는 프로그램을 작성하시오.  · 제한사항1. 자연수 N은 1이상, 100,000,000,000,000이하이다.2. N을 이진수로 바꿔서 출력하며, 이진수는 0으로 시작하면 안된다. · 입출력 예 Nreturn53110101풀이1. Men = int(input())def binary(num: int) -> str: print(bin(num)[2:])binary(n)bin 메소드를 사용하여 입력받은 수를 이진수로 변환하고, 이진수로 변환할 경우 앞에 '0b'가 붙기 때문에 리스트 슬라이싱을 이용하여 '0b'를 제거하였다.  이 문제 출제의 요점인 재귀함수 호출을 통해 다른 방법으로 풀어볼 수 있을 것 같다.

문제0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.  · 제한사항1. 정수 N은 0보다 크거나 같고 12보다 작거나 같다. · 입출력 예 Nreturn10362880001풀이1. Men = int(input())def factorial(n: int) -> int: if n == 1: return 1 elif n == 0: return 1 else: return n * factorial(n-1)print(factorial(n))일반적인 팩토리얼 풀이법을 사용하여 문제를 풀었다. 재귀함수 호출을 통해 팩토리얼을 계산하고, n이 1 또는 0일 경우 1을 반환한다.

문제2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라  · 입출력 예digitsreturn"23"["ad", "ae", "af", "bd", "bf", "bf", "cd", "ce", "cf"]풀이1. 모든 조합 탐색-> 가능한 경우를 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다.입력값 digits를 자릿수로 쪼개어 반복하고, 숫자에 해당하는 모든 문자열을 반복하며 문자 단위로 재귀 탐색을 진행한다. 문자를 조합해 만들 수 있는 길이는 입력값의 길이와 동일하므로, 해당 조건을 재귀함수의 종료 조건으로 설정하고, 조건에 맞지 않을 경우 dfs를 반복 수행한다.

문제1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. (연결되어 있는 1의 덩어리 개수를 구하라) · 입출력 예 grid mapreturn111101101011000000001110001100000100000113풀이1. DFS로 그래프 탐색이와 같이 작성하였을 경우, grid를 dfs 함수 호출시마다 넘겨주어야 하고, 함수 호출 시 매번 self.가 따라 붙는다.  2. DFS로 그래프 탐색 (중첩함수 사용)DFS 탐색을 하는 dfs 함수는 동서남북을 모두 탐색하며 재귀호출한다. 이동하고자 하는 곳이 육지가 아닌 경우에 return 하도록 설정해줌으로써 연결되어 있는 섬을 구할 수 있다. 이 함수에서 이미 방문했던 곳(grid[i][j])은 1이 아닌 값으로 마킹하..

문제매일의 화씨 온도(˚F) 리스트 T를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라  · 입출력 예 T[73, 74, 75, 71, 69, 72, 76, 73]return[1, 1, 4, 2, 1, 1, 0, 0] 풀이1. 스택 값 비교-> 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교하여, 더 높다면 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.def dailyTemperatures(T: list[int]) -> list[int]: answer = [0] * len(T) stack = [] for i, cur in ..

문제APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다. 이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은..

문제전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. · 구조대: 119 · 박준영 : 97 674 223· 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. · 제한사항1. phone_book의 길이는 1이상 1,000,000이하입니다.2. 각 전화번호의 길이는 1이상 20이하입니다.3. 같은 전화번호가 중복해서 들어있지 않습니다.  · 입출력..

문제n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.  예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.1. -1+1+1+1+1 = 3 2. +1-1+1+1+1 = 33. +1+1-1+1+1 = 34. +1+1+1-1+1 = 35. +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타켓 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return하도록 solution 함수를 작성해주세요. · 제한사항1. 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.2. 각 숫자는 1이상 50이하인 자연수입니다.3. 타겟 넘버는 1이상 1000이..

문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어, 7대의 컴퓨터가 그림과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터..

문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.  · 입력 첫째 줄에 정점의 개수 N(1줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. · 출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. · 입출력 예 inputoutput4 5 11 21 31 42 43 41 2 4 31 2 3 45 5 35 45 21 23 4..

문제상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. 팩토리얼 진법은 각 자리에 올 수 있는 숫자는 0부터 9까지로 10진법과 거의 비슷하다. 하지만, 읽는 법은 조금 다르다. 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다. 팩토리얼 진법으로 작성한 숫자가 주어졌을 때, 10진법으로 읽은 값을 구하는 프로그램을 작성하시오.  · 입출력 예 numreturn719531115711081028풀이1. Medef factorial(num:..