Remember Your Place

1. 문제 링크https://www.acmicpc.net/problem/92022. 문제 풀이 생각보다 플래티넘 V 정도의 문제들은 정석적인 풀이가 아닌 다른 방식으로도 풀리는 경우가 있는 것 같습니다. 이번 문제도 [BOJ] 14942 개미 문제와 같이 DFS로 풀렸습니다. 입력으로 단어들이 300,000 미만 정도의 개수로 주어지는데, 솔직히 시간제한과 메모리 제한이 각각 10초와 512 MB로 매우 널널합니다. 저는 트라이(Trie)와 DFS를 사용한 풀이보다는 Set을 활용한 DFS를 채택하였습니다. HashSet에 모든 단어를 저장한 후, DFS를 통해 단어의 존재 여부를 확인하며 문제를 해결했습니다. 이렇게 구현한 이유는 HashSet의 탐색 속도가 평균적으로 O(1)에 가깝고, 단어 길이가 ..

1. 문제 링크https://www.acmicpc.net/problem/149422. 문제 풀이 이 문제에서는 방의 개수 최댓값이 100,000으로 주어집니다. 보통 input 값으로 10만 이상의 단위가 나오게 된다면 단순 구현으로는 못 푸는 경우가 많죠. 그래서 원래라면 희소 배열(Sparse Table)이라는 개념을 적용해서 풀어야 하는 문제이긴 합니다만. 이 문제는 단순 DFS로 풀립니다! 물론 아직 푼 사람이 그렇게 많은 편이 아닌 데다가 추가 테스트 케이스가 있어야 플래티넘다운 문제라고 할 수 있겠는데 ..   static void dfs(int node, int parentNode) { parent[node] = parentNode; for (Edge edge : g..

1. 문제 링크https://www.acmicpc.net/problem/232892. 문제 풀이 이제 곧 기다리던 삼성 코딩 테스트죠? 구현만큼은 자신 있었던 (과거형) 저도 이번만큼은 긴장되네요. 그야 자소서 문항이 바뀌고 난 후 첫 시험이라 .. 코딩테스트도 변동이 있을 가능성도 없진 않을 테니까요. 그래서 예전 같았으면 그냥 배열 돌리기랑 bfs만 돌리고 갔을 텐데 이번엔 다릅니다. 몇 달 전에 큐빙을 풀긴 했지만 좀 제대로 된 플래티넘 구현 문제를 풀고 싶었습니다.  가장 중요한 건 설계. 코드를 구현하기 전에 꼼꼼하게 조건을 숙지한 후 구현을 해야 합니다. 그래도 나름 짧은 코드로 만들어보고 싶었으나 코드가 좀 길게 나왔습니다. 1. 모든 온풍기에서 바람 나옴2. 온도 조절3. 온도 1 이상인 ..

1. 문제 링크https://www.acmicpc.net/problem/5373 2. 문제 풀이 작년에 Java로 알고리즘을 본격적으로 시작하게 됐을 때 삼성 기출 위주로 스터디를 했습니다. 그때부터 눈여겨보던 문제였는데 A형 유형에 익숙해져서 구현 위주의 문제는 이제 마무리 지으려고 풀게 된 문제입니다. 구현이야 학부생부터 다른 언어 쓰면서도 다져온 것이니까 이제는 최적화를 중심으로 좀 더 심화된 알고리즘을 안 보고 코딩하는 연습을 해야겠습니다.  구현 쪽으로는 말이 좀 있는 문젠데 예전에 이 문제를 지나가면서 봤을 땐 배열만 어떻게 부분 복사만 하면 잘 될 거라 생각했습니다. 물론 풀진 않았지만. 전개도를 그리니까 삼성 기출에 들어있던 주사위 굴리기 문제가 생각났습니다. 풀면서 재밌었던 문제였는데 그..

1. 문제 링크 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 풀이 DP 문제를 좀 많이 풀어보고 싶어서 얼마 전부터 풀기 시작했습니다. 하지만?? 피보나치를 벗어나는 점화식을 만들어내는 건 아직 힘들더라구요. 처음엔 DP 문제가 아닌 줄 알았지만 시간제한이 0.5초라 브루트포스..같은 건 안될 거 같습니다. 동전의 구성은 같지만 순서만 다른 경우가 생기는데 그동안 만들어낸 조합들을 어떻게 하나하나 체크를 다 하겠어요.. 그러니 이 ..

1. 문제 링크 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 2. 문제 풀이 안녕하세요. 반례 찾을 때마다 시간을 엄청 날려버려서 또 찾아왔습니다. 이제는 그냥 문제 풀 때마다 글을 써야 할까 싶네요. 마침 애드센스도 승인됐고? 방문자도 많아지면? 억만장자의 길로 한 발자국 ... 은 무슨. 개발 블로그는 돈이 안됩니다. ^^; 개발 + 취미 + 일상으로 운영하면 괜찮긴 할 텐데 글쎄요.. 🧐 블로그가 주가 되면 안 될 거 같아요. 그냥..

1. 문제 링크 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 2. 문제 풀이 아니, 알고리즘 문제는 어차피 자기 자신이 풀어야 하는 거라서 사용되는 알고리즘 외에는 따로 해설은 필요 없다고 생각했습니다만. 어제오늘 너무 반례 때문에 화가 나서 도저히 안 되겠습니다. 이 문제는 좀 많이 혼나야 해요. 오죽하면 제가 평소에는 쓰지도 않던 반례 공유 게시글을 쓰겠냐구요. 내 삽질이 내 코드보다 가취치 있기를 ,,🤡 https://www.acmicpc.ne..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 분류 : 정렬 게임에서 브론즈 실버라는 등급은 무시받기 쉬운 계급입니다. solved.ac에서 정한 백준 문제의 티어가 브론즈 실버라면 이 정도쯤이야..ㅋ 많이 얕잡아보는 경향이 있습니다. 실버 5 티어의 문제라 할지라도 시간제한과 메모리 제한을 신경 쓰지 않는다면.. 원트라이로 문제를 풀 순 없겠죠. 이 문제의 정답률이 23%인 것만 봐도 많은 사람들이 어딘가에서 걸려 넘어졌네요. 저도 그랬습니다. java im..

https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 www.acmicpc.net 분류 : 구현, 문자열 오랜만에 solved.ac를 들어갔더니 깃허브 잔디밭 같은 기능이 생겼습니다. 예전에 푼 문제들은 깃허브에 따로 백업을 해놓았는데 이젠 안 그래도 되겠네요. 적어도 한문제 이상은 푸는 걸로 꾸준히 잔디 심어봐야겠습니다. 깃헙은 이제 쓸데없는 커밋은 밀어버리고 의미 있는 것만 남겨두기로... 클래스라는 메뉴도 생겼습니다. 백준에서 분류별 문제만 풀땐 지루했는데 낮은 클래스..

https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 분류 : C++ 연습용 N개의 정수가 주어지고 여기서 최솟값과 최댓값을 구하는 프로그램을 작성하는 문제입니다. test case는 아래와 같습니다. 5 > a; int *arr = new int[a]; for (int i = 0; i > arr[i]; } min = arr[0], max = arr[0]; for (int j = 0;..