전체 글
0308_프로그래머스 : 다리를 지나는 트럭(deque, queue)
블로그 오랜만ㅎㅎ 3일만에 돌아왔다. 이번에 도전한 문제는 프로그래머스의 다리를 지나는 트럭이다. 이거 해결하는데 꼬박 하루는 걸린 거 같다. 이 문제는 큐로 풀어야 하기 때문에 리스트 형태에서 pop(0)을 사용하는 것은 비효율적이라는 말을 들었다. 그래서 덱 구조를 사용해보았는데, 테스트케이스 10개 중 1개가 자꾸 시간초과가 뜨는 거다...하하 결국 시영쌤의 도움을 받아 간신히 극복했다. 항상 감사합니다 쌤 그럼 우선 푼 코드 공유 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 from collections import deque def solution(bridge_length, weight, truck_weights): answer = ..
0305_SW 2819번 : 숫자 이어 붙이기
출처 : 소프트웨어 엑스퍼트 아카데미 2819번 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com #1차 시도 : DFS 재귀함수 이용해 델타 값으로 이동하며 7자리 수 만들기 - FOR문으로 2차원 배열의 모든 점을 시작점으로 재귀함수 시작하기 - 처음에는 배열 입력 받을 때 int값으로 받았지만, 7자리 수들을 결과 리스트 안에 하나씩 넣어주기 위해 나중에 ..
0304_백준 1260번 : DFS와 BFS (개념 알고 익숙해지기)
*출처 : 백준 1260번 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net # DFS와 BFS 코드 1차 풀이 : 다른 사람들의 풀이와 비교했을 때 시간이 더 오래 걸린다는 것을 파악. 시간 단축 필요. - 맨 처음 DFS를 풀었을 때는 노드와 엣지를 표현할 때 2차원 배열을 사용했는데, 이게 정답은 나왔는데 시간 초과가 떴던 ..
0303_SW 1861번 : 정사각형 방
이번 문제는 두 가지 방법으로 풀어보았다. # 1차 시도 : 델타로 이동하며 완전탐색하는 알고리즘 구현. 패스는 했지만, 시간이 오래 걸리는 것이 단점, 중간에 자꾸 실수했던 부분은 처음 시작한 위치를 start라는 변수에 저장하는 과정을 놓쳐서 출력 조건 중 '이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.' 조건을 충족하지 못했다. 추가적으로 아직까지 dfs 완전 탐색, 변수를 지정하고 활용하는 법이 서툴다고 느껴졌다. 앞으로 이 부분 더 추가로 문제 풀면서 보완해야겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 # 상하..
0303_프로그래머스 : 완주하지 못한 선수_해시
이 문제는 해시 개념을 이용한 문제이다. 나도 이 문제를 풀기 전까지 해시가 뭔지 몰랐다. 그러니 먼저 해시의 개념부터 알고 가자. #해시함수 (Hash Function) 해싱이라는 것이 해시테이블 이라는 구조를 이용해 데이터 검색을 빨리할 수 있게 하는 기법. 해시를 통해 데이터를 빠르게 삽입, 삭제하고 가져올 수 있는데 쉽게 말하면 key-value 쌍으로 존재하는 자료형 구조인 것이다. '딕셔너리'를 떠올리면 굉장히 쉽다. 참고로 파이썬에서는 딕셔너리 타입이 있기 때문에 따로 해시 함수를 구현할 필요가 없다. [참고 용어] 해시함수: Key에 대해 산술 연산을 이용해 데이터(Value) 위치를 찾을 수 있는 함수 해시 : 임의 값을 고정 길이로 변환하는 것 해시 테이블: 키 값의 연산에 의해 직접 ..
0302_백준 15656~15666번 : N과M문제 (재귀함수로 순열, 조합 구하기)part2
출처 : 백준 15656번 문제~ https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 어제에 이어 오늘 재귀함수로 구하는 순열, 조합 N과M 문제를 마무리 ..! 어제보다 난이도가 살짝 높았지만.. 주변 블로거님들 참고하며 극복ㅎㅎ 이전 문제들은 비슷한 맥락이지만, N과M 문제 9번부터 N개의 자연수 중 중복되는 숫자가 있어 이를 처리해줘야 하는 부분에서 조금 헤맸다. 해결방법은 overlap 이라는 새로운 변수를 만들어 만든 부분집합의..
0301_3월 첫 날/백준 15649 ~ 15655번 : N과M문제 (재귀함수로 순열, 조합 구하기)
# 출처 : 백준 N과M 문제 https://www.acmicpc.net/workbook/view/2052 문제집: N과 M (baekjoon) www.acmicpc.net 그 동안 순열과 조합을 itertools 외장 라이브러리를 사용하여 순열과 조합을 만들어 왔으나, 재귀함수를 이용해 풀어보는 연습이 꼭 필요하다는 피드백을 받아서 이를 연습하고자 백준 N과 M문제를 풀기 시작했다. 오늘은 6문제 정리하였고, 내일 6문제 추가로 풀 예정이다. 아직 함수를 쓰는 것도, 재귀 개념을 활용하는 것도 서툴지만 여러 차례 반복하여 문제를 풀다 보니 차츰 개념이 정리되는 느낌이다. [풀이 과정 정리] 중복 가능 : 순열 P 함수 중복 불가능 : 조합 C 함수 * 고려해야 할 요소 : 구한 수열들의 중복이 가능 유..
0227_ 오늘도 고생했다 .. SW 1258번 : 행렬찾기
오늘 문제 출처 : 삼성 소프트웨어 엑스퍼트 아카데미, 1258번 행렬찾기 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 여러번 시도했던 문제. bfs로도 풀 수 있다고 들었는데 나는 bfs, dfs 개념을 잘 모르고 아직 쓰는 것도 서툴다.. (이것도 또 공부해야 해) 이 문제 첨에 접근할 때 행렬 처음 위치에서 값이 있으면 열을 증가시키고 0을 만나면 행을 증가시키며 이동하고,, 결론은 처음 찍었던 좌표 위치와 마지막 이동한 좌표 위치..