깡뇽

- 문제직사각형 격자 미로에서 탈출하려고 함. 각 칸은 통로 또는 벽. 벽은 통과 불가능하며, 통로 중 한 칸에는 미로 탈출 문이 존재. 그러나, 문은 레버를 당겨야만 열 수 있으며, 레버도 통로들 중 한 칸에 존재.즉, 출발 지점에서 먼저 레버 칸으로 이동해서 레버 당긴 후에 미로 탈출 문 칸으로 이동해야 함.아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있으며, 미로 한 칸 이동은 1초 소요.최대한 빠르게 미로를 빠져나가는데 걸리는 시간 구하기. - 입력 문자열 배열 maps : 미로 - 출력탈출에 필요한 최소 시간 리턴(단, 탈출 불가능 시에는 -1 리턴) - 제약 사항5 (S : 시작 / E : 출구 / L : 레버 / O : 통로 / X : 벽)시작 지점과 출구, 레버는 항상 다른 ..

문제 : 1년 동안 각 달의 수영장 이용 계획을 세우고 가장 적은 비용으로 수영장을 이용할 수 있는 방법 찾기 1. 1일 이용권 : 하루 이용 가능. 2. 1달 이용권 : 한 달 이용 가능. 매달 1일부터 시작. 3. 3달 이용권 : 연속 세 달 이용 가능. 매달 1일부터 시작. (11월, 12월, 다음해 1월 사용 불가능) 4. 1년 이용권 : 일 년 이용 가능. 매년 1월 1일부터 시작. - 입력 테스트 케이스 T 1일 이용권 요금, 1달 이용권 요금, 3달 이용권 요금, 1년 이용권 요금 1월~12월 이용 계획 - 출력 수용장 이용 계획대로 진행했을 때 가장 적게 지출하는 비용 - 제약 사항 10 ≤ 이용권 요금 ≤ 3,000 각 달의 이용 계획은 각 달의 마지막 일자보다 크지 않음 문제 이해 1월..

문제 : N * N 크기의 부지에 최대한 긴 등산로 만들기 1. 등산로는 가장 높은 봉우리에서 시작. 2. 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결. (높이가 같거나 낮은 지형이거나 대각선 방향 연결 불가능) 3. 한 곳을 골라 최대 K 깊이 만큼 지형 깎기 공사 가능. - 입력 지도 크기 N, 최대 공사 가능 깊이 K N * N의 지도 정보 - 출력 만들 수 있는 가장 긴 등산로의 길이 - 제약사항 3 ≤ N ≤ 8, 1 ≤ K ≤ 5, 1 ≤지형의 높이 ≤ 20 가장 높은 봉우리 최대 5개 지형은 정수 단위로만 깎기 지형 높이 1보다 작게 만들기 가능 문제 이해 N * N 크기의 지도에서 등산로를 만들고, 그 중에서 가장 긴 등산로의 길이를 찾자! 접근 방법 DFS 사용해서 등산로를..

"2115. [모의 SW 역량테스트] 벌꿀채취"에 기반을 두는 문제. 문제 : N개의 벌통이 있는데, 각 벌통에 있는 꿀의 양으로 부터 벌꿀을 채취해 얻을 수 있는 최대 수익 알아내기 1. 꿀은 최대 C까지만 채취 가능 2. 서로 다른 벌통에서 채취한 꿀이 섞이지 않도록 하나의 벌통에서 채취한 꿀은 하나의 용기에 담기 3. 하나의 벌통에서 꿀 채취할 때, 한 번에 모든 꿀을 채취 4. 채취한 꿀을 팔 때, 하나의 용기 속 꿀의 양이 많을수록 상품가치가 높고 각 용기의 꿀 양을 제곱만큼 수익 발생 ex) 6, 1, 8 만큼 꿀이 담긴 용기 3개를 판매하면 (6*6) + (1*1) + (8*8) = 36 + 1 + 64 = 101 수익이 생김 - 입력 테스트 케이스 개수 T T줄 - 벌통 크기 N, 꿀 채취..

입력 1. input() 활용 1) n과 m에 각각 숫자가 할당되고, m번 반복하여 숫자행이 입력 n, m = map(int, input().split()) numbers = [] for _ in range(m): numbers.append(list(map(int, input().split())) 활용 2) n개의 숫자만큼 숫자들 여러 줄(엔터) 입력 n = int(input()) numbers = [int(input()) for _ in range(n)] 활용 3) 값들이 한 줄로(스페이스바) 입력 numbers = input().split() 2. sys.stdin.realine() 사용할 때, import sys를 해야 함. 기본으로 \n가 포함된다는 것을 유념. -> sys.stdin.readli..

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