Door

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

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 상당히 까다로웠던 dp문제. DP+길찾기가 합쳐져서 어려웠습니다. #백준 1520번 내리막길 #시간초과 코드 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0,0] N,M=map(int,input().split()) room=[list(map(int,input().split())) for _ in range(N)] dp=[[0]*M for _ in ran..

알고리즘 공부 2022. 9. 29. 11:05

https://www.acmicpc.net/problem/22955 22955번: 고양이 도도의 탈출기 첫째 줄에 방의 높이 $N$ ($ 2 \leq N \leq 1\,000$)과 방의 너비 $M$ ($ 2 \leq M \leq 1\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에 공간의 상태가 주어진다. 공간의 상태는 $C$, $D$, $E$, $F$, $L$, $X$로 이루 www.acmicpc.net 구현+다익스트라가 합쳐진 독특한 구조. 다익스트라를 써서 가장 적은 체력으로 목적지에 도착하는 경우를 구합니다. 쌩구현이라 시간이 좀 걸리지만 크게 로직이 어려운 건 없었습니다. 주의할 점은 X에서 내려갈때, 바닥이나 문을 만나는 경우 이외에도 사다리를 만날 수 있다는 점입니다. 또, 사다리가 연속..

알고리즘 공부 2022. 9. 28. 18:29

https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 처음 문제를 마주하고 조금 까다롭다고 생각한 문제. 그래도 일반적인 bfs라 생각하고 문제를 풀이했습니다. #백준 9328 열쇠 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0,0] T=int(input()) def bfs(sx,sy): global answer global key global visited q=deque() q.append((sx,sy)) v..

알고리즘 공부 2022. 9. 28. 10:10

https://www.acmicpc.net/problem/5022 5022번: 연결 A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다. www.acmicpc.net 예전에 이 문제를 접하고 예시코드까지 보고도 뭔소리인지 몰라서 접었는데 다시 보니 풀이방법이 보였습니다. 이 문제는 bfs문제인데 좀 특이합니다. bfs를 총 2번 해야하며, 이전 bfs로 지나간 곳은 지나갈 수 없습니다. '그럼 bfs2번만 해주면 되는 쉬운 문제네요' 라고 생각하실 수 있겠지만 bfs특성상 모든 지역을 다 탐색할 수 있습니다. 아무리 heaq로 구해도 이미 거의 대부분 지역을 탐색한 뒤라서 다음 bfs에서 이상하게 됩니다. 그래..

알고리즘 공부 2022. 9. 27. 11:51