깡뇽

Day9 DF/BFS 문제풀기 - 음료수 얼려 먹기(난이도 중하) N X M 크기의 얼음 틀에 뚫린 부분은 0, 칸막이가 있는 부분은 1로 표시되며 구멍이 뚫린 부분은 상, 하, 좌, 우로 붙어 있다면 연결되어 있다고 간주한다. 만들어지는 총 아이스크림의 개수 구하자. 첫째 줄: N과 M N줄 : 얼음 틀의 형태. 0 또는 1. 음료수 얼려 먹기 풀기 #솔루션 n, m = map(int, input().split()) ice = [] for i in range(n): ice.append(list(map(int, input()))) def dfs(x, y): # 범위 밖 if x = n or y = m: return False # 현재 노드가 아직 방문하지 않은 곳이면 if ice[x][y] == 0: i..

Day8 탐색(Search) : 많은 데이터 중에서 원하는 데이터를 찾는 과정 DFS/BFS는 대표적인 탐색 알고리즘. 스택 & 큐에 대한 이해가 필요. 자료구조(Data Structure) : 데이터를 표현, 관리, 처리하기 위한 구조 - push : 데이터 삽입 - pop : 데이터 삭제 - overflow : 수용 가능한 데이터의 크기를 넘은 상태에서 삽입 연산 수행 시 발생 - underflow : 자료구조에 데이터가 없는데 삭제 연산 수행 시 발생 스택(Stack) : FILO(First In Last Out). 선입후출. LIFO(Last In First Out). 후입선출. => 먼저 쌓은 것은 나중에 뺄 수 있고, 나중에 쌓은 것은 먼저 뺄 수 있음. - append() : 리스트 맨 뒤에..

(앨범에 수록된 곡에 포함되어 있는 저작권이 있는 멜로디의 개수) / (앨범에 수록된 곡의 개수) = 앨범에 포함되어있는 저작권이 있는 멜로디의 평균값 평균값은 반올림을 해서 정수로 표현 입력 : 앨범에 수록된 곡의 개수 & 앨범에 포함되어있는 저작권이 있는 멜로디의 평균값 출력 : 앨범에 수록된 곡에 포함되어 있는 저작권이 있는 멜로디의 개수 2914번 저작권 풀이 [시도1] 맞았습니다!! a, i = map(int, input().split()) b = (a * (i-1)) + 1 print(b)

Silver 2에 해당하는 문제이다. 수열의 크기와 수열을 이루는 값들이 입력되었을 때에 수열의 가장 긴 증가하는 부분 수열의 길이를 출력해야 한다. 11053번 가장 긴 증가하는 부분 수열 풀이 [시도1] 틀렸습니다 n = int(input()) numbers = list(map(int, input().split())) cnt = 0 for i in range(n): if i == 0: num = numbers[i] else: if num < numbers[i]: num = numbers[i] cnt += 1 else: continue print(cnt+1) 입력받은 numbers를 검사하면서 이전의 값과 비교해서 크면 카운트를 해주도록 코딩했는데 틀렸다... dp 개념을 사용해야 한다고 하는데.. 사..

Siver 4 레벨에 해당하는 문제이다. 이전에 풀었던 스택 문제와 같은 자료 구조 시리즈이다. 10845번 큐 풀이 [시도1] pypy3 맞았습니다!! import sys n = int(input()) queue = [] for i in range(n): say = sys.stdin.readline().rstrip() if 'push' in say: num = say.split() queue.append(num[-1]) elif say == 'pop': if len(queue) == 0: print(-1) else: print(queue[0]) queue = queue[1:] elif say == 'size': print(len(queue)) elif say == 'empty': if len(queue..

Day7 구현 문제풀기 - 게임 개발 (난이도 중) N X M 크기의 직사각형 맵에서 각 칸은 육지 또는 바다로 이루어져 있다. 캐릭터는 동서남북 중에 한 방향을 바라보고 있으며, 상하좌우로 육지로 움직일 수 있다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례로 갈 곳을 정함. 2. 캐릭터의 바로 왼쪽 방향에 아직 방문하지 않은 칸이 있으면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진함. 왼쪽 방향에 칸이 다 방문한 칸이면, 왼쪽 방향으로 회전만 하고 1단계로 돌아감. 3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 된 칸이면, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아감. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 ..

Siver 4 레벨에 해당하는 문제이다. 금방끝내고 싶어서 이 문제를 골랐는데 이상하게 더 많은 틀렸습니다를 만났다... 자료 구조 중에서 스택 구조를 경험해 볼 수 있는 문제이다. push를 하면 스택에 값을 넣고, pop는 스택의 맨 윗 값을 제거하며 반환하고, size는 스택의 크기를 알려주고, empty는 스택이 비워짐을 확인해주고, top은 스택의 맨 윗 값을 반환한다. 10828번 스택 풀이 [시도n] pypy3 맞았습니다!! import sys n = int(input()) stack = [] for i in range(n): say = sys.stdin.readline().rstrip() if 'push' in say: num = say.split() stack.append(num[-1])..

Day6 구현 문제풀기 - 왕실의 나이트 (난이도 하) 나이트가 8 X 8 좌표 평면에서 L자 형태로만 이동할 수 있을 때, 나이트의 이동 경로 경우의 수를 출력해야 한다. 행 위치는 1~8, 열 위치는 a~h로 표현한다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동 2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동 ex) 나이트의 위치 : a1 → 2가지 경우(1. c2 / 2. b3) 첫째 줄 : 나이트의 현재 위치 좌표 문자열 입력. 왕실의 나이트 풀이 from string import ascii_lowercase alphabets = list(ascii_lowercase) #알파벳 소문자 리스트 생성 n = input() w = alphabets.index(n[0]) + 1 #알파..

