본문 바로가기

분류 전체보기

[백준][Python][2225][DP] 합분해 문제 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 배열의 의미는 다음과 같다 세로 K = K개의 숫자를 쓴다 가로 N = 0-n 까지를 써서 만든다. 이랬을 때, 문제 조건상 1개의 숫자로 만들수 있는 n 후보들의 갯수는 1이다. 0을 0번써서 만드는 건 1로 하자. 이때, i개를 써서 j를 만드는 방법의 갯수는 (i-1개를 써서 0-j 까지를 만드는 방법의 갯수의 총 합) 으로 나타낼 수 있다. 왜냐면, 10 = 9를 만드는 방법의 수 + 1, 8을 만드는 방법의 수 +2 ... 이런 식으로 나타낼 수 있기 때문이다. 원래는 10을 만드는 방법의 .. 더보기
[백준][Python][17142][시뮬레이션] 연구소 3 문제 : https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 시뮬레이션 문제다. 코드가 더러워 보이는데 더러운것 맞다. 이 문제는 모든 선택된 바이러스 조합에 대해 BFS를 통해 최솟.. 더보기
[백준][Python][15989][DP] 1,2,3더하기 4 문제 : https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 1+3 (3+1) 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net DP 문제인데 좀 까다롭다. 1,2,3 더하기 시리즈를 보면 하나같이 DP 문제인데, 이문제가 제일 어려웠다. 1,2,3을 써서 숫자를 만드는데, 숫자는 같으면서 순서만 다른건 하나로 하는 것이다. 밑에는.. 더보기
[백준][Python][14226][BFS] 이모티콘 문제 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net BFS 문제다. 숨바꼭질 문제와 크게 다를바 없는 문제이다. 이 문제에서 내가 접근한 방식은 다음과 같다. 큐에 넣을 현재 .. 더보기
[프로그래머스 Programmers][Python] 카드 게임 (3/13 수정) 문제 : https://programmers.co.kr/learn/courses/30/lessons/42896 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr (3/13 이후 테스트케이스가 추가되었습니다. 따라서 기존 풀이로는 풀리지 않습니다.) DP 단골 문제 길찾기에서 방향만 하나 더해지는 거니까 어렵지 않게 풀 수 있다. 어려웠다. 댓글에서 알려주신 [2,1,1], [3,1,1] 예시를 들면 예전 코드에서는 2가 나온다. 그런데 2가 나올려면 (2,3) 상황에서 오른쪽의 3을 버려야 각각 1,1 을 버릴 수 있게 되어 2가 나온다. 근데 이건 불가능하.. 더보기
[프로그래머스 Programmers][Python] 네트워크 문제 : https://programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS 문제다. 기본적으로 DFS 싫어하기도 하고, 파이썬에서는 dfs로 잘못풀다가는 스택 제한걸려서 터지는게 다반사라서 BFS로 풀다가 안됨. DFS를 기본적으로 쓰는거 같길래 보고 써봤다. 풀고나서 보니까 다른사람들은 BFS잘만 쓰더라. from collections import deque def dfs(v,c, start,n): v[start] = True for i in range(n): if.. 더보기
[프로그래머스 Programmers][Python] 단어 변환 문제 : https://programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS 문제다. onemissing 은 일단 한글자가 다른가를 확인하는 함수이다. 그 다음 일반적인 bfs처럼, 단어를 순회하면서 한글자만 다른지 onemissing으로 확인한다. 물론 중복체크를 위해 dict v를 사용한다. 그리고 큐에 (단어, 사용 횟수)를 적고, 단어가 target이 되면 답을 반환한다. from collections import deque def onemissing(a,b,n.. 더보기
[프로그래머스 Programmers][Python] 짝지어 제거하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 괄호 문제랑 비슷한 문제로 스택을 쓰면 해결된다. string s의 처음부터 차례차례 스택에 넣으며 맨 위쪽과 현재 문자가 같으면 스택에서 하나를 제거한다. 아니면 그 문자를 스택에 넣는다. 처음이거나 중간에 다 지워지거나 했을 경우를 대비하여 len(st)==0 스택이 비었으면 무조건 문자 하나를 넣고 본다. 스택의 길이가 0이면 완전히 지워진 상태이므로 return 1 , 아니면 return 0을.. 더보기

티스토리툴바