꿈꾸는 개발자의 devLog

스택 - 선입후출 (처음에 들어간게 제일 나중에 나옴) --> pop() 사용, append()로 스택에 입력 가능 큐 - 선입선출 --> popleft() 사용, append()로 큐에 입력 가능 큐 사용시 deque 사용 [예제] from collections import deque queue = deque() ## deque 라이브러리 사용 queue.reverse() ## 큐를 역순으로 바꾸기 ## 해당 코드는 기본적으로 외워 놓는 것이 좋음 근데 리스트로 선언해도 됨!! DFS (Depth-First Search, 깊이 우선 탐색) 위와 같은 트리가 있다는 가정하에, DFS가 동작한다면 어떻게 동작할 까? - DFS는 순서와 상관없이 처리해도 됨 - 코딩 테스트에서는 번호가 낮은 순서부터 처리하..

이 문제는 처음에 문제를 이해하기 약-간 어려웠다 그리고, 이런 유형의 문제는 풀어봤는데 항상 방향이 헷갈려서... 근데 하다가 먼가 꼬여서 반복문 탈출을 못하길래 해설코드 참고해서 풀었당 해설코드에서 반은 맞고 반은 틀렸다!! 잘 기억하자 이런 유형의 문제를 ^_^ [예제] 게임 개발 - NxM크기의 직사각형, 각각의 칸은 육지 또는 바다 - 맵의 각 칸은 (A,B)로 나타내며 A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수 (즉, 행렬에서의 위치값이라고 생각하면 됨) - 캐릭터는 상하좌우 이동 가능, 바다 공간에는 이동 불가능 * 캐릭터 움직임 매뉴얼 * 1. 현재 위치, 현재 방향 기준으로 왼쪽방향 (반시계 방향)으로 갈 곳을 정함 2. 왼쪽 방향에 가보지 않은 칸이 존재한..

[예제] 왕실의 나이트 - 왕실 정원은 8X8 좌표 평면 - 나이트는 L자 형태로만 이동 가능 1. 수평으로 두 칸, 수직으로 한 칸 2. 수직으로 두 칸, 수평으로 한 칸 - 행 위치는 1~8로 표현, 열 위치는 a~h로 표형 예시) 만약, a1에 위치한다면? (0,0)에 위치한다는 뜻 1. 오른쪽으로 두 칸 이동 후 아래로 한 칸 이동 (c2) 2. 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동 (b3) 이렇게 해서 현재 위치 입력 시 움직일 수 있는 경우의 수를 구하는 문제 여기서 포인트! 사실 전체 탐색 할 수 있는 경우의 수는 최대 8가지 경우의 수이다. 수평으로 2칸씩 옮기고, 수직으로 한 칸 수직으로 2칸, 수평으로 한 칸 요 방향은 사실 상 순서에 상관없이 현재 좌표에 각각 +2, -2 이..

파이썬에서 리스트 크기 [int형 데이터의 개수에 따른 메모리 사용량] 1천 -> 4KB 1백만 -> 4MB 1천만 -> 40MB [예제2] 시각 정수 N 입력 시, 00:00:00 ~ N:59:59 까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 문제 N이 23인 경우에 모든 경우의 수는 86,400개 -> 이는 10만개도 안되는 경우의 수 이기 때문에 문제에서 제한하는 메모리 제한 용량이 128MB를 넘지 않음 --> 즉, 시간 제한 2초 안에 해결 할 수 있음 # # ##### n = int(input()) cnt = 0 for i in range(n+1): for j in range(60): for m in range(60): if '3' in str(m)+str(j)+s..

구현 - 완전 탐색, 시뮬레이션 대표적인 문제 - 상하좌우, 시각 [예제] 상하좌우 - NxN 크기의 정사각형 공간에서 (1,1) 좌표에서 시작 - 상,하,좌,우 한 칸 씩 이동 가능 - 공간밖을 벗어나면 무시 - 최종적으로 이동한 장소의 좌표 출력 처음에 해당 예제를 봤을 때, 지도 크기만큼의 배열을 만들어야 하는 줄 알고 좌표 인덱스를 편하게 설정하려고 시작점을 0,0으로 설정하였음 (근데 굳이 그렇게 안해도 됨) 그리고 상하좌우 탐색하는 문제가 아직까지 어색한 이유가 4방향 다 돌면 시간이 터지지않을까? 하는 걱정이 앞서는데 해당 유형의 문제를 보자마자 상하좌우 기본으로 탐색하자는 마인드를 머리에 새겨야겠다 일단 내가 푼 방법은 다음과 같다. - 상하좌우 방향으로 이동할때의 좌표값을 지정하고 방향을..

Greedy 알고리즘 마지막 예제 어떠한 수 N이 1이 될 때까지 다음 두 가지 과정을 반복 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 예시 : N이 17, K=4 인 경우 N의 변화 : 17--> 4--> 1 4로 두 번 나누면 1이 된다 만약에 이 알고리즘에 대해 모른 상태로 문제를 봤다면, 문제가 주어지자마자 할 나의 생각은 하.. 이거 또 경우의 수 다 따져야 하는건가..? 어느세월에 다하지? 그럼 무조건 시간 초과인데.. 하면서 우울해 했을 것이다 그런데 그래도 알고리즘의 개념이라도 알아내서 그런가 이번에는 관점이 달랐다 보자마자 든 생각은 바로 "엥 당연히 나누는게 더 빨리 줄어 들 것 같은데? 1은 마지막에 빼도 되지 않나? " 이 생각이였다. 이 생각을 가진 채로 해설을 보자마자 내..

두번째 예제 [숫자 카드 게임] - NxM 형태로 숫자 카드들이 놓여짐 - N:행의 개수, M:열의 개수 - 행마다 카드를 뽑고, 처음에 카드를 뽑은 이후에 해당 행에서 가장 낮은 숫자 카드를 뽑아야 함 [입출력 예시] 입력 출력 3 3 3 1 2 4 1 4 2 2 2 2 2 4 7 3 1 8 3 3 3 4 4 * 내가 생각해낸 해결 방법 먼저, 2차원 행렬을 입력 받음 행마다 반복문을 돌면서 (1차원 반복문) 행마다 sort를 수행하고 가장 뒤에 위치한 (가장 작은 숫자)를 추출 그리고 행마다의 가장 작은 숫자들을 변수에 저장해놓고, 다음행에 갔을 때 이전 작은 숫자보다 크지만 해당 행에서는 작은 숫자인 경우 다시 (가장 작은 숫자) 변수에 저장함 - 해당 방법에서의 문제점? 행마다 sort를 진행하므..

그리디 알고리즘 - 욕심부리면서 현재 기준으로 당장 눈앞에 좋은 것만 고르는 알고리즘 - 문제에서 "가장 큰/작은 순서대로" 와 같이 현재 기준에 좋은 것을 고르게 하라는 힌트를 제시함 [예제] 거스름돈 거스름돈으로 사용할 500원, 100원, 50원, 10원 거스름돈이 N원일 때, 거슬러 줘야할 동전의 최소 개수 N은 항상 10의 배수 --> 가장 큰 화폐 단위 부터 돈을 거슬러 줌 [예제] 큰 수의 법칙 배열의 크기 N, 숫자가 더해지는 횟수 M, 연속 더해지는 수 K 2,4,5,4,6 (M=8, K=3) 6+6+6+5+6+6+6+5 = 46 3,4,3,4,3 (M=7, K=2) 4+4+4+4+4+4+4 = 28 먼저, 입력 받은 배열을 오름차순으로 정렬 가장 첫번째로 큰 숫자를 K번 만큼 더하고 두..