본문 바로가기

📖 Algorithm15

[Set & List] 성능 차이 코딩 테스트를 준비하며 백준을 풀고 있었습니다. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 바로 이 문제인데요? 생각보다 간단한 문제이고 쉽게 풀었는데, 계속 시간 초과가 났었습니다.. 원인이 무엇인고, 하고 봤습니다. 첫 번째 문제 입력한 숫자 만큼 정수를 받아서 자료구조에 저장하고 contains로 비교할 생각이었습니다. 당연히 정수이므로 Integer로 제네릭을 선언했는데, 이게 변환과.. 2022. 10. 29.

2022.07.07 [Lv.2 괄호 변환] https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드.. 2022. 7. 7.

2022.06.27 「LV.2 하노이의 탑」 여느 때와 같이 프로그래머스에서 문제를 풀고 있었다. 자료구조, 알고리즘 고득점 kit를 어느 정도 풀었기 때문에, 특별한 기준을 두고 문제를 고르진 않는다. 문제들을 보다가 하노이의 탑이라는 문제가 눈에 띄었다. 워낙에 재귀 함수를 이용한 풀이로 유명하지만 실제로 한 번도 풀어본 경험이 없었다. 그래서 한번 풀어보기로 결심했다. 근데 이게 웬걸. 생각보다 내가 재귀에 대한 개념이 부족하다는 걸 느끼면서 푸는 시간과 이해하는 시간이 거의 3일은 걸렸던 것 같다. 프로그래머스에서 같은 레벨이라도 난이도는 천차만별인듯하다. 당장에 카카오 기출만 보더라도...(기준이 뭘까..) 어찌 됐든 겨우 이해해서 그 풀이과정을 기술해볼 생각이다. https://programmers.co.kr/learn/courses/3.. 2022. 6. 27.

2022.06.22 「Lv.2 Jadan Case」 https://programmers.co.kr/learn/courses/30/lessons/12951 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고 programmers.co.kr 문제 설명 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세.. 2022. 6. 22.

2022.06.22 「Lv.2 N-Queen」 이번 주는 코딩 테스트 연습에 더 박차를 가해볼 계획을 짰다. 다음 주에 모의 테스트를 볼 계획이므로 비중을 좀 더 둬봐야겠다. 이번 기회에 자료구조 한번 더 정리해볼 계획도 구상했다. https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 문제 설명 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경.. 2022. 6. 22.

2022.06.15 「Lv.2 오픈채팅방」 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 오픈 채팅방 카카오톡 오픈 채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김 크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리 자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네.. 2022. 6. 15.

2022.06.14 「Lv.2 멀쩡한 사각형」 문제 설명 가로길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자 칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭짓점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solutio.. 2022. 6. 14.

2022.06.08 「Lv.2 문자열 압축」 https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제 설명 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 .. 2022. 6. 8.

2022.05.31 「Lv.3 디스크 컨트롤러」 오랜만에 코테 문제를 풀어보았다. 힙 자료구조를 이용한 문제인데, 주로 우선순위 큐를 이용해 문제를 풀면 된다는 것을 배웠다. 프로젝트 때문에 시간이 거의 안 나는데 짬짬히 푸려고 노력을 좀 해야겠다. 풀이 과정을 설명하겠다. 문제 설명 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 제한 사항 jobs의 길이는 1 이상 500 이하입니다. jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다. 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다. 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다. 하드디스크.. 2022. 5. 31.

2022.05.24 「Lv.3 입국심사」 요새 프로젝트 비중이 너무 컸던지라 오랜만에 시간이 나서 코테 문제를 풀었다. 자료구조 중에서 이분 탐색 (Binary Search)을 이용한 문제이다. 얼핏 보니까 출제율이 낮던데 그래도 이론 상 알고 가는 게 아니라 직접 문제를 풀어보아야겠다는 생각이 들어 문제를 풀고 정리를 해보겠다. 이분 탐색 (Binary Search) 이분 탐색 알고리즘이란 최소, 최대 값을 정해 두고 반으로 나누어 가며 중간 값을 검사하며 탐색을 하는 알고리즘이다. 시간 복잡도로 O(logN)을 갖고 있는 탐색 알고리즘이다. https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있.. 2022. 5. 24.

