본문 바로가기

취준

[백준][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.. 더보기
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번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연.. 더보기

티스토리툴바