본문 바로가기

백준

[백준][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가 나온다. 근데 이건 불가능하.. 더보기
2020-03-21 코딩테스트 대비 모의고사 후기 https://www.acmicpc.net/contest/view/505 2020/03/21 코딩테스트 대비 모의고사 www.acmicpc.net 3월 21일에 백준에서 코딩테스트 대비 모의고사를 하길래 한번 해봤다. 삼성 A형이랑 비슷하게 문제를 만들었다고 했고, 실제로 그런것 같았다. 결론적으로 2문제중 1문제를 맞췄는데 2번문제는 시간제한에 걸렸다. 수가 작아서 BFS 안써도 될줄 알았는데 써야 통과가 되더라. 안타깝다. https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연.. 더보기
[백준][Python][17140][시뮬레이션] 이차원 배열과 연산 문제 : https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 문제다. 조건에 맞는 계산을 할때 Counter를 쓰면 편하다. (thatsort, rowcmd) Counter로 (item, 갯수 ) 들의 목록을 만든다 이걸 갯수, item 순서로 정렬한다. 0은 제외한다 가장 긴 길이에 맞춰 0을 추가해준다. 그리고 위의 계산을 가로 단위로 만든 뒤, 세로 ->가로 -> 연산 ->세로 로 바꾸는 식으로 재활용이 가능하다.(co.. 더보기
카탈란 수 Catalan number Python 구현 https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net 이 문제를 풀면서 처음 알게된 수열이다. 뭐 위키피디아 같은데 보면 증명 다 볼 수 있는데, 코딩테스트에서 쓸 수 있을정도로만 알면 되니까.. 더보기

티스토리툴바