2022.05.18 「Lv.2 Heap 더 맵게」 자료구조 정리해야지 계획만 하고 눈으로만 개념들을 보고 정리하고 있다.. 눈으로 읽고 코드 작성해봐도 어느 정도는 감이 오는 것 같지만 빠른 시일 내에 정리 좀 해야겠다 정말 오늘은 오전에 Heap을 이용한 문제를 풀었다. Lv2이다. 예전에는 Lv1도 어려웠고, 문제 자체도 이해가 안 되었는데 풀다 보니 좀 감이 오는 듯하다..?? 두 달 안에 Lv3까지 마스터 목표를 잡자. 취업하고 싶다!! Heap이란 자료구조는 완전 이진트리와 거의 비슷한데 예전에 잠깐 이진 트리에 대해서 개념을 본 기억이 있었는데 개념을 먼저 보고 문제를 풀었다. 결국 Heap이 우선순위 Queue (PriorityQueue)를 구현하기 위해 Heap을 이용하는 건데 그와 비슷한 문제이므로 이를 이용하여 문제를 풀었다. 문제 설.. 2022. 5. 18.

2022.05.17 「Lv.2 프린터」 문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 .. 2022. 5. 17.

2022.05.16 「Lv.2 카펫」 오늘은 프로그래머스에서 완전 탐색 문제 중 레벨 2의 카펫 문제를 풀며 정리를 해보겠다. 항상 느끼는 거지만 자료구조에 대해 정리 좀 해야겠다. 풀 순 있는 문제라도 자료구조에 대한 개념을 이용해 푸는 것과 내 방식대로 푸는 것은 나중에 큰 차이가 있을 것이 분명하므로 오늘이나 이번 주 안에 무조건 정리하는 것으로 하자! 문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 .. 2022. 5. 16.

2022.05.12 「LV2 소수 찾기」 여느 날처럼 코테 문제를 계속 풀고 있다. 자료구조도 날 잡아서 한번 정리해야 되는데 시간이 좀 나질 않는다. 시간 배분 좀 잘해보자. 어제오늘 푼 것이 소수 찾기라는 완전 탐색 문제인데, 이건 소수라는 것이 결국 1과 자신만을 약수로 가지는 수를 말한다. 어떤 블로그에서 봤는데 결국 문제를 간소화하는 게 관건이라는데 그것을 보는 안목을 좀 길러야겠다. 소수 찾기 소수 : 1과 자기 자신만을 약수로 가지는 수 String 숫자 값을 받아 소수를 조합하는 개수를 구하는 문제이다. import java.util.HashSet; import java.util.Iterator; class Solution { HashSet numberSet = new HashSet(); /** * 소수 확인 메서드 * @para.. 2022. 5. 12.

2022.05.09 「해시 Lv.2」 요새 매일매일 코테를 준비하며 프로그래머스 문제를 풀고 있다. 처음엔 완전히 막혔지만 그래도 이젠 어느 정도 풀이가 떠오르긴 한다. 한 가지 아쉬운 점은 생각보다 클래스마다 다양한 메서드를 가지고 있고 이를 잘 알고 활용해야 한다는 점이다. 제일 많이 나오는 유형인 해시 문제를 마주하고 문제를 풀기 위해 활용할 메서드를 검색해서 이를 활용하여 문제를 풀었지만 한번 정리해볼 만한 가치가 있다고 생각이 들어서 이렇게 정리하게 되었다. 문제 설명 위장이라는 문제인데, 옷의 종류와 옷의 이름으로 이루어진 2차원 배열을 가지고 그 경우의 수를 구하는 문제이다. 매일 옷을 다르게 입어야 하고, 하루에 옷 1개는 무조건 입는 조건이다. 해시를 이용해 풀란다. 풀이 public int solution(String[][.. 2022. 5. 9.

이전 1 다음

티스토리툴바