쉬운 문제일줄 알았는데, 시간과의 싸움이었던 문제 바로 기록 들어간다!!! 1. 출처 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 시간 초과와의 싸움 ㅠ 아래 설계에서 실패 이유까지 설명하겠다. 3. 설계 1) 실패한 설계 문제를 보면, 문자열 W가 랜덤순서이다. 만약 abcd라고 해보자 그럼 W는 abcd일 수도 있고, cdab일 수도 있다. 그리고 내가 찾은 벽화의 기록된 마야 문자열 S에 abcd, cdab라는 문자열이 부분 문자열로 포함되어 있는지를 찾는 문제이다. 그..
제목부터 무시무시한 문제이다. 무려 BFS / DFS / MST가 모두 쓰이는 문제! 1. 출처 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 드디어 맞췄다!!! 흑흑 오랜만에 알고리즘을 다시 접하니 까먹은 것도 있어서 다시 공부하고... 다시 풀어보았다. 2. 설계 이 문제는 많은 분들이 3step으로 푸는 문제이다. step 1. 섬을 구분한다 -> BFS step 2. 다리를 만들 수 있는 모든 가짓수를 구한다 -> DFS step 3. 모든 섬을 연결할 수 있는 최소 길이의 다리 ..
오늘도 풀어보는 과거 내가 못풀었던 문제! 나는 이 문제를 재귀로 풀어보았다. 1. 출처 https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 무려 파이썬으로 2년전 실패했던 문제다 ㅎㅎ.. 싸피에 들어와 재귀를 배우고 문제를 풀어보니 감회가 색다르다. 2. 설계 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” [각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.] [1 ≤ k, n ≤ 14] 이 문구가 이 문제의 ..
설탕배달2가 생각보다 빠르게 풀린 것 같아 내가 못풀고 쟁여놨던 경비원 문제를 풀어보았다. 그동안 프로젝트하면서 함수를 장난아니게 만들었더니 함수를 이용해 차근차근 푸는 능력이 생겼나보다. 잘 해결해내었다. 좀.. 비효율적인 코드인 것 같지만... ^^ 아무튼 시작! 1. 출처 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 이것도 3달 전엔 못풀었던 문제다...ㅎㅎ 알고를 한동안 쉬다가 오니 머리가 리프레쉬라도 되었나...^^ 2. 설계 일단 문제 자체 이해는 쉽다. 경비원 X가 (동/서/남/북) 위치에서 가게(..
정!말! 오랜만에 코딩테스트 공부하러 왔다 ㅠㅠ 6월, 방학과 따로 추가적인 팀프로젝트 진행하면서 면접 보느랴 프젝 공부하느랴 바빴는데... 그래도 알고리즘은 감 떨어지면 안되기 때문에...!! 내가 저번 학기에 못풀었던 문제들을 다시 풀어보고자 한다! 1. 출처 26099번: 설탕 배달 2 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 2달전... 시간 초과 났던 그 문제... 다시 풀어보기 스타트! 2. 설계 및 전체 코드 여기서 주목 한 것은 3kg, 5kg의 설탕봉지이다. 우리가 덜 배달을 가려거든 5kg 봉지를 최대한 많이 가져가야..
1학기 마지막 프로젝트도 끝내고... 하나금융티아이 1차 면접도 끝내고... 넘 오랜만에 알고리즘으로 돌아왔다 ㅠ 뭔가 그리웠음... 한 번 코테를 쳐봐서 그런지 제대로 코딩테스트를 준비하고 싶어져서 [무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의 IT기업 코딩테스트 대비를 위한 [자료구조 및 알고리즘 핵심이론 & 관련 실전 문제 풀이 강의] 입니다. - JAVA 편 -, - 강의 소개 | 인프런 www.inflearn.com 이 강의를 보며 100제 풀어보려고 한다! 내가 풀다가 처음보다시피 한 문제 풀이 방법이 있어 가져왔다. 바로 누적합 문제이다. 1. 출처 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는..
골드 5 길래 얼른 풀고 시험공부 할라했더니 3시간 순삭했던 문제...;; 나의 실패썰과 성공썰을 공유하겠다. 1. 출처 처음엔 그냥 무작정 브루트포스 방식으로 알고리즘을 짰는데, 조합으로 풀지 않으면 답이 나오지 않겠다라는 생각을 하게 해 준 글이 있었다. 그래서 2번째 알고리즘은 조합으로 풀었더니 정답이 나왔다. 2. 설계 / 전체코드 1) 실패한 코드 import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static class Node { int r; int c; publi..
2일 전에 풀기 시작 한 문제... 프림으로 풀어서 안풀려가지고... 크루스칼로 도전해보았다. 1. 출처 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 2일 전엔 프림으로 풀다가 틀렸고, 오늘은 크루스칼로 풀다가 부모를 비교하는 과정에서 험난한 과정을 겪었다. 2. 설계 반례 참고 : https://www.acmicpc.net/board/view/48609 글 읽기 - 반례를 못..
