전체 글

[BOJ] 9251 : LCS (Java)

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 걸린 시간 : 1시간 13분 난이도 좀 더 쳐줘요.. LCS를 알면 제일 기초여서 난이도가 낮게 책정된 듯. 처음에 무슨 생각이었는지 N 이 1000인데도 불구하고 시간제한이 걸려있어서 O(N^2) 이 불가능하다고 생각했다. 그러다 O(N^2)이 가능한 것을 알고 표를 무작정 그려봤는데,,, 감은 왔지만 정확한 점화식을 생각해내지 못했다. 결국, 답을 ..

[BOJ] 1987 : 알파벳 (Java)

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 걸린 시간 : 23분 22초 전형적인 백트래킹 문제이다. 단, 재귀함수 호출 시 알파벳을 지나갔는지에 대한 검사도 해야 한다. 이 검사에는 HashSet 자료구조를 썼다. 정답 코드 import java.io.*; import java.util.*; public class BOJ1987 { static int R, C; static String[] board = new String[21];..

[BOJ] 1744 : 수 묶기 (Java)

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 걸린 시간 : 25분 2초 알고리즘 두 수를 묶는다는 것은 곱한다는 것이다. 따라서 음수끼리 혹은 양수끼리 곱해야 한다. 즉, 음수가 짝수라면 작은 음수부터 차례대로 묶어가면 끝이다. 양수도 마찬가지로 짝수라면 큰 수부터 차례대로 묶어가면 된다. 만약 양수가 홀수라면 가장 작은 양수를 묶지 않고 즉시 더해주면 된다. 만약 음수가 홀수라면 가장 큰 음수를 즉시 더해주면 된다. 단, 만약 수열에 0..

[BOJ] 21608 : 상어 초등학교 (Java) with 정렬

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 걸린 시간 : 1시간 4분 복잡한 문제같지만 자리를 주어진 조건에 맞게 정렬해서 한 명 한 명 자리에 앉히면 된다. 정렬 Java에서 복잡한 정렬을 하는 방법은 여러가지가 있다. Comparator 인터페이스의 compare 함수를 직접 구현하기 람다식을 활용해 익명 객체 사용해 구현하기 메서드 참조와 유틸리티 메서드 사용하기 나는 2번을 이용해 문제를 풀었다. 아래는 int 형 변수 ..

[BOJ] 1941: 영역 구하기 (Java)

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 걸린 시간 : 47분 8초 (자바 미숙) 자바로 코테가 미숙해서 열심히 푸는 중...!! 자바 언어에 익숙해지고자 풀어봤다. 문제에서 입력할 때 M, N 순서로 주기도 하고 N, M 순서로 주기도 해서 주의해야 한다. 알고리즘 영역이 100 X 100 이하이므로 이 크기의 2차원 배열을 만들어 입력 받을 때 칠해진 곳을 체크한다. 그 후 DFS로 방문체크를 하며 연결요소의 수를..

[BOJ] 1941: 소문난 칠공주 (Java) with 조합

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 이전에 C++로 푼 문제이다. https://morenow.tistory.com/21 [BOJ] 1941: 소문난 칠공주 (C++) with 조합 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생 morenow.tist..

[Programmers] 2023 KAKAO BLIND RECRUITMENT : 택배 배달과 수거하기 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 실제 시험에서 못 풀었던 문제다. 그리디와 최적화가 필요한 문제이다. 그리디적인 아이디어를 떠올리긴 어렵지 않지만, 매번 배달 거리를 처음부터 계산하도록 코딩하면 O(N^2) 이다. 인덱스를 기억해서 O(N) 으로 바꿔야 한다. 알고리즘 그리디 배달과 수거를 할 때, 제일 먼 곳부터 배달/수거하면 된다. 조금만 생각해보면 먼 곳부터 다녀오면서 거리를 줄여나가는 것이 최적이라는 것을 생각할 수 있..

[Programmers] 네트워크 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 8분 50초 알고리즘 간단한 BFS 혹은 DFS 문제이다. 이 문제는 어떤 것으로 풀어도 나쁘지 않지만, 코드 구현은 BFS보다 재귀를 사용하는 DFS가 간단한다. 방문체크는 vis라는 배열로 처리하고, 방문하지 않은 노드를 발견하면 카운트를 하고 DFS를 실행하면 끝이다. 정답 코드 #include #include using namespace std; bool vis[201]; v..

[Programmers] 정수 삼각형 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 10분 알고리즘 대표적인 DP 문제이다. 거쳐가는 숫자들을 더해서 저장해놓는 memo 배열을 채워가며, memo의 마지막 열 값들 중 최댓값을 리턴한다. 정답 코드 #include #include using namespace std; int memo[501][501]; int solution(vector triangle) { int answer = 0; memo[0][0] = tri..

[Programmers] JadenCase (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/12951 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 걸린 시간 : 8분 알고리즘 첫 문자가 소문자이면 대문자로 바꾼다. 그 후 모든 문자를 검사하며 다음을 실행한다. 해당 문자가 공백이면 다음 문자가 소문자인지 검사하고 대문자로 바꾼다. 해당 문자가 대문자이면 이전 문자가 공백이 아닌지 검사하고 소문자로 바꾼다. 정답 코드 #include #include using namespace std; string solution(string s) { if ..