실전 압축 코딩

https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 알고리즘: DP + 타일링 작년 겨울에 실제로 응시 했던 카카오 겨울 인턴쉽 문제 이다..당시 다른 문제들은 풀거나, 풀지 못해도 부분 점수라도 얻었었는데, 시간의 압박 때문인지 아님 타일링 알고리즘 자체가 많이 낯설었는지 손도 못댔던 문제이다. ( 타일링 알고리즘은 해당 문제를 풀면서 알게 되었다..) 하지만, 집중력을 가지고 다시 풀어보니, 생각보다 할만했던 문제 였던거 같다.풀이이 문제에서의 ..

- 누적합 계산시[0,0] 에서 [x,y] 까지 구한다 -> sum[x][y] = sum[x-1][y] + sum[x][y-1] - sum[x-1][y-1] (중복된 영역)  - 구간합을 구할때 ->[x1,y1] 에서 [x2, y2] 까지 = OD(sum[x2][y2]) - OB(sum[x1-1][y2]) - OC(sum[x2][y1-1]) + OA(sum[x1-1][y1-1])(중복된 영역)

https://school.programmers.co.kr/learn/courses/30/lessons/42894?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 빡센 구현문제. 그래도 해설 안 보고 풀었다...! 풀이 블록이 사라지긴 위해선 2*3 혹은 3*2 직사각형 크기가 되어야 한다. 이는 해당 블록의 빈 공간에 검은 블록이 채워져 있으면 블록이 사라짐을 의미 한다. 구현 아이디어 1. 블록 삭제 사이클을 돌리기전 사전 작업을 수행한다. 이는 맨 위 블록이 닿기 전 까지 모든 수직 배열에 검은 블록을 채우는 것이다. 검..

https://school.programmers.co.kr/learn/courses/30/lessons/92345?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간만에 알고리즘 관련 글을 써본다. 그만큼 신박했던(?) 문제였기에, 포스팅을 하기로 했다. 문제에서 요구하는 알고리즘 자체는 간단하다. board의 크기가 최대 5x5 이기 때문에, 백트래킹과 dfs을 이용해 완전탐색을 수행한다. 하지만, 문제에서 말하는 항상 이길 수 있는 플레이어와 항상 지는 플레이어에 대한 이해를 못햇다... 그래서 처음에는 단순히 서로가..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 알고리즘: dp + dfs 1. 판다는 대나무를 먹고 상,하,좌,우로 이동한다. 하지만 여기서 제약 조건이 붙은데, 반드시 대나무가 더 많은 곳으로 이동해야 한다는 것이다. 2. 해당 조건을 토대로 dp의 메모제이션 기법을 사용 할 수 있다. 이동한 장소를 기준으로 얼마나 생존할수 있는지를 계산해 각 생존일을 장소 마다 저장시키면 된다. 3. for문을 돌며, 시작 장소를 정한다. 시작..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 유형: 다익스트라 + dp 처음에는 포장할 도로를 조합하고, 이를 매번 다익스트라로 돌리려고 했다. 그리고 해당 결과물을 dp의 메모제이션 기법을 사용하려고 했으나, 어딘가 잘못됨을 느끼고 결국 구글링을해 풀이를 봤다. 문제의 핵심은, 1. 해당 노로 가는 경로를 '포장을 할 때' 와 '포장을 하지 않을때'로 구분 해야 한다. 2. 다익스트라의 최단거리 저..

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 투 포인터 문제이다. 해당 문제의 핵심은 1. 수의 범위는 정수다. 즉, 음의 정수와 0이 포함된다. 2. for loop을 통해 검사하고자 하는 배열에 현재 index가 포함되면 안된다. 위의 두가지 핵심을 놓쳐 조금 헤맸다... 일단 문제 풀이는 1. 수를 정렬한다. 2. 정렬된 배열의 for loop을 돌면서 투 포인터 알고리즘으로 수의 합을 계산한다. 3. left index는 항상 0번으로, right Index는 ..

https://velog.io/@1998yuki0331/Python-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9-%EC%A0%95%EB%A6%AC 원소 추가 - num 번째 인덱스에 원소 추가 - s |= (1

5214번: 환승 (acmicpc.net) 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 누구나 쉽게 BFS를 떠올릴수 있지만 메모리와 시간 초과를 피하기 위해 새로운 발상이 필요했던 문제. 풀이 알고리즘 파악 BFS 일반적인 BFS 방식으로는 메모리 초과나 시간 초과가 날 수 밖에 없다. 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M의 범위는 1≤K,M≤1,000이다. 하이퍼튜브 하나당 정점끼리 K*K 개의 간선이 연결되므로 그래프의 총 간선의 개수는 최악의 경..

5719번: 거의 최단 경로 (acmicpc.net) 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 알고리즘 파악 다익스트라 + DFS 출발점 S에서 D까지 가는 최단경로를 구하는 문제이다. 단, 단순한 최단경로가 아닌, (복수의) 최단경로를 제외한 나머지 경로에서의 최단거리를 구하는 것이다. 구현 총 두번의 다익스트라와 dfs를 통한 경로 탐색을 진행한다. 1. 다익스트라를 돌려 최단길이를 모두 구한다. 이 과정에서 이차원 boolean 배열인 route에 경로를 저장한..