문제 https://edu.goorm.io/learn/lecture/17301/cos-pro-1%EA%B8%89-%EA%B8%B0%EC%B6%9C%EB%AC%B8%EC%A0%9C-java/lesson/839399/1%EC%B0%A8-%EB%AC%B8%EC%A0%9C5-%EC%86%8C%EC%9A%A9%EB%8F%8C%EC%9D%B4-%EC%88%98-java 구름HOME 구름은 클라우드 기술을 이용하여 누구나 코딩을 배우고, 실력을 평가하고, 소프트웨어를 개발할 수 있는 클라우드 소프트웨어 생태계입니다. www.goorm.io COS PRO 1급 기출문제 중 위 문제가 꽤 재밌어서 가져와봤다. N*N 격자에 1부터 N까지의 수가 소용돌이 순서로 있을 때 대각선상에 있는 수들의 합을 구하는 문제다. 풀이 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 풀이 정말 어려웠지만 재밌는 문제였다. 풀이법이 잘 생각나지 않지만 생각만 잘한다면 코드 길이가 매우 짧고 명료하게 해결할 수 있다. 이 문제는 DP를 이용하면 해결할 수 있다. 나는 DP 배열을 다음과 같이 정의했다. DP[0][i][j] = (i,j) 좌표에 세로로 들어오는 경우의 수 DP[1][i][j] = (i, j) 좌표에 가로로 들어오는 ..
문제 https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 풀이 이 문제는 아래와 같이 DP를 사용하여 해결할 수 있다. 1. A에 있는 문자열을 HashSet 자료구조에 모두 저장한다. 2. S의 뒷자리부터 0까지 순서대로 문자열을 substring으로 잘라 A에 속해있는지 확인한다. ex) t, st, est, test, ntest, ontest, contest ..... 3. 만약 substring이 A에 속해있다면 해당 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 풀이 이 문제는 정말 재밌는 문제였다. 문제에 나온대로 그냥 덧셈을 모두 하게 되면 시간초과가 발생할 수 밖에 없다. N*M배열에 K개의 명령이 있을 때 O(KNM)이라는 시간복잡도가 발생하기 때문이다...
문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 이 문제는 단순히 BFS, DFS를 사용하면 해결하기 매우 힘들다. 모든 자리에서 4방향을 모두 조사하는 식으로 탐색하면 경우의 수가 너무 많아 시간 초과가 발생한다. 따라서 조합을 사용하여 해결하는 편이 좋다. 25개의 자리 중 7개를 선택하는 경우의 수는 25C7 = 480700 으로 작은 편이다. 1. 25개의 자리 중 7개를 뽑는다. 2. 해당 7개의 자리가 모두 상하좌우로 연결되어..
문제 https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 풀이 이 문제는 아이디어가 매우 중요하다. 알고리즘 분류에 슬라이딩 윈도우로 표시되어 있는 것을 보고 힌트를 얻었다. a가 연속적이여야 한다는 말은 a가 a의 개수 만큼 연속적으로 위치해야 한다는 뜻이다. 예를 들어, "ababa" 라는 문자열이 있다면, a가 3개이므로 "aaabb", "baaab", "bbaaa".... 등 a가 3개 연속적으로 위치해야한다. 따라서, 인덱스 0 부터 끝까지 ..
문제 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 코드를 짜는 것보다 예외를 처리하는게 훨씬 어려웠던 문제였다. 우선 다음과 같은 Fireball 클래스를 만들었다. public static class Fireball{ int r;// 행 int c;// 열 int m;// 질량 int s;// 속력 int d;// 방향 Fireball(int r,int c,int m, int s,int d){ ..
문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 이 문제는 간단한 BFS 문제이다. 다만 일반적인 BFS와 달리 방문 여부를 체크하지 않는다. 대신 6개의 숫자를 택하면 더 이상 탐색을 진행하면 안 되는 식으로 구현하면 된다. 나는 다음과 같은 Node 클래스를 만들어서 큐의 원소로 사용했다. public static class Node{ int x; int y; String str; Nod..
문제 https://programmers.co.kr/learn/courses/30/lessons/72413?language=java 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 이 문제는 접근법만 알면 간단한 문제이다. 예전..
문제 https://programmers.co.kr/learn/courses/30/lessons/72412?language=java HTML 삽입 미리보기할 수 없는 소스