취업 준비 및 일상

https://www.acmicpc.net/problem/3663 3663번: 고득점 현수는 조이스틱을 이용해 지렁이를 미로에서 탈출시키는 게임을 하고 있다. 최고 점수를 얻은 경우에는 조이스틱을 이용해서 이름을 입력해야 한다. 이름을 입력하는 과정은 다음과 같다. 가 www.acmicpc.net or https://programmers.co.kr/learn/courses/30/lessons/42860# 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 풀이 0) 글자 바꾸는건 별로 안 어렵..

https://programmers.co.kr/learn/courses/30/lessons/42627# 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 (요청 시간, 소요 시간)을 갖는 class Job을 만듭니다. 우선순위 큐 2개(pq1, pq2)를 선언하는데, pq1은 요청 시간이 작은 순, pq2는 소요 시간이 작은 순으로 배열하도록 합니다. pq1은 현재 시간 t보다 요청 시간이 큰(==현재 할 수 없는) 일, pq2는 현재 시간보다 요청 시간이 작거나 같은(==현재 할 수 있는) 일을 담..

https://www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 풀이 특별할 거 없는 구현입니다. 다만, 행, 열 표기법이 익숙하지 않은 방식으로 제시되니 잘 변환하도록 합니다. 배운 점 이동을 한 후 벽 or 로봇에 부딪히는지 움직임 처리를 반복문을 쓰지 않고 한번에 이동을 시킨 후 체크를 하니 틀렸다. 유사한 문제가 있었는데, 그 때 그런 식으로 풀었던 경험이 독이 되었다. 역시 구현은 한번 집중 흐트러지면 디버깅이 지옥이 된다.. ..

https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 풀이 특별할 거 없이 8!가지의 위치 조합을 순열 함수를 통해 구하고, 조건문에 해당하면 1씩 더해주어 answer를 return하면 됩니다. 문자열 처리를 살짝 곁들인 백트래킹? 백준이면 실버 1 정도 될 듯합니다. 역시 카카오가 문제 퀄리티가 좋네요. 배운 점 프로그래머스에서는 채점 시 solution을 여러 번 사용하기에, 전역변수를 선언했다면 solut..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 일반적인 구간 DP 문제입니다. dp[i][j]를 'i번째 파일부터 j번째 파일까지 합치는 최소 비용'이라고 하면, dp[i][i+k] = min(dp[i][i+j]+ dp[i+j+1][i+k] + 'i번째 파일부터 j번째 파일의 용량')(for j in range(1, k))이 됩니다. 여기서 'i번째 파일부터 j번째 파일의 용량'은 누적합을 구하여 처리하면 됩니다. 배운 점 당연..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 장애물이 있는 범위를 누적합을 통해 구하면 됩니다: 가령, H=7이고 석순의 길이가 3이라면, 1, 2, 3이 영향을 받으므로, '석순 배열'의 3번째 index에 1을 넣고, H에서부터 1까지 누적합을 구하면 높이가 3인 석순이 1, 2, 3에 영향을 끼친다는 것을 구현할 수 있습니다. 반대로, 종유석의 길이가 3이라면 이는 7, 6, 5에 영향을 미치기에, '종유석 배열'의 5(=H+1-종유..

https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 솔직히 누적합 유형 문제는 껌이라고 생각했는데, O(N^2) 브루트포스 풀이말고 생각이 전혀 안 나더라... 내가 껌이였고 풀이 1. 누적합(sum[i]: 0번째 index부터 i번째 index까지의 합)을 구한다. 2. value는 Integer, key는 long으로 하는 map을 선언한 후, (0, 1)을 넣어준다. 이는 0..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 풀이 dp[i]를 'N을 i번 사용하여 만들 수 있는 숫자들의 집합'이라고 정의합니다. 일단, 보기처럼 N=5일 경우, 5, 55, 555, ... , 55555555와 같이 '붙여 만드는 값'은 사칙연산으로 만들어지지 않기에 대응되는 dp[i]에 넣어줍니다. dp[i] = (j는 1부터 i-1까지) (dp[j]의 원소)와 (dp[i-j]의 원소)의 사칙연산으로 모든 원소를 만들 수 있습니다. i = 2부터 8까지 반복문을 돌면서 차근차근히 모든 원소를 찾아줍니다. 이후 numbers가 있는 가장 작은 set을 찾아 해당 set의 index..

https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제 설명 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다...

https://www.acmicpc.net/problem/2196 2196번: 이진수 XOR 길이 B(1 ≤ B ≤ 16)인 이진수들이 E(1 ≤ E ≤ 100)개 있다. 이 이진수들을 두 개씩 선택하여 XOR연산을 하여, 어떤 이진수를 만들려고 한다. 이 과정에서 만들어지는 이진수들을 이용하여 XOR연산을 www.acmicpc.net 문제 길이 B(1 ≤ B ≤ 16)인 이진수들이 E(1 ≤ E ≤ 100)개 있다. 이 이진수들을 두 개씩 선택하여 XOR연산을 하여, 어떤 이진수를 만들려고 한다. 이 과정에서 만들어지는 이진수들을 이용하여 XOR연산을 해도 되며, 같은 두 이진수를 XOR연산을 해도 된다. 만약 우리가 만들고자 하는 이진수를 만들 수 없다면, 이 이진수와 제일 가까운 이진수를 만들려고 ..