본문 바로가기

전체 글

 (34)
백준(boj) 14502_연구소 (파이썬, c++) https://www.acmicpc.net/problem/14502풀이벽을 3개 세워서 바이러스들이 퍼지게 한다. 바이러스가 퍼지지 않는 곳이 최대가 되도록 벽을 세운다. 6중 포문으로 3개의 벽의 위치를 나타내었고, 바이러스가 퍼지는 것은 바이러스들을 리스트에 넣어놓고 bfs()를 돌릴 때마다 큐에 바이러스들을 넣고 퍼지도록 만들었다.벽을 세 개 놓을 때 겹쳐서 놓지 않도록 (ix==jx and iy==jy) or (ix==kx and iy==ky) or (jx==kx and jy==ky) 인 경우는 continue로 건너뛰어 준다. bfs()함수에서 퍼지지 않는 바이러스 값을 찾을 때는 마지막에 a를 이중 포문으로 돌면서 0인 곳의 개수를 세어줘도 좋지만, 시간을 단축하기 위해서 zero 변수를 만들..
프로그래머스 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..

티스토리툴바