이코테 책의 그리디 파트에서 1이 될 때까지 문제를 풀고 난 이후에 이 문제를 발견해서 비슷하겠지 싶어서 도전해 보았다. 1463번 1로 만들기 풀이 [고민] n = int(input()) cnt = 0 while n != 1: if n % 3 == 0: n = n / 3 cnt += 1 else: if n % 2 == 0: n = n / 2 cnt += 1 else: n = n - 1 cnt += 1 print(cnt) 1이 될 때까지 문제를 풀었을 때는 2가지 경우여서 간단하게 풀 수 있었지만 이 문제는 단순히 횟수만 구해서는 안된다. 처음에는 너무 간단하네~ 하고 예제 입력 10을 넣었더니 3이 나와야하는데 4가 출력되었다. 10 -> 9 -> 3 -> 1로 3번 만에 가능하기 때문이다. 즉, 3으..

Day5 구현 → 완전 탐색(모든 경우의 수를 다 계산하는 방법), 시뮬레이션(문제에서 제시한 알고리즘을 차례대로 직접 수행) 파이썬 데이터의 개수(리스트의 길이) : 1,000 → 메모리 사용량 약 4KB 1,000,000 → 약 4MB 10,000,000 → 약 40MB 주의) 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 못 풀 수도 있음. 1초에 2,000만 번의 연산 수행 가능하다고 가정. 시간 제한이 1초, 데이터의 개수 100만 개인 문제는 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 풀어야 함. 예제1) 상하좌우 Q. N X N 크기의 정사각형 공간을 L(왼쪽)..

Day4 그리디 문제풀기 - 1이 될 때까지 (2018 E 기업 알고리즘 대회 기출 / 난이도 하) N이 1이 될 때까지 2개의 과정 중 하나를 반복해서 수행하고, 과정 수행의 최소 횟수를 출력해야 한다. 단, 2번 과정은 N이 K로 나누어떨어질 때만 수행할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 첫째 줄 : N(2≤N≤100,000), M(2≤k≤100,000) 자연수 입력. 공백 구분 N은 항상 K보다 크거나 같다. 1이 될 때까지 풀이 n, k = map(int, input().split()) cnt = 0 while True: #n이 1이 되면 반복문 중단 if n == 1: break #n이 1이 아닌 경우 else: #n이 k로 나누어 떨어지면 나눗셈 진행 if n % k..

Day4 그리디 문제풀기 - 숫자 카드 게임 (2019 국가 교육기관 코딩 테스트 기출 / 난이도 하) 주어진 룰을 지켜 가장 높은 숫자가 쓰인 카드 한 장을 뽑아야 한다. 1. 숫자 카드들은 N(행) X M(열) 형태로 배치된다. 2. 먼저 뽑을 카드가 있는 행을 선택한다. 3. 그다음 선택된 행에 있는 카드들 중 가장 낮은 숫자 카드를 뽑는다. 4. 즉, 처음에 카드를 고를 행을 선택할 때에 나중에 해당 행에서 가장 낮은 숫자의 카드를 뽑을 것을 미리 고려해서 최종적으로는 가장 높은 숫자의 카드를 뽑도록 해야 한다. 첫째 줄 : N, M 자연수 입력. 공백 구분 둘째 줄 : N개의 줄 입력. 카드에 적힌 숫자들 숫자 카드 게임 풀이 n, m = map(int, input().split()) numbe..