깡뇽

Day10 DFS/BFS 문제풀기 - 미로풀기 (난이도 중하) N X M 크기의 직사각형 미로에 갖혀 있는데 (1,1) 위치에서부터 (N,M) 출구까지 이동한다. 괴물이 있는 0, 괴물이 없는 1로 이루어진 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하자. 첫째 줄 : N(4≤N)과 M(M≤200) N줄 : M개의 정수(0 또는 1). 공백없이. 시작 칸과 마지막 칸은 항상 1 미로 탈출 풀이 #솔루션 from collections import deque n, m = map(int, input().split()) world = [] for i in range(n): world.append(list(map(int,input()))) direction = [(-1,0), (1, 0), (0, -..

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() : 리스트 맨 뒤에..

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

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..

Day3 그리디 문제풀기 - 큰 수의 법칙 (2019 국가 교육 기관 코딩 테스트 기출 / 난이도 하) 배열 안 N개의 숫자들 중에서 숫자들을 골라 M번을 더하여 가장 큰 수를 출력해야한다. 그런데 특정 인덱스 숫자가 연속 K번을 초과하여 더해질 수 없다. 첫째 줄 : N, M, K 자연수 입력. 공백 구분 둘째 줄 : N개의 자연수. 공백 구분 K는 항상 M보다 작거나 같다. 큰 수의 법칙 풀이 import sys n, m, k = map(int, sys.stdin.readline().split()) numbers = list(map(int, sys.stdin.readline().split())) numbers.sort() a = numbers[-1] #가장 큰 수 b = numbers[-2] #두 번..

Day2 그리디(greedy) = 탐욕적 = 현재에만 집중! 나중은 생각하지 않아! 그리디 알고리즘은 문제 출제의 범위가 넓어서 암기가 거의 불가능하므로 많은 유형의 문제들을 접해봐야 함. 문제 속에 숨어 있는 기준을 찾아서 접근해야 하고, 정렬 알고리즘과 함께 엮여서 자주 출제됨. 예제1) 거스름 돈 Q. 손님에게 거스름돈 N원을 가장 적은 수의 동전으로 주려면 어떻게 해야할까? A. 손님에게 가장 큰 화폐 단위부터 돈을 거슬러 주자. N = 1260일 때 500원, 100원, 50원, 10원짜리 동전 최소한의 개수로 거슬러 주기. n = 1260 count = 0 # 큰 액수의 돈부터 차례로 확인 coin_type = [500, 100, 50, 10] for coin in coin_type: coun..

오늘부터 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 보면서 알고리즘을 다시 더 깊게 공부하고, 티스토리에 알게된 점들을 정리해보려고 한다. 이 책을 예전부터 코딩 테스트 공부를 위해서 사야할까 고민하다가 결국 2학기 개강을 앞두고 사게 되었다. 전부 다 보지는 못하더라도 차근 차근 하나씩 이해하며 해나가는 것을 목표로 해보자. Day1 - 온라인 코딩 테스트 응시할 때에 온라인 IDE를 이용하게 된다면 소스코드가 'Public'과 같은 공개 설정으로 되어 있지는 않은지 확인해야한다! - 코드업 -> [문제] - [문제집]의 [기초 100제] 풀기 - 백준 온라인 저지 + solved.ac 확장 프로그램(문제 분류와 난이도 참고 가능) - 프로그래머스 -> 카카오 공채 문제 제공 - SW ..