Door

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 이 문제는 백트레킹 문제중에서 난이도가 상당히 높은 문제. 우선 제가 초기에 풀었을 때는 '정석(?)'대로 대각선이 비어있는지 확인해주고 비숍을 넣는 방식이었습니다. import sys sys.setrecursionlimit(10**8) N=int(input()) room=[list(map(int,input().split())) for _ in range(N)] ga=[False]*(2*N-1) sa=[F..

알고리즘 공부 2022. 10. 8. 11:16

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 의외로 이 문제로 헤메는 사람이 많고 저 역시나 제법 오랜 시간 뻘짓했다가 풀었습니다. 예전에 이 문제와 유사하게 밖으로 나가는 경우를 구하는 문제가 있었습니다. 해당 문제의 경우처럼 전체 크기를 h+2 x w+2로 해줬습니다. 기존 입력한 거에서 ['.']*(w+2)행을 위 아래로 추가 각 열 앞뒤에 '.'을 추가해줬습니다. 그럼 사람의 x,y좌표가 0or h+1 0 or w+1이면 탈출. 그런데 제출하고 ..

알고리즘 공부 2022. 10. 8. 00:36

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/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