관찰과 질문, 그리고 데이터

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열의 크기가 백만 단위라서 N^2 의 DP로는 문제로 풀 수 없다. Binary Search를 활용해서 O(NlogN)으로 풀어낼 수 있다. 자세한 풀이는 최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기 LIS는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다. 개인적..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net BFS 문제. 2d array 대신 dictionary를 이용했다.

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으 www.acmicpc.net BFS로 해결할 수 있는 문제.

https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 �� www.acmicpc.net 조건대로 구현하면 되는 문제.

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net DFS 문제. 두 달 정도 쉬었더니, 그새 구현방법을 다 까먹어서 엄청 버벅댔다. 잘 만든 코드는 아니니까, 나중에 더 세련된 방법으로 다시 풀어봐야겠다...

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 시뮬레이션 문제. pypy3으로는 통과하지만 Python3으로는 시간초과가 나는데, Python3 통과코드를 보고 어떻게 수정해봐도 내 코드는 더 이상 최적화가 안 된다. 왜지..?

https://programmers.co.kr/learn/courses/30/lessons/42894 코딩테스트 연습 - 블록 게임 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr 구현까지 시간이 오래 걸렸던 문제. 검은 블록을 채울 수 있는 모든 공간에 검은 블록을 채우고, 검은 블록과 설치된 블록을 합쳤을 때 직사각형 블록..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 윈도우 문제. 매번 윈도우 위치를 변경할 때마다 min함수를 사용할 경우, 시간복잡도가 O(n**2)가 된다. deque를 활용해 삽입/삭제를 빠르게 수행하되, deque에 값을 저장하는 방식을 약간 변경하면 효율적으로 연산을 수행할 수 있다. 아래 풀이에서 더 상세한 해설을 볼 수 있다. 백준 11003번 문제 (최솟값 찾기) with Java · 쾌락코딩 백준 11003번 문제 (최솟값 찾기) with Java 03 D..

https://programmers.co.kr/learn/courses/30/lessons/12977 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. combinations으로 숫자 세 개 뽑기 2. 뽑은 세 개의 숫자를 합한 값이 소수인지 판별하기.