Door

https://www.codetree.ai/frequent-problems/artistry/submissions 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 실제로 시험장에서 풀었었던 문제... 그 당시에는 테케 10개 중에서 4개까지만 맞아서 엄청 해매고 써렌쳤던 아픔... 3시간동안 풀거같은데 안풀리는 그 x같음이 잊혀지질 않네요. 이 문제를 단계적으로 쪼개보면 이렇습니다. 1. BFS로 구역을 구한다 2. 각 경계를 만나는 선분을 구한다 3. 돌려준다 제 기억을 되돌아보면 3때문에 시험장에서 뻘짓했습니다. 어라?1~2는 틀린게 없는데... 3이 문제인가... 그렇게 연습장 다 쓰고...

알고리즘 공부 2022. 10. 6. 13:17

https://www.acmicpc.net/problem/3101 3101번: 토끼의 이동 첫째 줄에 N, K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 300,000) N은 행렬의 크기, K는 토끼가 점프한 횟수이다. 둘째 줄에는 'U','D','L','R'로 이루어진 문자열이 주어진다. 이 문자열의 길이는 K이며, 토 www.acmicpc.net 이 문제를 보고 '지그재그로 가는 모든 경로를 다 구하자' 라는 마인드를 가지면 바로 시간초과. N이 10만까지 된다면 지그재그 하다가 시간이 다 소요가 됩니다. 결국 해당 좌표지점의 수를 예측해서 더하는 게 관건. 이 부분이 상당히 까다로웠습니다. 수학적 능력이 필요한 부분이라... 생각하기 상당히 어렵습니다. 제 나름대로 스스로 풀어볼려다..

알고리즘 공부 2022. 10. 5. 22:44

https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 방법이 다양한데 저는 백트레킹 기법을 썼습니다. 완전탐색하듯이 모든 케이스를 다 구하는 경우를 가정했습니다. from copy import deepcopy def dfs(depth, max_depth, shoot, max_shoot, lion, appach): global answer global max_cha if shoot > max_shoot: return if depth == ma..

알고리즘 공부 2022. 10. 4. 22:13

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀다가 헛웃음을 나오게 한 문제. 처음에 이 문제가 lv3이라해서 긴장했는데 읽다보니 상당히 쉬웠습니다. 문제에 있는거 그냥 구현만 하면 되네. 뭐야 개꽁인데? 효율성??뭐 얼추 맞겠지 뭐. 테케 다 통과 오케. 효용성...다 시간초과?? 아니. 이걸 어떻게 시간을 줄여? 고토 와타시가 뭘 잘못했지? 이걸 어떻게 시간을 줄이지? 하고 질문하기를 보니... 누적합이라는 걸 쓰지 않으면 시간이 절..

알고리즘 공부 2022. 10. 4. 19:22

https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현+수학이 들어간 문제. 먼저, 정수n을 k진법으로 바꾼다. 그 다음, 0이 나올때까지 숫자를 넣어주고 0을 만나면 그 숫자가 소수인지 판별해준다. 만약에 숫자가 남아있는데 진법으로 변환된 수를 다 돌았다면 그 숫자가 소수인지 판별해준다. 여기서 주의할 점은 소수판별법입니다. 2~제곱근+1한 값까지 나눴을때만을 구해야 시간초과를 피할 수 있습니다. import math def prime(n): ..

알고리즘 공부 2022. 10. 4. 15:32

https://www.acmicpc.net/problem/11567 11567번: 선진이의 겨울 왕국 첫 번째 테스트 케이스의 경우에는 (1,6) → (2,6) → (3,6) → (4,6) → (4,5) → (4,4) → (4,3) → (4,2) → (4,1) → (3,1) → (2,1) → (2,2) → (2,3) → (1,3) → (1,2) → (2,2) 의 순서로 가면 탈출이 가능하다. www.acmicpc.net 문제 조건이 헷갈려서 체감적으로 까다로울 수 있는 문제. 이 문제에서 주의할 점들. 1. 도착점이 이미 X일 수 있다는 점. 2. 움직일 때 추락이 가능하다는 점. 3. 출발,도착점이 같을 수 있다는 점. 여기서 2번이 직관적으로 와닿지 않는데요. 그냥 일반적인 탈출만 생각하면 '시작점과..

알고리즘 공부 2022. 10. 4. 10:34

https://www.acmicpc.net/problem/12908 12908번: 텔레포트 3 첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000) 셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000) 입력으로 주 www.acmicpc.net 이 문제는 언뜻보면 bfs같았지만 좀 다르게 풀어야했습니다. #백준 12908번 텔레포트3 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0,0] sx,sy=map(int,input().split()) ex,ey=map(int,input().spli..

알고리즘 공부 2022. 10. 3. 17:40

https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 나온지 좀 된 문제인만큼 푸는 사람도 많은 문제. 그리고 고통받는 사람도 참 많은 문제. 이 문제는 단순한 bfs로 풀면 안 됩니다. '방향'이 중요하기 때문. 방향에 따라서 움직임이 카운트가 되기 때문에 이를 신경써줘야합니다. 주의할 부분들 살펴보면 1. K이동-->최대 3개까지 이동이 가능합니다. K이동시 벽을 만나면 멈춥니다. 단, 이전에 방문한 곳을 또 지나칠 수는 있습니다. 만약 0 0 0 인데, ..

알고리즘 공부 2022. 9. 29. 23:42