백준
3190_뱀
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 뱀이 사과를 먹고 길어져서 벽에 부딪히거나 하면 끝나는 게임이다. 다들 한번쯤 해본 적 있을 것이다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 문제에서 해당 멘트를 제공해 주는데 정말 코드로 구..
12100_2048(easy)
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048을 구현하면 되는 문제이다. 결국 5번의 전체탐색을 해야하는데 이는 dfs를 사용했다. 그리고 위,오른쪽,아래,왼쪽으로 이동시킬때 문제를 쪼개서 생각해 보았다. 해당 부분을 위로 올리는 과정을 생각해보자. 4개의 세로줄이 있는데 이를 왼쪽부터 차례대로 하나씩 올리는 방향으로 계산을 할 것이다. 우선 왼쪽 상단부터 2,2,2를 순서대로 빼서 큐에 넣는다고 생각해보..
13460_구슬탈출 2
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성역량 테스트 문제였다고 한다. 예시에 있을법한 반례들이 거의 다 주어져서 그런지 시간은 조금 걸렸지만 도움을 안받고 스스로 푸는데에는 성공했다. 문제를 접근하는 것은 간단했는데 꼼꼼하게 체크하는것이 중요했다. 전체적인 흐름은 아래와 같다. 1. R,B,O의 좌표를 처음 가지고 시작 2. 큐를 활용하여 bfs 탐색 (상하좌우) 3. B가 O위치에..
14501_퇴사
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp를 활용하면 풀 수 있는 문제이다. 단 상담 날짜가 안되는게 해당날짜부터 뒤부터 안되므로 dp를 채워나갈 때 뒤에 날짜부터 시작하였다. 백준의 주어진 입력케이스로 생각해보자. 7일 부터 시작해서 과거로 하루씩 늘어난다고 생각하고 이걸 i라고 생각해보자 즉 i 는 1일부터 7,6,5,4,3,2,1 이 된다. (코드로 구현한다면 6,5,4,3,2,1,0으로 구현할 수도 있다.) 7일인 경우 i는 1이고 상담에 걸리는 날짜가 2일이기에 추가할 수 없다. 이런식으로 dp를 거꾸로 채워나갈 것이다. 그렇다면 상담을 할순 있는 날짜임을 걸러..
1305_광고
https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 역시 KMP알고리즘을 활용해 푸는 문제이다. 특히 KMP Table을 이용해서 풀 수있다. 예를들어서 7 aabaaba라는 문자열이 있다고 생각하면 KMP Table을 구하면 [0, 1, 0, 1, 2, 3, 4] 가 나온다 즉, 광고판의 끝부분에서 보았을때 시작부터 4개의 지점이랑 겹친다는 의미이다. 그렇기 때문에 광고판의 개수에서 겹치는 개수를뺀 l - KMP_Table[-1]을 구하면 답을 구할 수 있다. l..
4354_문자열제곱
https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net KMP 알고리즘을 활용해서 문제를 풀 수 있다. a란 이름의 str이 입력된다고 생각해보자. a+a 문자열을 하나 만들 수 있을 것이다. 만약 abcd가 들어온다면 abcdabcd를 만들어준다. 이 a+a 문자열에서 a가 시작되는 부분을 구해준다. abcdabcd라면 abcd가 다시 시작되는 부분은 5번째일 것이다 index로 나타내면 4이다. aaaa가 들어온..