본문 바로가기

분류 전체보기94

[백준] 14247번 나무 자르기 자바 문제 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 문제 풀이 처음엔 그날 그날의 나무 중에서 가장 큰 걸 자르도록 구현했는데, 이렇게 하면 주어진 테스트 케이스도 맞추지 못한다. 나무1 나무2 나무3 나무4 나무5 1일째 1 3 2 4 6 2일째 3 10 5 8 1 3일째 5 7 8 12 2 4일째 7 14 11 4 3 5일째 9 7 14 8 4 => 6 + 10 + 12 + 14 + 14 = 56 이므로 최대치가 아니게 된다. 최대치를 구하기 위해서는 성장 속도가 제일 느린 것부터 더해주어야 한다. 왜냐하.. 2022. 6. 17.
[2022 우아한테크캠프 5기] 코딩/과제 테스트 후기 사전 접수 처음 공고를 보고 우아한테크코스랑 비슷한 교육 과정인 줄 알았는데 인턴 과정이 포함되있는 신입 개발자를 뽑는 중요한 공고인 걸 뒤늦게 알았다. 사전 접수는 별도의 이력서 제출없이 프로그래머스에서 바로 신청이 가능했다. 그래서 부담없이 바로 안드로이드 분야로 지원했다. 1차 코딩테스트 후기 150분 동안 총 4문제가 나왔다. 4문제 모두 못 풀 정도의 난이도는 아니였던 것 같다. 카카오의 쉬운 문제?랑 비슷한 느낌...? 근데 잘하는 사람들 기준에서는 쉬웠을 것 같다. 기억에 구현이랑 dfs 문제가 나왔던 것 같다. 나는 4문제 중 3솔, 마지막 문제 조금 건드리다가 제출 했는데 이게 채점의 기준에 포함되는지는 모르겠다. 안드 기준에서는 3솔이 커트라인 같은데, 주변 풀스택 지원 후기를 들어보면.. 2022. 6. 15.
[백준] 1519번 부분 문자열 뽑기 게임 자바 문제 1519번: 부분 문자열 뽑기 게임 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 dp배열을 이용하여 해당 게임 판에 써져 있는 N에서 진 부분 문자열을 빼서 만들 수 있는 모든 수의 승패여부를 확인한다. dp[x] = 숫자 x에 대해서 패배하는지 승리하는지의 여부 저장 (0:아직 모름/ 패배:-1/ 승리: 승리하기 위한 최소 부분문자열) dp[N+1]로 잡아서 숫자1부터 N까지 담을 수 있도록 한다. 그리고 N이 일의 자리인 경우 부분 문자열을 고를 수 없으므로 무조건 게임에서 지게된다. 따라서 우선 dp[1] ~ dp[9]까지는 -1을 담아 두고, N값에서 부분 문자열을 뺀 값부터 dp적용을 한다. 예를 들어 dp[10]은 .. 2022. 6. 13.
[백준] 2075번 N번째 큰 수 자바 문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 처음에는 배열의 맨 아래 행만 정렬시킨 후 ArrayList에 담아, 두 개의 포인터를 이용해서 꺼내면서 이동시켜가면서 N번째 수를 구하려고 했는데 우선순위 큐를 이용하면 훨씬 빠르고 간단하게 풀이가 가능하다. ✔️ Priority Queue (우선순위 큐) 일반적인 FIFO인 큐의 구조를 그대로 가지는데, 데이터가 들어온 순서대로 나가는 것이 아니라 우선순위를 먼저 결정한 후 우선순위가 높은 데이터부터 나가는 자료구조이다. N번째 큰 수를 구해야 하므.. 2022. 6. 11.
[백준] 4195번 친구 네트워크 자바 문제 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 풀이 HashMap을 이용하여 친구의 이름을 숫자로 표현해야 배열 인덱스를 이용할 수 있다. 그리고 union-find함수를 이용하여 두 친구 관계의 집합 크기를 늘려간다. 이때 연결 노드를 저장할 부모 배열외에 몇개가 연결되어있는지 누적하기 위해 count 정수형 배열을 하나 더 사용해준다. count배열에는 처음에 모두 1로 초기화해주고 해당 원소가 다른 원소로 합쳐질 때(부모값이 변경될 때) count값을 해당 원소의 최상위 부모 co.. 2022. 6. 8.
[백준] 5397번 키로거 자바 문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 문제 풀이 처음에 ArrayList와 idx변수 하나를 이용해서 list의 인덱스 번호를 옮겨가면서 값을 삽입하는 방법으로 진행을 했는데 시간초과가 떴다. 그래서 구글링해본 결과, Stack을 이용하는 방법과 ListIterator를 이용하는 방법 두 가지가 있었다. 두 가지 모두 풀이에 적용해 보았다. 먼저 ListIterator를 이용하는 방법은 기존 ArrayList에서 index를 바꿔나가는 방법과 로직을 동일하게 사용하고 사용 자료구조와 함.. 2022. 5. 31.

티스토리툴바