https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 이 문제를 풀면서 내가 수학과 규칙성 찾기가 많이 부족하구나를 느꼈다... 처음에 이 문제를 시도했을 때는 단순 하드 코딩 밖에 생각나지 않았다.. 그래서 바로 메모리 초과로 뚜드려 맞고 고민을 해보았다. 그런데 도저히 방도가 생각나지 않았다. 그래서 이제 미지수를 두어서 여러가지 시도를 해보았다. 미지수를 두고 방정식을 세워서 더해도 보고, 빼보기도 하면서 무언가 감이 올듯 오지 않아서 결국 또 질문 게시판을 ..
https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 이 문제는 경우를 따지는 것이 조금 어려웠다. 처음에는 접근 방법을 어떤 식으로 해야하나 고민하면서 그림을 여러 차례 그려보면서 조금씩 이해했고, 반례를 찾기위해 저번처럼 질문 게시판의 반례들을 사용해보면서 경우를 찾아 냈다. 원리는 정리해보면 간단하다. 두 좌표지점에서 그리는 각각의 원이 접해서 생기는 점의 갯수를 구하는 것이다. 경우는 접하지 않는 경우, 접하는 경우, 원 안에 원이 포함되어 접하는 경우, 원 안에 원이 포함된 경우, 원이 같은 ..
https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 이번 문제는 참외밭이다. 문제를 이해하면서 조금 어려움이 있었다. 처음에는 그냥 전체 넓이에서 짤린 부분을 계산하면 되겠지라고 생각해서 하는데 이게 주어지는 입력이 반시계방향 순서대로 주어지는게 맞는지 반례들을 보다보니 헷갈렸다. 그래서 도저히 모르겠어서 다른 사람들의 코드를 보면서 이해를 했다... 내가 맨 처음 생각한 원리와 비슷하지만 조금 다른 풀이 방법이다. 일단 제일 긴 가로와 세로를 ..
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 이번 문제는 좀 많이 고생한것 같다. 다른 사람들이 올려둔 반례를 참고하고 중간에 시간초과로 다시 방식도 바꿔서 짜다보니 오래 생각하고 풀어본 것 같다. 일단 이 문제에서 다루는건 Queue와 Deque라고 할 수 있겠다. 나는 처음에 queue로 짰다가 명령어R을 수행시키는 과정에서 시간초과 요인이 생겨서 백준 질문 게시판에 다른 사람들이 추천한 Deque를 사용했다. 우선, 제일 먼저 TestCase의 갯수를 입력 받을 T를 정의하고 Buffered..
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 이 문제는 약간 생각을 깊게하면 더러운 문제인 것 같다. 단순하게 배열여러개 쓰면 쉽게 풀 수 있지만 처음에 EntrySet이나 Iterator를 이용해서 할려고 하다보니 쓸데없이 시간을 좀 많이 썼다가 그냥 단순하게 풀기로 했다. 이 문제를 풀면서 HashMap에 왜 getKey메서드가 없는건지 아쉬웠다... 어쨌든 EntrySet이나 Iterator를 쓰기에는 너무..
종강 기념해서 이제 하루에 하나씩 백준을 풀어보려고 한다. 오늘은 몸풀기로 아주 쉽고 쉬운 문제를 풀었다. 오늘 푼 문제는 아래의 문제다. https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 이게 왜 실버 3인지 잘 모르겠지만 그렇다고 하니까...일단 풀었다. 너무 간단한 문제라서 아마 코드를 짧게 쓰는 사람이 많을 것 같다고 생각한다. for문을 두번이나 써서 좀 그런것 같아서 다른 사람들은 어떻게 풀었는지도 봤다..
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제는 읽어보면 좋겠다. 나는 처음에 문제 내용도 이해 못했다.. 문해력 키워야지... 주변에 알고리즘 장인들이 많아서 많이 물어보면서 풀었다. 나도 잘하고싶어~~~ㅠㅠ 어쨌든 사담은 그만하고 문제에 대해서 설명하겠다. 문제를 간단하게 생각하면 주어진 size에 대해 9등분하여 5번칸을 제외하고 또 각각의 칸을 9등분하는 과정을 반복하는 것이다. * * * * * * *..
이번에 풀은 문제는 백준 18870번이다. 처음에 이 문제의 내용 자체를 몰라서 좌표압축이 뭔지부터 공부해보았다. https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표압축이란 간단하게 설명하면 입력 받은 값들을 정렬하여서 순서대로 인덱스값(좌표를 부여하는 것이다.) ex) 2,4,-10,4,-9를 주면 -10, -9, 2, 4, 4으로 정렬하고 -10은 0, -9는 1, 2는 2, 4는 3 그다..
