문제 🥇[골드 4] 12851- 숨바꼭질4 풀이 수빈이의 현재 위치를 current , 수빈이의 시작 위치를 n, 동생의 위치를 m 으로 정하자. 숨바꼭질 2와 같게 똑같이 케이스를 n>m , m==n 일 경우는 BFS를 이용해서 굳이 계산하지 않는다. 남은 경우는 수빈이의 위치가 동생의 위치보다 작을 경우에 대해서 만 BFS를 이용해서 구하면 된다. 자료구조 queue를 이용하면 문제를 간단하게 해결할 수 있다. 일반적인 BFS와 같게, queue를 선언하고, 다음 도착지를 queue에 넣는다. 종료 조건은 동생 위치에 도착했을 때로 정한다. 그리고 Visited 배열을 선언해서, Visited 배열에 들어가는 값을, 현재 위치에 도착하기 위해서 출발한 위치로 정한다. 예를 들어서 3에서 출발해서 5에..
문제 🥇[골드 5] 12851- 숨바꼭질 3 풀이 수빈이의 현재 위치를 current , 수빈이의 시작 위치를 n, 동생의 위치를 m 으로 정하자. 숨바꼭질 2와 같게 똑같이 케이스를 n>m , m==n 일 경우는 BFS를 이용해서 굳이 계산하지 않는다. 남은 경우는 수빈이의 위치가 동생의 위치보다 작을 경우에 대해서 만 BFS를 이용해서 구하면 된다. Python에서 지원하는 Dequeue를 사용해서 문제를 해결 했다. 현재 위치를 currnet라고 하면 current * 2 의 위치로 이동할 경우는 Dequeue의 맨 앞쪽에 넣고, current+1, current-1의 경우는 Dequeue의 맨 뒤쪽에 넣었다. 그리고 Visited 배열을 선언해서, 몇 초 만에 도착했는지 기록했다. Visited[..
문제 🥇[골드 5] 12851- 숨바꼭질2 풀이 BFS를 응용하면 된다. 풀기 전에 몇 가지 케이스에 대해서 분리해서 계산하면 더 효율적인 방법을 사용할 수 있다. 1) N(수빈이의 위치) 보다 K(동생의 위치)가 작을 경우(N>K) 수빈이가 n+1 칸이나 n*2 칸으로 이동하는 경우의 수는 최소 시간을 구하는데 의미가 아예 없다. 따라서 이 경우에는 -1로만 움직였때 동생의 위치로 도착하는 수를 구하면 된다. 즉 N-K번 회 움직이면 동생을 찾을 수 있고, 1가지의 경우의 수만 존재한다. 2) N == K 일 경우 0번 움직이고, 이 경우는 1가지만 있다. 3) N < K 일 경우 이 경우 BFS를 이용해서 푼다. 이 문제를 풀기 위해서 , M번째에 도착하는 위치를 리스트로 넣어서 통으로 큐 에다가 넣..
문제 🥈[실버 1] 1303- 전쟁-전투 풀이 DFS 혹은 BFS를 이용하면 된다. 뭉쳐있는 W에 해당하는 병사 , B에 해당하는 병사수를 DFS/BFS를 이용해서 각각 구하고 제곱하면 전투력을 쉽게 구할 수 있다. 코드 #전쟁 [Silver 1] import sys global army_sum def add_battle_power(current_row,current_col,row,col,army_map,army): global army_sum army_sum = army_sum + 1 army_map[current_col][current_row] = 0 d_row = [0,0,1,-1] d_col = [1,-1,0,0] for i in range(4): n_col = d_col[i] + current_..
문제 🥇[골드 5] 14719 - 빗물 풀이 기본적인 아이디어는 다음과 같다. 맨 처음 원래 배열에서 가장 큰 숫자의 위치를 찾는다. (만약 가장 큰 숫자의 값이 여러개일 경우 맨 왼쪽에 위치한 숫자와 오른쪽에 위치한 숫자의 위치를 찾아서 flag_index 배열에 기록한다. 예시에서는 3번째에 있는 8이 가장 큰 숫자이고, 제일 왼쪽에 있다. 이럴 경우 3번째에 있는 8보다 왼쪽에 있는 수 중에서 왼쪽에 있는 제일 큰 수를 찾아서 flag_index에 기록한다. 위의 방법이, 제일 큰 수가 제일 왼쪽에 올 때 까지 반복한다. 예시의 경우 0번째 배열부터 0번째 배열을 검사하고 1이 가장 큰 수이므로아래와 같은 경우에서 반복 조건이 끝난다. 또 가장 오른쪽에 있는 8은 7번째에 있는 숫자이다. 이 경우 ..
문제 🥈[실버2] 2504 - 괄호의 값 풀이 스택을 이용하면 괄호의 값 문제를 간단하게 구현할 수 있다. 알고리즘의 기본적인 아이디어는 다음과 같다 . 빈 스택을 하나 선언한다. '(' 혹은 '[' 가 들어오는 경우에는 스택에 push 한다. ')' 이 들어올 경우 '('이 나올 때 까지 pop을 한다. ']' 이 들어올 경우 '['이 나올 때 까지 pop을 한다. pop을 하면서 내부의 숫자를 연산한다. 코드 # 괄호의 값 [Silver 2] import sys bracket = str(sys.stdin.readline().strip()) bracket = list(bracket) stack = [] while(len(bracket)>0): a = bracket.pop(0) if(a == '(' or..
문제 🥈[실버1] 14888 - 연산자 끼워넣기 풀이 문제를 읽어보면 숫자의 최대 개수가 11개임을 알 수 있다. 파이썬으로 알고리즘을 풀 경우 대부분 연산이 1억 번 내외로 일어나면 통과이다. 만약 최대 숫자 개수에서 모든 경우의 수를 계산한다고 단순하게 생각했을 때, 총 10^4개의 경우의 수가 생긴다. 이런 경우 알고리즘을 짤 때, 전체 탐색을 이용해서 알고리즘을 짜도 무관하다. 전체 탐색으로 알고리즘을 구현할 경우에, 재귀 함수를 이용해서 간단하게 구현 할 수 있다. 메모리를 효율 적으로 사용할 수 있는 방법이 있겠지만, 이번에 알고리즘을 짤 때는 미처 고려하지 못했다.( 문제를 푸는 데는 지장은 없다. ) 아이디어는 다음과 같다. max와 min을 global 변수로 지정한다. 숫자를 담은 배열..
문제 프로그래머스 : 상위 n개 레코드 풀이 ORDER BY를 이용해서 DATETIME column 기준으로 정렬 후 LIMIT를 이용해서 조회하는 개수를 제한 할 수 있습니다. LIMIT 뒤에 숫자를 작성하여 조회 범위를 제한 할 수 있습니다. LIMIT 구문의 사용 방법은 아래와 같습니다. LIMIT 1 : 첫 번째 값부터 1개 까지의 정보를 조회 LIMIT 8, 10 : 8번째부터 10번째 까지의 정보 조회 코드 SELECT NAME FROM ANIMAL_INS ORDER BY DATETIME ASC LIMIT 1 출력 결과
문제 프로그래머스 : 여러 기준으로 정렬하기 풀이 ORDER BY를 이용해서 다중정렬을 사용할 수 있습니다. ORDER BY를 사용할 경우 왼쪽의 조건부터 정렬됩니다 예를 들어서 ORDER BY column_1 ASC , column_2 ASC 를 작성하면 column_1을 기준으로 오름차순 정렬을 하고 column_1이 같은 값들만 column_2를 기준으로 다시 오름차순 정렬을 하게 됩니다. 코드 SELECT ANIMAL_ID,NAME,DATETIME FROM ANIMAL_INS ORDER BY NAME ASC, DATETIME DESC 출력 결과
문제 프로그래머스 : 동물의 아이디와 이름 풀이 모든 레코드 조회하기와 따로 SELCET하는 column을 지정해 주는 부분을 제외하고는 거의 비슷한 문제 입니다. 마찬가지로 SELECT와 ORDER BY를 이용하면 간단하게 해결할 수 있습니다. 코드 SELECT ANIMAL_ID,NAME FROM ANIMAL_INS ORDER BY ANIMAL_ID ASC 출력 결과
