본문 바로가기

분류 전체보기

 (120)
[BOJ] 2023. 신기한 소수(Python) / DFS www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 원래 8자리로 10 ** 8 짜리 리스트로 에라토스테네스의 체를 사용해 미리 소수 0, 1 테이블을 만들어놓으려고 했는데, 메모리를 보니 4mb로 매우 작아서 백트래킹(Backtracking)으로 재귀로 들어오는 temp 값의 소수여부를 확인해 가지치기했다. 출력되는 소수값을 자세히 보면 맨 앞자리 수는 2, 3, 5, 7만 올 수 있고 2~N자리 수까지는 1, 3, 7, 9만 올 수 있어서 이를 반..
[BOJ] 2206. 벽 부수고 이동하기(Python) / BFS www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 꽤 고차원적인 BFS 문제이다. 이 문제 사실 4번째 푸는 문제더라.. 그 와중에 1시간 반 정도 걸려서 풀었다, 인풋부터 잘못 받아서 계속 틀렸다. int가 아니라 str로 받아서 자꾸 BFS를 퍼트리지 못했다ㅠㅠ bfs 함수 안에서 꽤 헤맸다. 폭탄 가지고 있을 때, 없을 때를 다른 visited에 표현 큐에 폭탄(벽 부술 기회) 정보와 위치 정보를 담으면서 BFS 퍼트리는 것이 핵..
[BOJ] 2661. 좋은 수열(Python) / Backtracking www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 깔끔한 Backtracking 문제였다. 1시간 22분 소요 Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다. 개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것이다. 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 고려할 수 있는 경우의 수를..
[SWEA] 5650. 핀볼 게임(Python) / Simulation swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com SW Expert Academy 삼성 SW 역량 테스트 모의 문제에서 평범한 난이도의 시뮬레이션 문제이다. 1시간 1분 소요 특별한 알고리즘 X, 있는 그대로 구현하는 simulation 문제 웜홀 정보 딕셔너리(wormhole_info)에 저장하여 웜홀 만났을 때 즉시 위치 바꿔줌 블록별로 상하좌우에서 왔을 때 어떻게 방향이 바뀌는지 change_dir에 정보 미리 저장해둠 파이썬 코드는 다음과 같다. # 상하..
[SWEA] 2383. 점심 식사시간(Python) / DFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com SW Expert Academy 삼성 SW역량테스트 모의 문제들 중에 개인적으로 난이도 극상의 문제라고 생각한다. pass까지 3시간 조금 넘게 걸렸다. dfs 재귀로 조합 구현하여 계단 선택 완료 - comb() 함수(23분 소요) 이후 2시간 될 때까지 열심히 코드 짰는데 50개 tc 중 45개만 맞음.. 하.. 다음 날 아침 1시간 동안 디버깅해서 겨우 pass 받았다. 디버깅으로 고통스러웠지만 내 힘으로 ..
[SWEA] 4013. 특이한 자석(Python) / DFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 난이도가 낮은 편에 속하는 SW Expert Academy 삼성 SW 역량 테스트 모의 문제이다. 41분 소요로 워낙 많이 풀어본 문제라 오래 걸리지 않았다. DFS의 구조를 익힌 것이 도움이 됨 dfs 함수 안에서 num이 3보다 작을 때와 0보다 클 때를 모두 봐야 해서 둘다 if 조건문을 걸어줘야 한다! 오른쪽/왼쪽 방향 살피기(자성 같거나 달라서 회전할 수 있는지 여부 확인하며 재귀로 넘기기) 마지막에 자..
[SWEA] 5644. 무선 충전(Python) / BFS + Simulation swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성 모의 SW역량테스트 문제 중 어느정도 난이도가 있는 문제에 속한다. 1시간 37분 소요. BFS + Simulation BFS로 각 BC의 충전 범위를 그려줌(다음에 풀 때는 BFS 안 쓰고 위치의 절대값으로 BC의 범위를 그려보자) 핵심은 두 개 이상의 BC의 범위가 겹칠 때, 성능이 큰 순으로 내림차순 정렬하는 것. 이동할 때, 시작 위치도 포함해야 함. 가장 까다로운 부분은 두 사람이 같은 BC에 있는..
[SWEA] 4014. 활주로 건설(Python) swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어렵지 않은 삼성 모의 SW역량테스트 문제였다. 문제 푸는 데 1시간 정도 소요. 가로(행) 탐색, 세로(열)의 모든 케이스를 check_slope 함수에 넣어 가능하면 1, 불가능하면 0 리턴. check_slope () 함수에서 같은 높이이면 cnt += 1 높이 1 높아질 때, 그동안의 쌓아온 거리가 경사로 길이보다 크거나 같다면 가능한 경우이므로 cnt = 1로 초기화 높이 1 낮아질 때, 현재 쌓아온 거..

티스토리툴바