Door

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제접근 1. 그래프를 사용하는 문제다 2. 최저요금이니깐 다익스트라를 쓰면 되겠구나 어려웠던 지점 합승??? 합승을 끝내는 지점or합승을 안하는 경우를 어떻게?? A,B각각을 S까지 갈 때의 최소비용을 구할까? 그럼 합승할 때 겹치는 걸 빼야하는데 이게 안되는데.... 시작점-합승끝내는 지점을 각각 구하고 그 지점에서 a,b거리를 구한다? 그럼 시작점-합승사이 bfs해주고 합승끝부터 a,b거리 ..

알고리즘 공부 2023. 3. 6. 12:03

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제접근 다익스트라를 활용한다는 게 바로 들어왔다. '최소비용'이라는 말을 읽자마자 heap을 활용해서 비용이 가장 적은 것을 빠르게 서치해야겠다 생각. 문제 설계 1. heappop,heappush를 활용해서 bfs랑 유사한 구도로 짠다. 2. 이전 방향에 따라 코너를 생성해야하기 때문에 초기 heap에 넣을때 상하좌우 모든 케이스를 넣어본다. 3. visited를 n*n*4(4는 상하좌우 방향..

알고리즘 공부 2023. 3. 2. 09:22

https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 초기 문제접근 1. 설치,삭제할 때마다, 해당 지점이 조건을 만족하는지 본다 2. 조건 구현해서 프로그래밍하자 막힌 이유 1. 조건을 잘못 잡은 거 같다 2. 추가,삭제 조건을 수행하면서 누락된 케이스가 존재했다. 개선한 풀이 1. 추가,삭제 후, 해당 board가 가능한지 반복한다 개선된 풀이로 진행할 경우, 코드가 더 깔끔해집니다. 현재 추가한 보드의 상태를 쭉 보면서 설치,삭제가 가능한지 보..

알고리즘 공부 2023. 3. 1. 14:35

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제접근 1. 경로 중 최단거리??완전탐색+백트래킹을 써야겠네 2. 상하좌우 우선순위를 생각한 탐색이니 탐색돌릴때 신경써야겠다 3. 갔던 곳 다시 갈 수 있다고???????bfs로 어떻게 구하지? 아... k만큼 가야하니깐 그 이상가면 안되니 굳이 visited쓰면서 할 필요는 없겠군. (갔던 곳을 다시 갈 수 있다는 규칙때문에 heap을 활용한 방법도 사용해봤으나 백트래킹이 가장 좋다고 생각해..

알고리즘 공부 2023. 2. 27. 23:39

https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 문제접근 문제에서 제시된 시뮬레이션대로 각 좌표를 돌면서 쿼리대로 수행했을 때 목표한 x,y지점에 가는지 판단 시간초과이유 n*m*query갯수 최악의 케이스를 고르면 10^9 * 10^9 *200000 그럼 어떻게 고쳐야할까? 구글링을 통해 알아낸 접근입니다. 1. 쿼리만 수행하도록 고쳐도 최대 200000으로 확 줄어든다. 2. 쿼리를 역으로 수행해서 모두 수행했을 때 x,y지점으로 들어..

알고리즘 공부 2023. 2. 23. 11:55

https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제유형 그래프 탐색문제. 방향이 없는 그래프이니깐 그래프를 초기화할 때 양쪽 전부 방향을 넣어주자 처음에 문제를 접근했던 풀이 1. gate,봉우리를 설정하면서 bfs를 구한다면 시간초과가 뜰 것이다. 2. gate,봉우리를 제외한 지점의 intensity구하기 3. gate지점과 봉우리의 intensity를 구하고, 그 중 가장 큰 값을 받는다 반례 위의 예시에서 1-4처럼 봉우리-출입구가 ..

알고리즘 공부 2023. 2. 20. 11:16

https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr bfs,dfs를 쓰는 거 까지는 캐치했지만 어떻게 활용할지 몰라서 구글링을 했습니다. 문제풀이 순서 1. table에 있는 블록의 좌표를 구한다 -->[0,0]을 기준으로 두고 블록의 좌표를 구하고 저장합니다. 2. 테이블을 90도로 돌려가면서 비교한다. -->테이블 배열을 돌려가면서 bfs를 해주고 해당 좌표의 블록이 있는지 찾아봅니다. 찾고 있으면 해당 블록을 제거해줍니다. 세세한 풀이 DFS..

알고리즘 공부 2023. 2. 17. 12:04

https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 눈물나는 주식을 알고리즘 문제로 낸 사악한 문제. 주식차트를 간단하게 그려봅니다. 주식의 현재값들을 계속 큐에 넣어주고 현재 가격과 비교를 하는 식으로 코드를 구성할 수 있습니다. 그런데, 그렇게 코드를 짜면 시간초과가 발생합니다. 왜냐하면 큐 전체를 다 돌아야하기 때문에 시간이 많이 소요가 될 수 밖에 없습니다. 근데 다시 생각해보면 모든 큐를 다 돌 필요가 없습니다. 현재 큐에서 가장 가격이 ..

알고리즘 공부 2023. 1. 13. 10:08