본문 바로가기

분류 전체보기

 (120)
[SWEA] 1953. 탈주범 검거 (Python) / BFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 5번째 풀어보는 문제라 거의 외우다시피 한 문제다. 풀 때마다 조금씩 아이디어가 달라지긴 하지만 큰 틀은 바뀌지 않는다. 깔끔한 BFS 문제로 pass까지 42분 소요했다. 터널 1~7가지 종류를 각각 상하좌우로 뚫려있는지 여부를 0, 1로 미리 마스킹해두어 현 위치에서 나갈 수 있고, 이동할 위치에서 들어올 수 있는지 확인하며 bfs를 탈주범이 갈 수 있는 위치를 확장했다. 고려해야 할 부분이라면, bfs 함수..
[BOJ] 2456. 나는 학급회장이다(Python) www.acmicpc.net/problem/2456 2456번: 나는 학급회장이다 첫째 줄에는 반의 학생들의 수 N (3 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 각 줄에는 각 학생이 제출한 회장후보 3명에 대한 선호 점수가 주어지는 데, 첫 번째 점수는 후보 1번에 대한 점수이고 두 www.acmicpc.net 브론즈 1 문제이다. 단순 하드코딩으로 이차원 배열에 3명의 후보별로 [총점, 3점, 2점] 리스트로 구성해 정렬하는 방식으로 풀다가 막혀서 구글링하다가 3점, 2점 점수 합 제곱을 해줘서(가중치 처리) 크기 비교를 하는 풀이법을 찾았다. (이런 아이디어 나도 내고 싶다..) 아이디어를 참고해 풀었다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.rea..
[BOJ] 4179. 불! (Python) / BFS www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 전형적인 최단거리 구하기 BFS 문제이다. 처음 아이디어는 사람이 먼저 4방향으로 뛰고, 불을 퍼트리고, 사람 이동, 불 이동 이런 식으로 번갈아 해줬는데 어디서 꼬였는지 자꾸 70%대에서 계속 틀렸다. 3번 넘게 계속 틀렸습니다가 떠서 질문검색을 통해 1. 불을 먼저 완전히 퍼트리고 이 정보를 보고 2. 사람이 격자 밖으로 나갈 수 있는지 여부를 확인함을 알았다. 불이 각 위치에 도달한 정보를 ..
[BOJ] 1915. 가장 큰 정사각형(Python) / DP 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 보자마자 바로 반복문으로 풀었는데, 어쩐지 쉽다 했더니 바로 시간초과; 아니나 다를까 Dynamic Programming 문제이다. 골드 5 문제이기도 하고. 요새 계속 기초 DP 문제를 풀고 있는데, 여전히 발상 자체가 어려운 것 같다. DP는 사실 코드는 짧은데, 이를 생각해내기가 참 어렵다ㅠㅠ 아직 DP초보라,, 더 노력하는 수밖에! 결국 다른 분 코드를 참고해서 풀었다. cagongman.tistory.com/18 [백준][Python] 1915 가장 큰 정사각형 - 풀이 공유 https://www.acmicpc.net..
[Programmers] 단어 변환(Python) / DFS 프로그래머스 고득점 KIT > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > Level 3 단어 변환 문제이다. programmers.co.kr/learn/courses/30/lessons/43163?language=python3 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr DFS를 먼저 떠올렸고, 계속 생각만 하다가 결국 코드로 구현하지 못하고 다른 사람의 코드를 참고했다. 참고 링크 : khann.tistory.com/79 프로그래머스 단어 변환..
[Programmers] 네트워크(Python) / DFS / BFS 프로그래머스 고득점 KIT > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > Level 3 네트워크 문제이다. programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 그래프 기본 문제로, BFS와 DFS 알고리즘으로 각각 코딩해보았다. 시간, 메모리는 비슷하게 나왔다. 다음은 BFS로 풀이한 파이썬 코드이다. from collections import deque def solution(n, computers):..
[Programmers] 타겟 넘버(Python) / DFS 프로그래머스 고득점 KIT > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > Level 2 타겟 넘버 문제이다. programmers.co.kr/learn/courses/30/lessons/43165?language=python3 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 발상으로는 매우 쉬운 수준의 문제인데, 함수 내 전역변수 사용법 때문에 생각보다 헤맸다. 늘 백준, SWEA 문제로만 연습하다보니 완전탐색할 때 전체 갯수, 최대 갯수..
[SWEA]1949. 등산로 조성(Python) / DFS SW Expert Academy에 있는 삼성 모의 SW 역량테스트 문제이다. swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 45분 정도 소요 본 문제는 이미 여러번 풀어봤기 때문에 문제도 보지 않고 바로 코드를 쳐 나갔다. 같은 문제를 풀 때마다 매번 아이디어가 조금씩 다르고 보다 효율적인 자료구조, 알고리즘을 쓰기 위해 노력하고 있다. 로직은 간단하다. 맵에서 가장 높은 위치를 만날 때 방문표시 하고, DFS를 사용해 함수 내에서 진입할 때마다 최대 길이를..

티스토리툴바