개인사

리뷰오랜만의 파이썬 풀이였는데 C++을 주로 쓰다보니 이제 파이썬이 익숙치 않아 큰일이다.. 문제 풀이일반적인 다익스트라 풀이로 쭉 진행한다.인접리스트를 n + 1크기로 초기화 후 단방향으로 값을 받아준다.거리 리스트를 적당히 큰 값으로 설정하고 n + 1 크기로 초기화 해준다.경로를 나타낼 path 배열을 0 값으로 n + 1크기로 초기화 해준다.시작 위치의 거리를 0으로, 힙을 세팅해 주고 while문을 돌려준다.힙에서 pop한 현재 노드를 기준으로 인접리스트를 돌고 만약 현재 까지 구한 해당 노드까지의 거리보다 현재 거리가 더 작을경우 갱신해 준다.이때 path 배열의 다음 노드 인덱스에 현재 노드를 넣어준다. 이후 갱신한 거리와 다음 노드를 힙에 추가해준다.while 루프가 끝난 후 우선 목적지 ..

리뷰처음엔 파티 장소까지 갔던 인덱스를 구해 다시 돌아오면 되는 줄 알았지만 문제를 자세히 읽어보니 왕복 거리가 가장 큰 수를 출력해 내는 것이였다. 문제를 잘 읽자... 문제 풀이우선 모든 마을에서 x번 마을까지의 거리를 모두 구해준 뒤 거리 정보의 리스트를 리턴해준다. 난 go에 저장했다.이제 for문을 통해 x에서 모든 마을로 가는 경우의 수를 구해준 뒤 back이라는 리스트에 저장해준다.go와 back을 더한 값이 가장 높은 경우가 왕복거리가 제일 큰 학생의 거리가 된다. 참고 사항함수를 사용하지 않으면 코드가 너무 길어지기에 적절히 bool 인자를 섞어 함수로 구현하자dist를 INF로 초기화 해줄때 0번 인덱스는 0으로 바꿔줘야 max를 사용하기 편하다.go와 back을 비교하기 쉽게 back..

리뷰출력에서 예제 테스트용인 인덱스 5를 넣었다가 한번 틀려버렸다 ㅠ 문제 풀이n, m값을 받아주고 e는 빈 리스트를 n + 1개, dist는 INF 를 n + 1개로 초기화 해준다.m개 줄에 a, b, c를 받아주고 a번 노드에 거리 c와 도착지점 b를 리스트로 추가해 준다.start와 end가 될 도시의 정보를 받아와 주고 힙에 [0, start]를, start 도시의 거리를 0으로 초기화 해준다.while루프를 시작하여 현재 누적 거리보다 더 빠른 거리가 있을 경우 해당 도시까지의 거리를 최신화 해준다.while루프를 마친 후 end 도시까지의 거리를 dist[end]를 통해 출력해 준다. 참고 사항마지막줄에 시작 도시와 도착 도시의 정보가 있으니 꼭 참고하자  정답 코드import sysimpor..

리뷰다익스트라를 사용해 푸는 문제, 메모리 시간 살발하다 C++로도 풀어봐야되는데 엄두가 안나네.. 문제 풀이n, m, k, x값을 모두 받아온다.각노드의 간선을 나타낼 빈 리스트를 n + 1개로 초기화 해준다.각 노드까지의 거리를 나타낼 리스트를 INF값을 갖는 n + 1개로 초기화 해준다.m개의 간선 정보를 각 노드에 추가해 준다. 이때 거리는 1로 고정이므로 [1, 다음 노드]의 형식으로 추가해 줬다.힙에 시작 노드와 거리 0을 넣어주고 현재 노드에서 현재 노드까지의 거리는 0으로 설정해 준다.while루프를 돌며 각 간선까지의 거리 정보를 최신화 해주고 힙에 추가해주는 작업을 해준다.루프 종료 후 거리가 k인 도시가 있다면 모두 출력해 주고 없다면 -1을 출력해 준다. 참고 사항while루프 내에..

리뷰다익스트라를 활용한 문제 풀이 문제 풀이노드의 개수 n와 간선의 개수 m를 받아오고 시작점 k을 받아온다.각 노드의 간선 정보를 edge 리스트에 초기화 해준다. 인덱스 참조를 위해 n + 1 개의 빈 리스트를 2중 리스트로 생성각 노드까지의 거리를 나타낼 dist 리스트를 초기화 해준다. 마찬가지로 n + 1 개의 INF값으로 생성해 준다.m개의 간선 정보를 받아온다, 각 노드 시작점에 [거리, 노드] 형식의 리스트를 추가해 준다.시작점이 될 힙을 거리 0, 시작노드 k로 초기화 해주고, 시작 위치의 거리를 0으로 변경해 준다.힙이 존재할때 까지 while루프를 돌아 최소 힙을 pop해주고 현재 거리와 노드를 뽑아내 준다.만약 현재 거리가 dist에 저장된 현재 노드의 거리와 다를 경우 contin..

