본문 바로가기

python33

백준 - 경사로 14890 백준에서 "경사로" 문제에 대한 풀이를 담고 있습니다.  백준 - 경사로 14890  블로그 목차  1. 풀이 2. 코드 3. 입력하기 4. 입력하기 추천글  풀이 - 골드급 문제지만 비교적 쉽게 풀었던 문제이다.- 파이썬이랑 자바를 편할대로 쓰면서 코테 준비를 하는데 특히 구현같은 경우는 파이썬이 훨씬 편하다..- 일단 아이디어는 다음과 같다. 1) 가로행과 세로행을 나누어서 탐색했다.- 그래서 아래 코드에 보면 입력을 받는 for문을 제외했을 때 첫 번째 for문은 가로행 탐색이고 두 번째 for문은 세로행 탐색이다.- 근데 로직이 다른 것은 아니고, 그냥 index의 증가가 가로로 증가하는지 세로로 증가하는지의 차이만 가지고 있다. 2) 평평하다가 갑자기 높이가 높아진 경우- 일단 기본적으로 길이.. 2025. 3. 19.
백준 - A와 B 2 12919 백준에서 "A와 B 2" 문제의 풀이를 담고 있습니다. 네이버, 삼성 코테 준비하시는 분들 모두 화이팅입니다.  백준 - A와 B 2 12919  블로그 목차  1. 아이디어 2. 코드추천글  아이디어 - 정말 간단한 아이디언데 빨리 떠올리지 못해서 아쉬웠다.- 최초에는 S를 이용해서 T를 만드려고 하다 보니 경우의 수가 너무 많아 시간 초과가 계속 났다.- 그러다가 거꾸로 T를 이용해서 S를 만드려고 하니 깔끔하게 조건이 두 가지가 필요했다. 1) 현재 문자열 t에서 가장 뒤의 문자가 A이면, 해당 문자를 제거한 t'을 만든다.2) 현재 문자열 t에서 가장 앞의 문자가 B이면, 해당 문자를 제거하고 뒤집어서 t''을 만든다.- 이 조건을 생각해내는 것이 꽤 어려운 부분인 것 같다.- 물론 B가 문자열 .. 2025. 3. 15.
프로그래머스 - 가장 먼 노드 lv. 3 단계의 코딩 테스트 연습 문제 중 '가장 먼 노드'에 대한 풀이를 설명하고 있습니다.  프로그래머스 - 가장 먼 노드  코딩 테스트 연습 문제 풀이  1. 원리 2. 코드추천글위의 목차를 클릭하면 해당 글로 자동 이동 합니다. 원리이 문제는 우선 순위 큐를 가지고 BFS를 돌리면 정말 금방 끝난다.다익스트라와 같이 이전에 탐색된 노드들의 거리를 갱신해줄 필요가 없는 이유는 간선의 거리가 모두 1로 통일이기 때문에 노드를 많이 거쳐가면 무조건 오래 걸린다.예를 들어, 다익스트라에서는 1->2로 이동하는데는 5가 걸리는데, 1->3->2로 가면 3이 걸릴 수 있다.따라서 특정 점에서 특정 점까지의 거리를 계속해서 갱신해야 한다.하지만, 현재 상황에서는 1->2가 1->3->2보다 무조건 빠르다는 .. 2025. 1. 2.
프로그래머스 - 아이템 줍기 lv. 3 단계의 코딩 테스트 연습 문제 중 '아이템 줍기'에 대한 풀이를 설명하고 있습니다.  프로그래머스 - 아이템 줍기  코딩 테스트 연습 문제 풀이  1. 원리 2. 코드추천글위의 목차를 클릭하면 해당 글로 자동 이동 합니다. 원리너무 너무 귀찮게 구는 문제였다.처음에는 사각형의 테두리와 그 내부를 모두 1로 칠하고, 외곽 라인을 BFS로 탐색하면서 도착 지점까지 가려고 했는데, ㄷ 자 모양에서 자꾸 건너뛰는 문제가 생겼다.또, 사각형의 높이 또는 너비가 1일 때, 사각형을 관통해버리는 문제도 있었다.(이제 생각해보면 이것은 조건을 통해서 해결 가능할 것 같다.)이 조건을 확인하는 방법이 궁금하면, 코드에서 line 33-45를 참고하면 된다.그래서 생각한 것은 사각형의 외곽 라인을 그래프처럼 x.. 2025. 1. 1.
프로그래머스 - 전력망을 둘로 나누기 lv. 2 단계의 코딩 테스트 연습 문제 중 '전력망을 둘로 나누기'에 대한 풀이를 설명하고 있습니다.  프로그래머스 - 전력망을 둘로 나누기  코딩 테스트 연습 문제 풀이  1. 원리 2. 코드추천글위의 목차를 클릭하면 해당 글로 자동 이동 합니다. 원리원리는 아주 간단하다.wires에 들어가 있는 간선을 하나 짜르고, 아무 점에서나 시작해서 BFS를 돌리면 된다.그렇게 BFS를 다 돌고 나서 방문하지 않은 노드가 있는지 탐색하고, 해당 노드에서 BFS를 한번 더 돌리면 두 개의 서브 트리를 다 순회한 것이다.BFS를 돌면서 몇 개의 노드를 거치는지 세고 담아두었다고 두 번의 BFS가 끝났을 때, 차이를 구하면 된다.코드는 아래와 같다.코드from collections import dequedef so.. 2024. 12. 25.
프로그래머스 - 피로도 lv. 2 단계의 코딩 테스트 연습 문제 중 '피로도'에 대한 풀이를 설명하고 있습니다.  프로그래머스 - 피로도  코딩 테스트 연습 문제 풀이  1. 원리 2. 코드추천글위의 목차를 클릭하면 해당 글로 자동 이동 합니다. 원리이 문제도 마찬가지로 DFS를 활용하면 된다.그런데 계산을 계속 하면서 DFS를 하기 보다는 순열을 만들면 된다.모르고 변수 이름을 comb로 지었는데 perm로 생각하는 게 좋을 것 같다...던전의 고유 인덱스를 기준으로 중복없이 하나씩 담는다.그러고 나서 던전 갯수만큼 담는 것이 완료되면, 담긴 순서대로 던전을 하나씩 돌아본다.그렇게 해서 몇 개의 던전을 돌 수 있는지 센다.이렇게 만들어질 수 있는 순열들에 대해 모두 계산해보고 가장 큰 경우를 저장하면 된다.dfs() 그리고 .. 2024. 12. 25.
반응형

티스토리툴바