본문 바로가기

알고리즘 문제풀이

 (31)
프로그래머스 Lv2. 스킬트리(파이썬) https://programmers.co.kr/learn/courses/30/lessons/49993풀이언뜻 봤을때 위상정렬로 풀어야하나 싶었지만, 그냥 skill의 우선순위를 표시해가며 풀어도 될 것 같아서 모든 알파벳의 우선순위를 0으로 초기화 하고, skill의 알파벳 순서대로 1씩 추가해준 값을 idx 배열에 저장해 주었다. 이를 이용해 비교하려는 문자열을 훑으면서 현재의 우선순위보다 높으면 잘못된 순서이므로 flag를 표시하고 끝낸다. 알파벳은 ABC...XYZ를 0번부터 25번의 인덱스로 사용하고 싶어서 ASCII 값을 이용해 바꿔주었다.(AToI함수) python3def AToI(A): return ord(A) % 65 def solution(skill, skill_trees): answer..
프로그래머스 Lv1. 크레인 인형뽑기 게임(파이썬) https://programmers.co.kr/learn/courses/30/lessons/64061풀이몇 번째 열인지 알려주고(moves 배열), 그 열의 가장 위에 있는 인형을 뽑아서 바구니에 옮긴다. 인형은 바구니에 아래서부터 차곡차곡 쌓이고 같은것이 2개 연속되면 터트린다. 바구니의 구현은 스택을 이용하면 되는데 파이썬은 그냥 리스트를 사용하면 된다. (c++은 벡터로 구현하면 된다.)인형을 뽑았을 때 바구니의 가장 위에 있는것과 비교해서 같은거면 없애고 정답 변수에 +2를 해준다. 다른거면 그냥 인형을 바구니에 올린다.(추가한다.)python3def solution(board, moves): answer = 0; st=[] for x in moves: x-=1 #0번 인덱스부터 사용할꺼야~ fo..
백준(boj) 13458_시험 감독 (파이썬, c++) https://www.acmicpc.net/problem/13458풀이시험을 봐야 하는데 총감독관 1명은 고정, 총감독관이 감시 가능한 인원 외 나머지 인원을 부감독관이 모두 감시할 수 있을 만큼 뽑아주면 된다. 계속 빼주면 너무 오래 걸리니 나누기 연산을 사용한다. 단, 나눴을 때 나머지가 0이 아니면 (예를 들어 남은 인원이 3명이고 부감독관 감시 능력이 2명이면 나머지가 생긴다. 이럴 땐 부감독관이 한 명 더 있어야 한다) 나눈 값에 1을 더해준다.python3from sys import* input = stdin.readline ​ n=int(input()) a=list(map(int,input().split())) b,c=map(int,input().split()) #총감, 부감 res=0 fo..
백준(boj) 3190_뱀 (파이썬, c++) https://www.acmicpc.net/problem/3190풀이뱀의 이동 방향과, 시간에 따른 방향의 변화가 주어진다. 뱀의 머리가 움직일 때 그 자리에 사과가 있으면 사과를 먹고 꼬리는 그대로 두고, 만약 사과가 없으면 머리를 움직이고 마지막 꼬리를 잘라낸다. 꼬리의 순서가 필요하므로 tail이라는 이름의 queue를 사용했다 . 시간에 따른 방향 변화도 큐에 넣고 제일 앞에 있는 원소의 시간이 현재 시간과 같으면 방향 지시에 따라 방향을 변화 시켜 주었다. 방향은 dd배열을 URDL순으로 만들어 놓고, 시계방향이면 dd배열의 다음 방향으로 바꾸고, 반시계방향이면 dd배열의 전(前) 방향으로 바꿔주었다.python3from sys import* from collections import* inpu..
백준(boj) 13460_구슬 탈출2 (파이썬, c++) https://www.acmicpc.net/problem/13460풀이빨간 구슬과 파란 구슬이 있다. 네 방향으로 기울일 수 있는데 한번 기울이면 구슬이 벽에 닿거나 구멍에 빠질 때까지 이동한다. 파란 구슬은 어떠한 상황에도 빠지면 안 되고, 빨간 구슬만 구멍으로 들어갔을 때 게임이 끝난다. 최소 몇 번 만에 빨간 구슬을 빼낼 수 있을까 찾는 문제이다. 단, 10번을 초과하면 -1을 출력한다. BFS를 사용해서 최단 거리를 찾아주었고, move() 함수를 통해 기울이는 동작을 구현했다. visit 배열을 4차원으로 선언해서 빨간구슬, 파란구슬 각각의 x, y 값이 위치한 곳에 방문 순서를 기록해 두었다.python3from sys import* from collections import* input = ..
백준(boj) 17070_파이프 옮기기1 (파이썬, c++) https://www.acmicpc.net/problem/17070풀이가로 방향일 때 (x, y+1), (x+1, y+1) 부분에 벽이 없으면 갈 수 있고,세로 방향은 (x+1, y), (x+1, y+1) 부분에 벽이 없으면 갈 수 있고,대각선 방향은 (x+1, y), (x, y+1), (x+1, y+1) 부분에 벽이 없으면 갈 수 있다.대각선 방향으로 갈 때는 옆,아래,대각선 모두 벽이 없어야 갈 수 있으므로 따로 처리해 주었다.(n-1, n-1)로 가는 모든 경우의 수를 구하는 문제이다. BFS를 사용하였다.python3#c++은 통과, python은 시간초과남 dp로 다시 풀기 from sys import* from collections import* input = lambda:stdin.readl..
백준(boj) 16637_괄호 추가하기 (파이썬, c++) https://www.acmicpc.net/problem/16637풀이수식이 문자열로 주어진다. 피연산자는 0~9인 정수이므로 홀수번째 인덱스는 수식이고 짝수 번째 인덱스는 숫자인 것을 이용했다. solve() 함수를 이용해 완전 탐색 해줬는데 check 리스트를 이용해서 그 자리에 해당하는 수식이 켜져 있는지 꺼져있는지 확인 후 계산해 주었다. 이때 계산은 deque를 사용해 주었다.python3from sys import* from collections import* input = lambda:stdin.readline().strip() def cal2(n1, op, n2): #연산 받아서 계산 if op == '+': return n1+n2 if op == '-': return n1-n2 if op..
백준(boj) 17825_주사위 윷놀이 (파이썬, c++) https://www.acmicpc.net/problem/17825풀이주사위 10개의 턴이 주어지는데, 이를 이용해서 최대 점수를 구하는 문제이다. 완전 탐색 하였다. 요점 1. 말 4개를 가지고 게임을 하는데, 2. 이미 말이 있는 곳은 갈 수 없다. 3. 각 칸에는 점수가 있고 4. 파란색 선이 있는 부분은 파란 방향으로, 그 외엔 빨간 방향으로 가야 한다. 해결책 1. horse 라는 리스트에 [방향, 인덱스]를 표현해서 해결 2. visit 리스트를 이용하여 해결 3. 판에 있는 점수들을 a리스트에 표현하여 해결(a리스트 방향에 따라 셋팅) 4. 방향(d 변수)이랑 인덱스(x 변수)로 빨간 방향 부분이면 거기로 향하게 함 a 리스트를 그림으로 표현하면 다음과 같다. python3from sys i..

티스토리툴바