리뷰itertools 모듈을 처음으로 활용해본 문제 문제 풀이입력값을 리스트로 받아주고 permutations를 통해 해당 리스트에서 만들 수 있는 7개 길이의 모든 리스트를 생성해당 리스트를 for문으로 돌며 합계가 100인 경우 각 요소를 출력하고 break 처리한다. 참고 사항문제에 100이 되는 경우가 유일하게 주어지므로 break는 굳이 안해줘도 될듯  정답 코드from itertools import permutationslst = [int(input()) for _ in range(9)]results = permutations(lst, 7)for result in results: if sum(result) == 100: for i in result: pri..

리뷰BFS를 통한 풀이, 기존 숨바꼭질 보다 조건이 추가되었다, 순간 이동 시 소요되는 시간이 사라졌음 문제 풀이n, k값을 입력 받고 bfs의 인자로 n, k , 0을 보내준다.while루프를 돌기 전에 큐에 현재 위치와 시간 정보를 담아주고 100001 크기의 방문 배열을 false로 초기화 한다.현재 위치를 true로 설정하고 while루프를 시작한다.이동할 수 있는 위치는 총 세가지다 x - 1, x + 1, x * 2 이 중 순간이동을 하는 경우는 시간이 소요되지 않는다.시간을 소요하지 않는 순간이동을 가장 먼저 수행 후 조건에 맞다면 큐에 넣어준다.이후 뺄셈, 덧셈 순으로 조건이 맞을 경우 큐에 추가해 준다.bfs종료 후 리턴값을 출력하면 된다. 참고 사항덧셈과 곱셈을 할때 k와 뺄셈한 거리보..

리뷰딕셔너리와 에라토스테네스의 체로 풀이하였다. 문제 풀이a~Z범위의 알파벳을 키로 갖고 각 순서를 value로 갖는 딕셔너리를 초기화 해준다.문자열을 입력 받고 각 문자를 딕셔너리와 비교하여 value의 합을 구한다.점수가 나올 수 있는 최대값 보다 크게 배열을 1로 초기화 하고 소수의 경우 0으로 최신화 해준다.배열의 점수 인덱스가 1이라면 소수 0이라면 소수가 아님을 출력해 준다. 참고 사항없음  정답 코드dic = {}point = 1for i in range(97, 123): dic[chr(i)] = point point += 1for i in range(65, 91): dic[chr(i)] = point point += 1s = input()prime = 0for char..

리뷰모듈러 연산을 통한 재귀 풀이 문제 풀이모듈러 연산의 성질을 활용하여 재귀를 통해 값을 구하였다.초기 입력받은 a, b, c를 재귀를 사용할 함수에 보내준다.a가 밑, b가 지수이므로 b가 0이 될때까지 실행을 하고 b가 0일 경우 a^b는 1이므로 1을 리턴해 준다.b가 0보다 클 경우 b를 0으로 나눈 값을 재귀 시킨다, 이후 짝수일 때는 a^(b/2) * a^(b/2)를 c로 나눈 나머지 값을 half로 정의, 홀수일 때는 짝수에서 나온 값 half에 밑 a를 한번 더 곱해준 후 c로 나눈 나머지 값을 half로 정의한다.이후 half를 리턴해 주면 된다. 참고 사항모듈러 연산 정보덧셈: (a+b)%m=((a%m)+(b%m))%m곱셈: (a×b)%m=((a%m)×(b%m))%m거듭제곱: (a^b..

리뷰리스트, 튜플, 세트, BFS를 짬뽕하여 풀었다. 이게 최적화 코드인지는 잘 모르겠다.. 문제 풀이n, m값과 숫자 리스트를 입력 받고 정답을 저장할 빈 set를 초기화 해준다.BFS에 n과 m, 그리고 방문 처리와 임시 저장용 빈 리스트를 초기 기본값으로 세팅해준다.임시 리스트가 m의 길이와 같을 경우 해당 리스트를 튜플로 변환하여 set에 add를 해준다.i번째 인덱스에 첫 방문일 경우 방문 처리 및 리스트에 값을 저장해 주고 재귀를 호출해 준다.이후 for문을 돌기 전에 방문처리와 추가했던 값을 다시 빼준다.모든 작업이 완료된 경우 set를 리스트로 변환 후 오름차순으로 정렬해 준다.정답 리스트를 순회하며 값이 저장된 리스트를 언패킹하여 출력해 준다. 참고 사항set를 사용함으로서 자동으로 중복..