동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다. 이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.
출력
첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.
코드
# 말이 되고픈 원숭이
fromcollectionsimportdequek=int(input())w,h=map(int,input().split())graph=[list(map(int,input().split()))for_inrange(h)]h_dx=[-2,-2,-1,1,2,2,1,-1]h_dy=[-1,1,2,2,1,-1,-2,-2]dx=[-1,1,0,0]dy=[0,0,-1,1]visited=[[[-1]*(k+1)for_inrange(w)]for_inrange(h)]defbfs():queue=deque([(0,0,0)])visited[0][0][0]=0whilequeue:x,y,z=queue.popleft()ifx==h-1andy==w-1:returnvisited[x][y][z]foriinrange(8):nx=x+h_dx[i]ny=y+h_dy[i]if(0<=nx<h)and(0<=ny<w)andz+1<=k:ifvisited[nx][ny][z+1]==-1andgraph[nx][ny]==0:visited[nx][ny][z+1]=visited[x][y][z]+1queue.append((nx,ny,z+1))foriinrange(4):nx=x+dx[i]ny=y+dy[i]if(0<=nx<h)and(0<=ny<w):ifvisited[nx][ny][z]==-1andgraph[nx][ny]==0:visited[nx][ny][z]=visited[x][y][z]+1queue.append((nx,ny,z))return-1print(bfs())
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예
participant
completion
return
["leo", "kiki", "eden"]
["eden", "kiki"]
"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]
["josipa", "filipa", "marina", "nikola"]
"vinko"
["mislav", "stanko", "mislav", "ana"]
["stanko", "ana", "mislav"]
"mislav"
입출력 예 설명 예제 #1 “leo”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다. 예제 #2 “vinko”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다. 예제 #3 “mislav”는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
코드
#완주하지 못한 선수
defsolution(p,c):p.sort()c.sort()foriinrange(len(c)):ifp[i]!=c[i]:returnp[i]exit(0)returnp[len(c)]
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.
첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
두 번째(1번), 세 번째(2번) 폰켓몬을 선택
첫 번째(1번), 네 번째(3번) 폰켓몬을 선택
첫 번째(2번), 네 번째(3번) 폰켓몬을 선택
이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.
입출력 예
코드
#프로그래머스 해시 포켓몬
defsolution(nums):length=len(nums)//2nums=set(nums)iflength<=len(nums):answer=lengthelse:answer=len(nums)returnanswer
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
코드
x=int(input())d=[0]*1000001foriinrange(2,x+1):d[i]=d[i-1]+1# 기본적으로 1을 뺐을때 가장 작은횟수라 가정
ifi%2==0:d[i]=min(d[i],d[i//2]+1)ifi%3==0:d[i]=min(d[i],d[i//3]+1)print(d[x])
지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다. 2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다. 2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 바이러스가 퍼진 뒤의 모습은 아래와 같아진다. 2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다. 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다. 빈 칸의 개수는 3개 이상이다.
눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 그림 1과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 그림 2와 같이 3개의 분리된 영역으로 나누어지게 된다. 그림 2와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.
출력
첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.
코드
#영역 구하기
importsysinput=sys.stdin.readlinesys.setrecursionlimit(10**9)m,n,k=map(int,input().rstrip().split())graph=[[0]*nfor_inrange(m)]for_inrange(k):y,x,y2,x2=map(int,input().rstrip().split())foriinrange(x,x2):forjinrange(y,y2):graph[i][j]=1#print(graph)
cnt=1dx=[-1,1,0,0]dy=[0,0,-1,1]defdfs(x,y):globalcntgraph[x][y]=1foriinrange(4):nx=x+dx[i]ny=y+dy[i]if(0<=nx<m)and(0<=ny<n)andgraph[nx][ny]==0:cnt+=1dfs(nx,ny)result1=0result2=[]foriinrange(m):forjinrange(n):ifgraph[i][j]==0:result1+=1dfs(i,j)result2.append(cnt)cnt=1print(result1)print(' '.join(map(str,sorted(result2))))
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 그림과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
코드
n=int(input())# 컴퓨터 수
m=int(input())# 네트워크 수
graph=[[0]*(n+1)for_inrange(n+1)]visited=[0]*(n+1)for_inrange(m):x,y=map(int,input().split())graph[x][y]=ygraph[y][x]=xcnt=0defdfs(start,graph,visited):visited[start]=Trueforiingraph[start]:ifi!=0andvisited[i]==False:globalcntcnt+=1dfs(i,graph,visited)returncntprint(dfs(1,graph,visited))
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
코드
```py #미로탐색 from collections import deque def bfs(x,y): queue=deque() queue.append((x,y)) #print(queue) while queue: x,y=queue.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] if nx<0 or nx>=n or ny<0 or ny>=m: continue if graph[nx][ny]==0: continue if graph[nx][ny]==1: graph[nx][ny]=graph[x][y]+1 queue.append((nx,ny)) return graph[n-1][m-1]
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
코드
```py from collections import deque n,m,v=map(int,input().split()) graph=[[0](n+1) for _ in range(n+1)] visited=[0](n+1) graph2=[[0](n+1) for _ in range(n+1)] visited2=[0](n+1) for _ in range(m): x,y=map(int,input().split()) graph[x][y]=y graph[y][x]=x graph2[x][y]=y graph2[y][x]=x
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호(“()”) 와 대괄호(“[]”)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
입력
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호(“( )”) 대괄호(“[ ]”)등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 점 하나(“.”)가 들어온다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 “yes”를, 아님 “no”를 출력한다.
코드
```py #균형잡힌 세상 while(True): a=input() s=[] tmp=True if a==’.’: break for i in a: if i ==’(‘ or i==’[’: s.append(i) elif i==’)’: if not s or s[-1]==’[’: tmp=False break else: s.pop() elif i==’]’: if not s or s[-1]==’(‘: tmp=False break else: s.pop() if tmp==True and len(s)==0: print(“yes”) else: print(“no”)
슈퍼 마리오 앞에 10개의 버섯이 일렬로 놓여져 있다. 이 버섯을 먹으면 점수를 받는다. 슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다. 중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다. 마리오는 받은 점수의 합을 최대한 100에 가깝게 만들려고 한다. 버섯의 점수가 주어졌을 때, 마리오가 받는 점수를 출력하는 프로그램을 작성하시오.
입력
총 10개의 줄에 각각의 버섯의 점수가 주어진다. 이 값은 100보다 작거나 같은 양의 정수이다. 버섯이 나온 순서대로 점수가 주어진다.
출력
첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다.
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.
어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다. 예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다. 각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.
입력
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.
어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. ‘radar’, ‘sees’는 팰린드롬이다. 수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다.
길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.
입력
첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.
출력
A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 “치킨 거리”라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자. 0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 2 0은 빈 칸, 1은 집, 2는 치킨집이다. (2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다. (5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다. 이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다. 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + … + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
코드
#나이트의 이동
fromcollectionsimportdequeimportsysinput=sys.stdin.readlinedx=[-2,-2,-1,1,2,2,1,-1]dy=[-1,1,2,2,1,-1,-2,-2]defbfs(sx,sy,ex,ey):q=deque()q.append([sx,sy])check[sx][sy]=1whileq:a,b=q.popleft()ifa==exandb==ey:print(check[ex][ey]-1)returnforiinrange(8):x=a+dx[i]y=b+dy[i]if0<=x<nand0<=y<nandcheck[x][y]==0:q.append([x,y])check[x][y]=check[a][b]+1a=int(input())for_inrange(a):n=int(input())sx,sy=map(int,input().split())ex,ey=map(int,input().split())check=[[0]*nforiinrange(n)]bfs(sx,sy,ex,ey)
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
카드의 개수 N과 숫자M 변수를 선언하고 입력을 받음 카드중에서 세개의 값을 합해서 그 값을 맥스값에서 뺀 차가 최소이면 M에 가장 가까운 합이라는 뜻이기 때문에 이런 방식으로 접근하기 위해 최댓값 변수 max를 999999로 선언 N개의 배열을 입력 받기 위해 카드 N개의 숫자 값을 입력 받습니다 그리고 아까 말한 맥스값에서 sum값을 뺀 값의 최소를 구하기 위해 sum과 result 변수를 선언 그리고 첫번째 for문은 첫번째 장 카드 부터 N-2장 카드까지 두번째 for문은 첫번쨰 for문의 다음 장 카드부터 N-1장 카드까지 세번째 for문은 두번째 for문의 다음 장 카드부터 N장 카드까지 각 for문에 해당하는 카드의 숫자를 더해 sum에 저장하고 이 숫자M에서 sum을 뺀 값이 max보다 작고 0이상이면 이전에 구했던 sum값보다 M에 더 가깝다는 뜻이기 때문에 max를 M-sum으로 저장하고 result를 sum에 저장합니다 그리고 결과를 출력합니다
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
입력
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다. zzzzzzz
길동이는 N x M 크기의 직사각형 형태의 미로에 갇혔습니다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 합니다. 길동이의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있습니다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있습니다. 미로는 반드시 탈출할 수 있는 형태로 제시됩니다. 이떄 길동이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하세요. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산합니다.
입력 조건
첫째 줄에 두 정수 N,M(4<=N, M<=200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어집니다. 각각의 수들은 공백 없이 붙어서 입력으로 제시됩니다. 또한 시작 칸과 마지막 칸은 항상 1입니다.
출력 조건
첫째 줄에 최소 이동 칸의 개수를 출력합니다.
입력 예시
5 6 101010 111111 000001 111111 111111
출력 예시
10
코드
```py #미로 탈출 from collections import deque def bfs(x,y): queue=deque() queue.append((x,y)) while queue: x,y=queue.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] if nx<0 or nx>=n or ny<0 or ny>=m: continue if graph[nx][ny]==0: continue if graph[nx][ny]==1: graph[nx][ny]=graph[x][y]+1 queue.append((nx,ny)) return graph[n-1][m-1]
N x M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요.
입력 조건
첫 번째 줄에 얼음 틀의 세로 길이 N과 가로길이 M이 주어집니다. (1<=N, M<=1000) 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어집니다. 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1입니다.
출력 조건
한 번에 만들 수 있는 아이스크림의 개수를 출력합니다.
입력 예시
4 5 00110 00011 11111 00000
출력 예시
3
코드
```py #음료수 얼려 먹기 def dfs(x,y): if x<= -1 or x>=n or y<=-1 or y>=m: return False if graph[x][y]==0: graph[x][y]=1 dfs(x-1,y) dfs(x,y-1) dfs(x+1,y) dfs(x,y+1) return True return False
DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
코드
```py #DFS def dfs(graph,v,visited): visited[v]=True print(v,end=’ ‘) for i in graph[v]: if not visited[i]: dfs(graph,i,visited) #각 노드가 연결된 정보를 표현(2차원 리스트) graph=[ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7], ]
자기 자신을 다시 호출하는 함수 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있음 EX ) 팩토리얼 구현
코드
#팩토리얼
#반복
deffactorial_iterative(n):result=1# 1부터 n까지의 수를 차례대로 곱하기
foriinrange(1,n+1):result*=ireturnresult#재귀
deffactorial_reCursive(n):ifn<=1:return1returnn*factorial_reCursive(n-1)
EX ) 유킬리드 호제법 GCD(A,B) 이때 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자. 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다. GCD(192,162) => 1단계 : A=192 B=162 => 2단계 : A=162 B=30 => 3단계 : A=30 B=12 => 4단계 : A=12 B=6
코드
```py #유클리드 호제법 def gcd(a,b): if a % b==0: return b else: return gcd(b,a%b)
두 개의 배열 A와 B는 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산은 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것 N,K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오
코드
#두 배열의 원소 교체
n,k=map(int,input().split())a=list(map(int,input().split()))b=list(map(int,input().split()))a.sort()b.sort(reverse=True)foriinrange(k):ifa[i]<b[i]:a[i],b[i]=b[i],a[i]else:breakprint(sum(a))
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘 계수정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용가능 데이터의 개수가 N, 데이터(양수)중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장 계수정렬은 때에 따라서 심각한 비효율성을 초래할 수도 있음 EX) 데이터가 0과 999,999 단 2개만 존재하는 경우 => 데이터가 2개뿐이지만 배열은 백만개를 만들어야하므로 공간적으로 매우 비효율적 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있음 EX) 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적
코드
```py #계수 정렬 array=[7,5,9,0,3,1,6,2,9,1,4,8,0,5,2] count=[0]*(max(array)+1) for i in range(len(array)): count[array[i]]+=1
기준 데이터(피봇)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가짐 최악의 경우 O(N^2)의 시간 복잡도를 가짐 EX) 이미 정렬된 배열에 대해 첫 번째 원소를 피벗으로 삼을 때
코드
```py #퀵 정렬 1 array=[5,7,9,0,3,1,6,2,4,8] def quick_sort(array,start,end): if start>=end: return pivot=start left=start+1 right=end while(left<=right): while(left<=end and array[left]<=array[pivot]): left+=1 while(right>start and array[right]>=array[pivot]): right-=1 if(left>right): array[right],array[pivot]=array[pivot],array[right] else: array[left],array[right]=array[right],array[left] quick_sort(array,start,right-1) quick_sort(array,right+1,end) quick_sort(array,0,len(array)-1) print(array)
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 선택 정렬에 비해 일반적으로 더 효율적 첫 번째 데이터는 그 자체로 정렬이 되어 있다고 가정 삽입 정렬의 시간 복잡도는 O(N^2) 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작 => 최선의 경우 O(N)의 시간복잡도
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내는 것 구현 방식에 따라서 오차는 있지만 전체 연산 횟수 = N + (N-1) + (N-2) + .. + 2 이는 (N^2+N-2)/2 로 표현 가능 => 시간복잡도는 O(N^2)
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열{1,1,2,2,2,2,3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이문제는 시간 복잡도 O(log N)으로 알고리즘을 설계하지 않으면 시간초과 판정을 받습니다.
코드
```py #정렬된 배열에서 특정 수의 개수 구하기 from bisect import bisect_left, bisect_right def count_by_range(array, left_value, right_value): right_index=bisect_right(array,right_value) left_index=bisect_left(array,left_value) return right_index-left_index
오늘은 떡볶이 떡을 만드는 날입니다. 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 덕은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이고 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm만큼의 길이를 가져갑니다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만틈의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
코드
#떡볶이 떡 만들기
n,m=map(int,input().split())array=list(map(int,input().split()))start=0end=max(array)result=0while(start<=end):total=0mid=(start+end)//2forxinarray:ifx>mid:total+=x-midiftotal<m:end=mid-1else:result=midstart=mid+1print(result)
왕국의 왕실 정원은 체스판과 같은 8x8 좌표 평면입니다. 왕실 정원의 특정한 한 칸에 나이트가 서 있습니다. 나이트는 체스 나이트와 같이 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없습니다. 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하세요. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 포현하며, 열 위치를 표현할 때는 a부터 h로 표현합니다. c2에 있을 때 이동할 수 있는 경우의 수는 6가지입니다.
코드
#왕실의 나이트
a=input()x=int(a[1])y=int(ord(a[0]))-int(ord('a'))+1cnt=0#나이트가 이동할 수 있는 좌표
dx=[-2,-2,-1,1,-1,1,2,2]dy=[-1,1,-2,-2,2,2,-1,1]foriinrange(8):nx=x+dx[i]ny=y+dy[i]ifnx>=1andnx<=8andny>=1andny<=8:cnt+=1print(cnt)
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오 예를 들어 1을 입력했을 때 00시 00분 03초, 00시 13분 30초는 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다. 반면에 00시 02분 55초, 01시 27분 45초는 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각입니다.
여행가 A는 N x N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당합니다. 여행가 A는 상 하 좌 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L R U D 중 하나의 문자가 반복적으로 적혀 있습니다. L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위로로 한 칸 이동 D : 아래로 한 칸 이동 이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다. 예를 들어 (1,1)의 위치에서 L 혹은 U를 만나면 무시됩니다.
한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 ‘공포도’를 측정했는데, ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 길동이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 길동이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오. 예를 들어 N=5이고, 각 모험가의 공포도가 2 3 1 2 2 라고 가정하면 그룹 1에 공포도가 1 2 3 인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있습니다. 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 떄문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.
각 자리 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘x’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다. 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0+2)9)8)*4)=576 입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.
코드
#곱하기 혹은 더하기
S=input()result=int(S[0])foriinrange(1,len(S)):num=int(S[i])ifnum<=1orresult<=1:result+=numelse:result*=numprint(result)
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다
N에서 1을 뻅니다.
N을 K로 나눕니다. 예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요
#1이 될때 까지(답)
N,K=map(int,input().split())cnt=0whileTrue:# N이 K로 나누어 떨어지는 수가 될 때까지 빼기
target=(N//K)*Kcnt+=(N-target)N=target# N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
ifN<K:break# K로 나누기
cnt+=1N//=K# 마지막으로 남은 수에 대하여 1씩 빼기
cnt+=(N-1)print(cnt)
당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이며 N=1260이라 가정한다.
주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 EX ) 크러스컬 알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 ‘욕심내어’ 그 선분을 추가시킨다. KruskalMST(G)(입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m , 출력: 최소 신장 트리 T)
가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자.
T=∅ // 트리 T를 초기화시킨다.
while ( T의 선분 수 < n-1 ) {
L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다.
if (선분 e가 T에 추가되어 사이클을 만들지 않으면)
e를 T에 추가시킨다.
else // e가 T에 추가되어 사이클이 만들어지는 경우
e를 버린다. }
return 트리 T // T는 최소 신장 트리이다. 시간복잡도 = O(mlogm)
프림 알고리즘 주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, (n-1)개의 선분을 하나씩 추가시켜 트리를 만든다. 추가되는 선분은 현재까지 만들어진 트리에 연결시킬 때 ‘욕심을 내어서’ 항상 최소의 가중치로 연결되는 선분이다. PrimMST(G)(입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m, 출력: 최소 신장 트리 T )
그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p]=0으로 놓는다. // 배열 D[v]는 T에 있는 점 u와 v를 연결하는 선분의 최소 가중치를 저장하기 위한 원소이다.
for (점 p가 아닌 각 점 v에 대하여) { // 배열 D의 초기화
if ( 선분 (p,v)가 그래프에 있으면 )
D[v] = 선분 (p,v)의 가중치
else
D[v]=∞ }
T= {p} // 초기에 트리 T는 점 p만을 가진다.
while (T에 있는 점의 수 < n) { T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 vmin과 연결된 선분 (u,vmin)을 T에 추가한다. 단, u는 T에 속한 점이고, 점 vmin도 T에 추가된다.
프림 알고리즘은 임의의 점에서 시작하나, 다익스트라 알고리즘은 주어진 출발점에서 시작한다.
프림 알고리즘은 트리에 하나의 점 (선분)을 추가시킬 때 현재 상태의 트리에서 가장 가까운 점을 추가시키지만, 다익스트라의 알고리즘은 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정한다. ShortestPath(G, s)(입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m, 출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D)
배열 D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다. // 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다.
while (s로부터의 최단 거리가 확정되지 않은 점이 있으면) {
현재까지 s로부터 최단 거리가 확정되지 않은 각 점 v에 대해서 최소의 D[v]의 값을 가진 점 vmin을 선택하고, 출발점 s로부터 점 vmin까지의 최단 거리 D[vmin]을 확정시킨다.
s로부터 현재보다 짧은 거리로 점 vmin을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신한다. }
그리디 알고리즘 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불리기도 한다. 데이터 간의 관계를 고려하지 않고 수행과정에서 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 -> ‘근시안적’인 선택 EX ) 동전 거스름돈 문제 남은 액수를 초과하지 않는 조건하에 ‘욕심내어’ 가장 큰 액면의 동전을 취하는 것 CoinChange 의사코드(입력: 거스름돈 액수 W, 출력: 거스름돈 액수에 대한 최소 동전 수)
change=W, n500=n100=n50=n10=n1=0
while ( change ≥ 500 ) change = change-500, n500++
while ( change ≥ 100 ) change = change-100, n100++
시간복잡도 - 단위연산이 수행되는 횟수를 입력 크기에 대한 함수로 구하여 분석 알고리즘을 분석하는 표준 분석 : 모든경우 vs 그렇지 않은 경우 모든 경우 시간복잡도 분석 입력의 크기가 같을 경우, 입력의 값과 상관없이 항상 알고리즘의 성능이 같은 경우 EX ) 예: 배열의 수 더하기
단위연산: 총합을 계산하기 위한 덧셈
입력: n, 배열에 있는 항의 개수
T(n) = n
예: 교환정렬
단위연산: S[j]와 S[i]의 비교
입력: n, 배열에 있는 항의 개수
T(n) = (n-1)+(n-2)+…+1 = n(n-1)/2
예: 행렬곱셈
단위연산: 가장 안쪽 for 루프에 있는 곱셈
입력: 행과 열의 수 -> n
T(n) = n X n X n = n^3
그렇지 않은 경우 시간복잡도
최악의 경우 시간복잡도
평균의 경우 시간복잡도 실제 값이 평균에 크게 벗어나지 않는 경우에만 평균을 “전형적”이다라고 할 수 있음 EX) 9월 15일의 서울 평균 최고 기온 -> 전형적일 수 있음 EX) 연평균 소득 -> 전형적이지 않을 수 있음
최선의 경우 시간복잡도
차수(order) 알고리즘의 복잡도를 표시하기 위하여 사용하는 표기법 시간복잡도가 2차인 알고리즘은 입력 크기가 충분히 크면 각 알고리즘에서 단위연산의 수행시간과 무관하게 시간복잡도가 n인 것보다 우수할 수 없다.
시간복잡도 빅오 정의 : 주어진 복잡도 함수 f(n)에 대하여, O(f(n))은 n ≥ N을 만족하는 모든 n에 대하여 부등식 g(n) ≤ c × f (n) 을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다. 결론적으로 해당 알고리즘은 big O보다 더 오래걸릴 수 없다는 최악의 경우의 알고리즘이다. 현실에서는 항상 최악의 경우를 생각해야 하기 때문에, 흔히 빅오 표기법을 많이 사용한다.
빅오메가 정의 : 주어진 복잡도 함수 f(n)에 대하여, (f(n))은 n ≥ N을 만족하는 모든 n에 대해 부등식을 g(n) ≥ c × f (n) 을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다. 결론적으로 해당 알고리즘은 빅오메가보다 더 빠를 수 없다는 최선의 경우의 알고리즘이다.
순회(Traversal)란 노드를 삽입, 삭제, 검색하기 위해 트리 내부를 이리저리 돌아다니는 작업을 말한다. 트리 자체가 재귀적으로 정의 되었기 때문에 트리의 순회 역시 재귀적이다. 순회의 종류에는 루트노드에 대한 작업이 어디에 박히느냐에 따라서 전위순회, 중위순회, 후위순회로 나뉘어진다.
전위순회
전위순회(Pre-order Traversal)는 하위트리의 루트노드에 대한 작업이 가장 먼저 일어난다. 전위순회의 전위(Pre-Order)란 말은 해당 노드에 대한 방문 작업이 재귀호출보다 앞서서(전위) 실행된다는 의미이다.
그림에서 트리를 전위순회하면서 노드 데이터를 출력하면 G,C,A,E,L이 된다. 먼저 함수를 호출하는 쪽에서 루트노드 G를 가리키는 포인터 R을 넘기면 이 R이 복사되어 T로 들어간다. 이 T를 T1이라 하면 이제 T1은 노드 G를 가리킨다. 함수가 실행되자마자 데이터 G를 일단 출력하고, G의 LChild를 넘기며 재귀호출한다. 이번에는 G의 LChild가 T로 복사되어 들어간다. 이 T를 T2라 하면 이제 T2는 G의 왼쪽 하위트리를 가리킨다. C를 루트로 하는 하위트리다. 재귀호출이 시작되자마자 C를 출력하고 C의 LChild가 T3로 복사되어 재귀호출한다. 이런식으로 순회를 반복하면 G,C,A,E,L순으로 출력이 됨을 알 수 있다.
중위순회
중위순회(In-order Traversal)는 Visit작업이 중간에 일어나는 순회를 말한다.
전위, 중위, 후위와는 별개로 레벨순회(Level-order Traversal)를 정의하기도 한다. 이 순서는 레벨 0에서 레벨 1로, 다시 레벨 2로 간다. 다시 말해, 트리의 위에서 아래로 진행하되, 같은 레벨에서는 왼쪽에서 오른쪽으로 진행한다. 그림을 레벨순회하면 G,C,L,A,E의 순서로 노드를 방문한다. 레벨순회에 해당하는 재귀호출은 존재하지 않으며 그래프 탐색 방법으로 말하자면 너비우선 탐색에 해당하는 것으로, 큐 구조를 사용하여 구현할 수 있다.
트리(Tree)비선형적, 계층적, 재귀적 구조를 가진 자료구조이다.(리스트와 스택, 큐는 선형적인 자료구조) 계층적으로 묘사될 수 있는 것은 무엇이든 트리로 나타낼 수 있다. 트리의 구성요소에 해당하는 A,B,…,F를 노드(Node)라 한다. B의 바로 아래 있는 E,F를 B의 자식노드(Child Node)라 한다. 반대로 B는 E,F의 부모노드(Parent Node)라 한다. 같은 부모 아래에서 자식노드 서로를 자매노드(Sibling Node)라 부른다. 예를 들어 B,C,D는 서로 자매노드며 E,F도 서로 자매노드이다. 주어진 노드의 상위에 있는 노드들은 조상노드(Ancestor Node)라 한다. 예를 들어 B,A는 F의 조상노드이다. 반대로 어떤 노드의 하위에 있는 노드를 후손노드(Descendant Node)라 한다. 예를 들어 B,E,F,C,D는 A의 후손노드다.
A처럼 부모가 없는 노드, 즉 원조격인 노드를 루트노드(Root Node)라 한다. 반대로 C,D,E,F처럼 자식이 없는 노드를 리프노드(Leaf Node)라 한다. 리프노드를 제외한 모든 노드를 내부노드(Internal Node)라 한다. 둘 이상의 자식노드를 가질 수 있는 트리를 일반트리(General Tree)라 하는 반면에, 최대 두 개까지의 자식노드를 가질 수 있는 트리를 이진트리(Binary Tree)라 한다.
주어진 트리의 부분집합을 이루는 트리를 하위트리(Subtree)라 한다. 위의 그림에서 B,E,F가 하나의 하위트리이며, 또 C 자체로서 하나의 하위트리이다. 트리의 레벨(Level)은 루트노드를 레벨0으로 하고 아래로 내려오면서 증가한다. 트리의 높이(Height)는 트리 내의 최대 레벨과 일치한다. 그림에서 트리의 높이는 3이며 정리하면 트리의 높이는 루트노드로부터 가장 먼 리프노드까지 가는데 필요한 연결(Link)개수를 뜻한다. 즉, 가장 먼 리프노드까지 가기 위해 중간에 지나야 하는 노드 수라고 할 수 있다. 트리의 높이를 공식으로 나타내면 트리의 높이=1+Max(왼쪽 하위트리의 높이, 오른쪽 하위트리의 높이)로 나타낼 수 있다.
트리에서 균형(Balance)을 말할 때가 있다. 여기서 균형이란 루트노드를 기준으로 왼쪽 하위트리와 오른쪽 하위트리 사이의 높이 차이를 말한다. 차이가 1 이하일 때 그 트리를 균형트리(Height Balanced Tree)라 한다. 이에 반해 완전 균형트리(Completely Height Balanced Tree)는 왼쪽, 오른쪽 하위트리 높이가 완전히 일치하는 트리를 말한다. 트리의 균형을 맞춰야하는 이유는 트리에서 데이터에 접근하기 위해 거쳐야하는 노드의 수가 레벨마다 하나인데, 데이터를 찾는데 거쳐야 하는 노드의 수가 적어지기 때문이다.(균형이 차이가 많이 나면 데이터에 접근하기 위해 거쳐야 하는 노드의 수가 매우 많아짐.)
너비우선 탐색(BFS, Breadth First Search))이란 문자 그대로 탐색 순서에 있어서 깊이보다는 폭을 우선적으로 취한다. 너비우선 탐색은 주어진 노드로부터 거리 1인 노드를 모두 방문하고, 다음 거기서부터 거리 1인 노드, 즉 원래의 노드로부터 거리 2인 노드를 방문하고, 다시 거리 3의 노드를 방문한다. 이런 특성으로 인해, 만약에 목적지를 찾는 문제라면 그 목적지까지 가는 최단경로를 찾을 수 있다. 거리가 짧은 순서로 목적지를 찾아가기 때문이다. 깊이우선 탐색이 스택을 사용한다면, 너비우선 탐색은 큐를 사용한다. 그림에서 탐색이 시작되면 일단 출발지인 A를 큐에 삽입한다. 다음, 큐 프런트인 A를 제거하면서 A에 인접한 B,G를 모두 큐에 삽입한다. 다음, 현재의 큐 프런트인 B를 제거하면서 B와 인접한 C,E를 삽입한다. 다시 현재의 큐 프런트인 G를 제거하면서 G와 인접한 H를 삽입한다. 이러한 작업을 반복하면서 큐에서 제거된 노드를 순차적으로 나열하면 그것이 너비우선 탐색 순서가 된다. 너비우선 탐색도 깊이우선 탐색과 마찬가지로 “목적지까지 가는 길이 있는가?”라는 문제 해결에 사용될 수 있다. 예를 들어 위 그림에서 “A에서 출발하여 K까지 가는 길이 있는가?”라는 질문에 탐색을 실시하면 결국 마지막에 큐가 비게 되므로 “그런 길이 없다.”라고 답할 수 있다. 반대로 “A에서 출발하여 F까지 가는 길이 있는가?”라는 질문이라면 F가 큐 프런트인 상태에서 “그런 길이 있다.”라고 답할 수 있다. 결론적으로, 안 가본 새로운 도시만 큐에 삽입하고 안 가본 도시가 없을 때까지 모든 도시를 조직적으로 하나씩 방문하는 소모적 탐색의 한 방법이다.
큐(Queue)란 쉽게 말해 기다리는 줄을 의미한다. 예를 들어 은행 창구 앞에 줄 서 있는 사람들, 공유된 프린터 하나를 사용하여 인쇄될 차례를 기다리는 파일 등이 예이다. 이들의 공통점은 스택과는 반대로 가장 먼저 넣은 것이 가장 먼저 빠져 나오는 것이 특징이다. 이를 선입선출(First In First Out)이라고 한다. 큐에서 줄의 맨 앞을 큐 프런트(Front), 맨뒤를 큐 리어(Rear)라 한다.
Add는 현재의 리어 바로 뒤에 새로운 데이터를 삽입하는 작업이고 Remove는 프런트에 있는 데이터를 가져오는 작업이다. 시각적으로 볼 때 큐에서의 Add와 Remove는 양쪽 끝에서 모두 사용된다.
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
n은 입력받을 숫자의 개수 cnt는 1부터 n까지 비교하기 위한 카운터(n까지 1씩 증가시킴) li는 n개의 숫자를 입력받아 저장할 리스트 tmp는 True와 False를 저장할 변수 result는 +와 -를 저장할 결과 리스트 for문에서 n번동안 num을 입력 받는다 이때 cnt가 num보다 작거나 같을때까지 li에 cnt를 PUSH시킨다. 그러면서 cnt는 1씩 증가 만약 li(스택)에 있는 마지막 원소가 num과 일치하면 POP을 해주고 result에 -를 추가해준다. 그렇지 않은 경우는 tmp를 False로 변경 만약 tmp가 False인 경우는 POP과 PUSH로 수열을 만들수 없다는 의미이므로 NO를 출력 그렇지 않으면 result의 원소를 차례대로 출력해준다.
정인이는 강남의 유명한 클럽 Top Root의 도어맨이다. 클럽의 사장은 정인이에게 클럽이 꽉찼을 때, 클럽에 있는 남자와 여자의 수는 거의 비슷해야 한다고 말해주었다. 사람들은 클럽이 문을 열기 전 부터 줄을 서 있는다. 클럽이 문을 열면, 한 명씩 직접 정인이가 입장시켜 준다. 정인이는 그들이 줄을 순서를 바탕으로 입장시켜 준다. 이때, 항상 첫 번째에 있는 사람을 입장시켜야 하는 것은 아니다. 정인이는 재량을 발휘하여 두 번째로 줄 서있는 사람을 첫 번째 사람보다 먼저 입장을 시켜줄 수 있다. 물론 이런 상황이 자주 발생하면 앞 사람이 매우 짜증이 날 것이고, 정인이에게 시비를 걸 수도 있다. 하지만, 정인이는 모든 싸움을 이길 수 있는 사람이기 때문에 이런 걱정은 하지 않아도 된다. 안타깝게도, 정인이는 이렇게 싸움은 잘하지만, 숫자 계산은 잘 하지 못한다. 정인이는 항상 클럽에 들어가있는 남자와 여자의 차이를 머리속에 계산하고 있어야 한다. 이 차이가 정인이가 기억할 수 있는 값보다 크게 된다면 남은 사람들은 클럽에 입장을 할 수 없게 된다. 줄을 서 있는 순서와 정인이가 기억할 수 있는 차이의 최댓값이 주어졌을 때, 클럽에 있는 사람의 수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X<100이 주어진다. 둘째 줄에는 줄을 서 있는 순서가 주어진다. W는 여성, M은 남성을 나타내며, 길이는 최대 100이다. 가장 왼쪽에 있는 글자가 줄의 가장 앞에 서 있는 사람의 성별이다.
a는 정인이가 기억할 수 있는 사람 차이의 수 b는 남자와 여자가 서있는 리스트 pop은 가장 뒤에 있는 원소부터 꺼내는 작업이므로 reverse를 통해 거꾸로 바꿔준다 그리고 mc와 wc는 각각 남자의 수와 여자의 수 먼저 스택에서 POP한 후 해당 사랑을 입장시키려 할 떄 차이가 a를 넘어가면 다시 스택에서 POP하여 두번째 사람의 성별을 확인 만약 두 번째 사람을 입장시킬 때 성별이 반대이며 a를 초과하지 않는다면 입장시키고 첫 번째 사람을 다시 스택에 PUSH 만약 두 번째 사람이 성별이 같다면 더 이상 입장할 수 없기 때문에 종료
깊이우선 탐색(DFS, Depth First Search))이란 문자 그대로 깊이를 우선적으로 추구하는 탐색이다. 길을 갈 수만 있다면 끝까지 깊숙이 가 보고, 거기서 길이 없으면 되돌아오는 방식이다. 그림에서 “노드 A에서 출발해서 노드 F로가능 경로가 존재하느냐?”라는 문제를 풀어보자. 이 문제를 해결하려면 A에서 출발하여 갈 수 있는 모든 곳을 다 가보는 수 밖에 없다. 계속 진행하다 보면 세가지 경우가 나온다.
목적지까지 제대로 간다.
어떤 도시로 갔는데, 거기서 더 나갈 곳이 없는 막다른 곳이 된다.
어떤 길을 따라서 계속 원을 그리며 돈다.
A-B-E-F라는 길을 따라서 1번 결과를 도출했다면 끝이지만 2번 결과처럼 A-G-H를 만나면 더이상 빠져 나갈 곳이 없게 된다. 이른바 막다른길(Dead End)이라고 한다. 그러나 이 경우에 길이 없다고 단정할 수는 없다. 3번은 무한루프로 A-B-C-D-B-C-D경로가 해당된다. 2번 결과를 방지하려면 “막다른 도시라면 다시 바로 그 이전 도시로 되돌아간다”라는 규칙을 정하면 된다. 이를 백트래킹(Backtracking)이라 한다. 3번 결과를 방지하려면 “한번 가본 도시는 다시 안 간다”라는 규칙을 정하면 된다. 이러한 탐색 방법은 스택과 관련이 있다. 어떤 도시를 선택해서 갈 떄마다 그 도시를 스택에 푸시한다면 스택의 내요은 A로부터 출발해서 지금까지 거쳐 온 일련의 도시를 나타낸다. 이렇게 되면 백트래킹은 스택의 팝 작업에 해당한다. 가장 최근에 거쳐 온 도시로 되돌아가는 행위이기 때문이다. A-B-E-F로 가는 깊이우선 탐색순서이다. A-B에서 E대신 C를 먼저 탐색한 이유는 인접한 노드가 여럿 있을 때 알파벳 순서로 먼저 방문하도록 규칙을 정했기 때문이다. 만약 맨 끝에 있는 스택이 비어있다면 해당 경로로 가는 길이 없다고 결론지을수 있다.
스택(Stack)이란 쉽게 말해 “쌓아올린 더미”를 의미 예를 들어 책상 위에 쌓아놓은 책, 설거지를 위해 쌓아놓은 식판, 창고에 쌓인 박스 등이 모두 스택이다. 이들의 공통점은 바로 가장 최근에 입고된 물건인 가장 앞쪽 물건부터 빠져나가게 된다는 특징이다. 이를 후입선출(Last In First Out)이라고 한다. 정리하면 가장 최근에 삽입된 위치에 있는 데이터를 삭제하거나 아니면 거기에 이어서 새로운 데이터를 삽입할 수 있도록 하는 추상 자료형을 뜻한다. Pop은 스택 탑 데이터를 삭제하는 작업이고 Push는 스택 탑 바로 위에 새로운 데이터를 삽입하는 작업이다. 시각적으로 볼 때 스택에서의 삽입, 삭제는 한 쪽 끝에서만 일어난다. 즉, 푸시나 팝 모두 스택 탑 부근에서 일어난다.
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.
입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다.만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 “0” 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 “0”일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
정의 : 주어진 복잡도 함수 f(n)에 대하여, O(f(n))은 n ≥ N을 만족하는 모든 n에 대하여 부등식 g(n) ≤ c × f (n) 을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.
정의 : 주어진 복잡도 함수 f(n)에 대하여, (f(n))은 n ≥ N을 만족하는 모든 n에 대해 부등식을 g(n) ≥ c × f (n) 을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.
빅오와 빅오메가를 하나로 합쳐 표현한 평균적인 경우의 알고리즘이다.
트리의 구성요소에 해당하는 A,B,…,F를 노드(Node)라 한다.
트리의 레벨(Level)은 루트노드를 레벨0으로 하고 아래로 내려오면서 증가한다.
그림에서 탐색이 시작되면 일단 출발지인 A를 큐에 삽입한다.
너비우선 탐색도 깊이우선 탐색과 마찬가지로 “목적지까지 가는 길이 있는가?”라는 문제 해결에 사용될 수 있다.
Add는 현재의 리어 바로 뒤에 새로운 데이터를 삽입하는 작업이고
Pop은 스택 탑 데이터를 삭제하는 작업이고
