안토니 블로그 안토니 블로그

코딩테스트 연습 2018 KAKAO BLIND RECRUITMENT [1차] 셔틀버스 https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 문제 이해에 꽤나 애를 먹었다. 설명이 좀 난해하게 작성되어있어 잘못 이해한채로 풀다보니 삽질을 오래했던 문제이다. 결과적으로 구현은 쉬웠지만 실제 시험장에서 마주했더라면 손도 못댔을 것 같다. 이 문제를 풀기 위해선 문제의 핵심인 "셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각"을 ..

문제 설명 https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다. 자 이제 가운데 물을 더 추가했다고 ..

소개 BOJ19583.swift 매번 보던 패턴과 풀이방법은 굳이 안올리는 편이라 알고리즘 풀이는 잘 올리진 않았습니다. 하지만 이번 문제는 되게 재밌게 풀었던 기억이 있어서 올렸습니다. https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net 설명 문제를 다 읽고난 뒤에 생각해보면 특이한 점을 발견할 수 있습니다. 이 문제는 특이하게도 입력의 개수가 몇개인지 알 수 없고, 모든 입력이 종료가 되면 정답을 출력해야..

개요 전형적인 탐색 문제였다. 문제에서 찾아야 하는 것은 단지의 수와 각 단지에 속하는 집의 수다. 단지의 수를 구하는 것은 간단하다. 방문을 했던 곳은 가지 않고 갈 수 있는 곳만 가면서 확인하면 된다. 집의 수를 구하는 법은 여러 방법이 있다. BFS 일 경우 갈 수 있는 Queue를 추가할 때 마다 Count를 센 뒤에 그 값을 출력하면 될 것이며 DFS라면 Depth를 들어갔을 때 마다 Count를 늘려가며 세는 방법이 있을 것 같다. 풀이 이 문제는 dfs 방식으로 접근해보았다. 또한 방문을 해야 하는 곳이 1, 했던 곳이 0으로 단순한 문제이기에 visited 배열을 사용하지 않고 풀 수 있었다. 방문한 곳은 0으로 바꾸어서 방문처리 했다. 1. global로 count를 둔 뒤에 depth를..

설명 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다. 좋은 수열을 구하여라 풀이 과정 아이디어를 떠올리는 것이 많이 힘들었다. 좋은 수열을 찾기 위해서는 수를 한개씩 추가할 때 마다 좋은 수열인지 반복해서 체크하는 과정이 필요했다. 또한 앞에서 아무리 좋은 수열 이었어도 뒤에 붙이는 숫자에 따라 나쁜 수열이 될 수도 있었기 때문에 dp와 같은 방법은 사용할 수 없었고 모든 경우를 대입하는 백트레킹 기법을 사용해야만 했다. 생각해낸 방법은 뒤에 숫자를 붙일 때 마다 좋은 수열을 체크하는 것이었다. 체크하는 방법을 떠올리는게 가장 어려웠는데 결국에 생각해낸 방법은 다음과 ..

파이썬으로 먼저 풀고 swift로 풀었더니 비효율적으로 풀었던 것 같다. 풀이과정을 요약하면 다음과 같다. 1) 빈 배열 answer과 제거 가능 횟수 cnt를 선언한다. 2) numbers의 원소 각각에 대한 반복문을 진행한다. 3) 이때 answer이 비여있다면 숫자를 추가해준다. 4) 제거 가능 횟수가 있으며 현재의 num이 answer의 마지막보다 큰 경우엔 마지막 원소를 제거하고 제거 가능 횟수를 하나 차감한다. 5) 배열이 비거나 제거 가능 횟수가 0이 될 때 까지 4를 반복한다. 6) 배열에 num을 추가한다. 7) 만약 차감 횟수가 남아있음에도 원하는 결과를 얻었다면 반복문을 종료한다. 처음 풀이(not good) import Foundation func solution(_ number:S..

https://www.acmicpc.net/problem/23257 23257번: 비트코인은 신이고 나는 무적이다 코인 경력 4년차, 차트에 통달한 찬호는 이전 $N$개의 월봉을 통해 다음 월봉의 절댓값을 예측할 수 있는 아래의 공식을 만들어냈다. (다음 월봉의 절댓값) = 이전 $N$개의 월봉 중 중복을 허용해 www.acmicpc.net 문제에서... (다음 월봉의 절댓값) = 이전 N개의 월봉 중 중복을 허용해 M개를 골라 절댓값들을 bitwise xor 한 것 중 최대 라고 되어있다. 처음 문제를 보게 될때는 N개중 M개를 고르는 것으로 보여 조합으로 생각할 수도 있다. 하지만 경우의 수가 너무 많아지게 되어 풀 수 없으며 다른 방법을 찾아야만 한다. 먼저 문제를 이해하기 위해 주어진 예시로 설명..

1. 먼저 가장 적은 강의실을 사용하기 위해선 시작시간과 종료시간이 빠른 수업을 먼저 배치한다. 따라서 시작시간이 빠른 순서대로, 시작 시간이 같다면 종료시간이 빠른 순서대로 정렬을 해야한다. 2. 수업을 강의실에 배치할 때 종료시간이 수업의 시작시간보다 같거나 빠른 경우 같은 강의실에서 강의를 할 수 있다. 3. 수업을 강의실에 배치할 때 종료시간이 수업의 시작시간보다 늦는 경우 새로운 강의실이 필요하다. scd는 n개의 [시작시간, 종료시간]를 가지고 있다. 이 솔루션은 시간초과가 발생하였는데 오답의 원인을 생각해보니 N의 개수가 20만개이기 때문에 O(N^2)의 방법으로는 불가했다. scd가 빌때까지 순회를 하면서 skip(이전 종료시간)보다 현재 노드의 시작시간이 더 빠른 경우를 건너뛰었으며 그렇..