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

https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 문제는 문제에 맞는 점화식 설계를 못하면 정말 풀기 힘들다... 처음엔 문제 조건에 맞게 백트래킹 형태로 풀어봤지만 시간 초과가 나왔다. DP로 문제를 풀어내려면 1. 무게 또는 면접 중심으로 벽돌을 정렬한다. 2. table[i] ..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 내가 Python을 써서 그런 건지, 애초에 메모리 제한이 128로 작아서 그런 건지는 모르겠지만 DP가 아니면 문제 자체를 풀 수가 없었다. 문제의 논리 그대로 bfs를 적용하면 메모리 초과가 발생하고, 그나마 DP를 쓸 때조차도 반복문 잘못 세워서 메모리 초과를 숱하게 띄웠던 문제. 고수분들의 고견을 구하고 싶습니다. Python의 작업이 어떻기에 위의 두..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 가장 긴 증가하는 부분수열 문제. Longest Increasing Subsequences라고도 불리며, DP로 풀 수 있는 보편적인 문제유형 중 하나라고 한다. 풀이 설명은 아래 블로그에서 그림으로 자세히 볼 수 있다. https://bitwise.tistory.com/215 백준 11053번: 가..

그래프에서, 연결할 수 있는 점을 전부 연결하는 형태의 문제. bfs나 dfs 중 어느 것을 써도 해결 가능하며, 나는 bfs로 풀었다. 효율성 통과조건이 꽤 빡세게 설정되어 있는 것 같았다. visited를 2D List 대신 set으로 구현하니 풀렸다.

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net Knapsack Problem으로 유명한 문제, DP의 대표적인 유형이라고 한다. 상세한 문제 풀이는 이곳에서 볼 수 있다. https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C [DP..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마 www.acmicpc.net bfs 문제유형 2. 대신, x, y축에 이어 z축이 추가된 형태다. 처음부터 토마토가 전부 익어 있는 경우는 데이터를 받는 과정에서 먼저..

https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다. 개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 카카오 신입 개발자 공채 관련 기사를 검색해보았다. 카카오 첫 공채..'블라인드' 방식 채용 카카오, 합병 후 첫 programmers.co.kr Python 정규식과 Counter를 이용해 풀 수 있는 ..

백준 '유기농 배추' 문제와 푸는 방식이 똑같다. image의 시작부터 끝까지 훓으면서, 방문하지 않은 좌표마다 bfs로 인접좌표에 같은 색상이 있는지 확인한다. bfs 함수를 호출할 때마다 count를 1씩 올려 주면 해결.

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net bfs로 풀 수 있는 문제. 수빈이 한 번 이동한 위치를 다시 가지 않도록 visited 좌표관리를 해야 한다.

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net bfs 문제풀이 방법을 익히기 위해 풀었던 문제. 2차원 배열에 배추가 있는 좌표만 기록한 후, 배열을 돌면서 배추가 있을 경우 bf..