class Solution: def isPalindrome(self, s: str) -> bool: # 예외 처리 if s == " ": return True s = s.lower() # 소문자로 변환 new_str = "" for i in s: if i.isalnum(): new_str += i n = len(new_str) for i in range(n // 2): if new_str[i] != new_str[n - i - 1]: return False return True
파이썬
import heapq INF = int(1e9) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split()) graph[a].append((b, 1)) graph[b].append((a, 1)) distance = [INF]*(n+1) start = 1 def dijkstra(start): # 다익스트라 q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if dist > distance[now]: continue for i in grap..
코딩 문제 풀 때 굉장히 알아두면 유용한! 문자열을 다룰 때 쓰이는 join 함수 1. 형태 string.join(iterable) 여기서 string 에 들어가는 문자열은 구분자이다. 물론 "".join(iterable) 이렇게 빈 문자열을 붙일 수도 있다. 2. 예시 i) 문자열 리스트를 하나로 합치기 myNumber = ['1','2','3','4','5'] print("".join(myNumber)) ii) 공백 문자를 사이에 두고 문자열 리스트를 하나로 합치기 myNumber = ['1','2','3','4','5'] print("_".join(myNumber)) myStr = ["Hello", "My", "Name", "is", "Minjee"] print("!!!!!!".join(myStr)..
enumerate(iterable한 객체, start=0) enumerate는 파이썬 내장함수로, 반복문에서 사용되어 인덱스와 iterable한 객체의 데이터가 묶인 튜플을 반환한다. 여기서 iterable의 의미: member를 하나씩 차례로 반환 가능한 object를 말한다. iterable한 데이터 타입의 예로는, list, str, tuple이 있다. enumerate 의 파라미터는 iterable한 원소와 index이다. index는 생략가능하며, 지정해주지 않을 경우에 0부터 시작한다. 다음과 같이 for문의 인자를 하나만 설정해주면, 결과값으로 튜플이 반환된다. data = ['A', 'B', 'C'] # iterable한 list for i in enumerate(data): print(i..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS로 풀이했다. 나 근데 가로 세로가 아직 헷갈린다;; 아이디어는 다음과 같다. n = 7, m = 5 사이즈의 2차원 배열 (= 그래프) 가 있다고 생각하면, 각 칸을 모두 0으로 초기화 시킨다 입력되는 직사각형 부분에 해당하는 칸들은 2차원 배열에서 1로 표시한다. 1은 이미 방문된 노드라는 의미이다. 그후 전체 2차원 배열을 이중 for문으로 하나씩 칸의 값을 체크하면..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉽지않은 계단수 문제였따 .. 여기서 (0-9)는 맨 끝자리수이고 N은 문제에서와 같이 자리수를 뜻한다. 규칙은 이렇게 각 끝자리수의 개수를 대각선 방향 왼쪽 위 + 대각선 방향 오른쪽 위 를 더하면 구할 수 있다. 즉, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 식이 나온다 !!! 끝자리 수가 0, 9일때는 각각 한쪽방향의 대각선에서만 존재하니까 그 수를 그대로 옮겨오면 된다. 위의 그림에서는 파란 선을 참고! 자리수가 1일때 (한자리수)일 때는 직접 초기화를 해주어야 한다. ..
다이나믹 프로그래밍은 전형적으로 보텀업 방식 형태를 보인다. 그렇지만 탑다운 방식과 보텀업 방식의 차이를 알아볼 필요가 있다. 상향식, 하향식에 따라 재귀호출인지 반복호출인지의 차이도 보여지기 때문이다. 1. 탑다운 방식 (Top-down) 재귀 함수를 이용하여 DP를 작성하는 방법. 큰 문제를 해결하기 위해 작은 문제를 호출한다. d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end=' ') if x == 1 or x == 2: return 1 if d[x] != 0: # 이미 계산한 적 있으면 그대로 값을 반환한다. return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x] * 실행 결과 f(10)을 구하기 위해서 ..
1. Stack 스택 자료구조 선입후출 (First In Last Out) 구조 stack = [] stack.append(1) # push 를 append()로 구현한다. stack.append(2) stack.append(3) stack.pop() stack.append(4) print(stack) # 스택의 가장 밑에 있는 원소부터 출력 print(stack[::-1]) # 스택 가장 위에 있는 원소부터 출력 [1, 2, 4] [4, 2, 1] 파이썬에서 stack 자료구조를 구현하기 위해서는 이렇게 다른 라이브러리가 필요없이, list 구조에서 append()와 pop()으로 간단히 구현할 수 있다. 2. Queue 큐 자료구조 선입선출 (First In First Out) 구조 , 나중에 온 사..
