B_log

문제 문제 상황 - 알파벳 문자열을 검색하며 연속 2개인 것을 제거해주고 모두 제거가 되면 1, 아니면 0을 반환한다. 해결 전략 - 스택을 활용해 제거가 되는지 확인한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def solution(s): # s를 전체 순회하며 stack에 저장하며 제거 stack = [] for i in range(len(s)): # 스택에 요소가 존재할 때 if stack: if s[i] == stack[-1]: stack.pop() else : stack.append(s[i]) else : stack.append(s[i]) return 0 if stack else 1 cs 해설 - 쉬운 문제 새로 학습한 것 & 실수 - . 출처 - https://progra..

문제 문제 상황 - 주어진 그림에서 특정 시점에 같은 블록이 2x2로 존재하면 그 요소를 삭제하고 동시에 그 위에 있던 요소를 아래로 밀어 과정을 반복한다. 지워지는 블록이 모두 몇 개인지 판단한다.- 해결 전략 - 우선 리스트를 좀 더 편하게 사용하기 위해 주어진 배열을 90도 회전시켜 아래로 빈칸을 채우는 것이 아니라 왼쪽으로 채우는 구조로 바꾼다. - 배열을 회전시키는 함수, 정해진 조건 하에서 사방을 확인하는 함수, solution 함수 세개로 분할해 문제를 해결하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45..

문제 문제 상황 - 오른쪽 또는 아래쪽으로만 움직이면서 합을 더해나가는 구조이다. 이 중 도착했을 때 총합이 최소가 되는 경로를 찾으면 된다. 해결 전략 - 백트래킹 최소합 문제와 거의 비슷하다. 다만 N-queen처럼 단방향으로 움직이는 것이 아니라 2차원적으로 움직이므로 조금 다르지만 기본적으로 Pruning 하는 개념은 같다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 # 탐색 함수 def BFS(x, y): # 전역변수 선언 global min_total, sub_sum # 더 계산할 필요가 없다. if min_total sub_sum: min_total..

문제 - https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브�� programmers.co.kr 문제 상황 - 1. 대소문자의 차이는 무시한다. 2. 입력으로 들어온 2글자 이상, 1000글자 이하의 문자는 2글자씩 끊어서 다중 집합으로 만든다. 3. 공백, 숫자, 특수문자 등은 처리하지 않고 무시하고 넘어간다. 4. 중복이 허용되기 때문에 파이썬의 set 자료형을 쓸 수 없다. 해결 전략 - 자카드 유사도를 구하는 함수와..

문제 - NxN의 배열이 주어질 때에 각 row에서 숫자를 선택해나가는데 한 column에 한 요소만 선택되게하여 최소 합을 구한다. 문제 상황 - 하나의 선택이 다음 선택에 영향을 미치는 구조이므로 단순히 최소값들을 모으는 것으로 최소합을 구할 수 없다. 해결 전략 - 완전탐색으로 하기에는 경우의 수가 너무 커질 수 있어 backtracking의 pruning 조건을 삽입한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 # row를 파라미터로 받는 최소 합을 찾는 함수 def find_min(row): global part..

문제 - 기존에 풀었던 미로 문제와 흡사하지만 이동한 최소거리를 계산하는 문제이다. 이동 가능 위치는 0, 벽은 1, 출발점은 2, 목적지는 3이다. 문제 상황 - 기존에는 목적지 도착이 가능한지 여부였지만 이번에는 최소 거리다. 그냥 거리가 아니라 최소거리이므로 조건을 잘 설정해야한다. 해결 전략 - 재귀를 이용한 풀이에 문제가 있어 큐를 이용해 다시 풀었다. distance 배열을 만들어 큐가 돌때마다 (해당 위치 +1) 값을 저장해 출발점(2)에서 부터의 거리를 계산하였다. - visited 항목을 통해 이미 도착한 위치를 파악하고 변수 하나를 추가해 이동한 거리를 파악한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ..

문제 - N개로 이루어진 수열에서 맨 앞의 값을 맨 뒤로 보내는 작업을 M번 했을 때, 맨 앞의 값을 구한다. 문제 상황 - 원형큐의 모형을 하고 있다. 해결 전략 - 실제로 원형큐를 구현할 필요 없이 index의 움직임만으로 쉽게 구현 가능하다. 코드 1 2 3 4 5 6 7 8 9 10 11 # testcase T = int(input()) for idx in range(T): N, M = map(int, input().split()) N_list = list(map(int, input().split())) # 큐의 맨 앞 front = 0 # 맨 앞의 인덱스를 N%M만큼 이동 front += M%N # 주어진 요소를 출력 print(f"#{idx+1} {N_list[front]}") cs 해설 - ..

문제 - 1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다. 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는다. 기준은 [(i+j)//2 + 1: ]이 된다. 문제 상황 - 기저조건까지 리스트를 세분화해서 내려간 뒤 다시 위로 올라오며 조건을 판단한다. 해결 전략 - 숫자 1이 가위, 2, 2는 바위, 3은 보 이므로 조건을 통해 대소비교를 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 # 가..