개발조아

문제 링크 : https://www.acmicpc.net/problem/22860 22860번: 폴더 정리 (small) main 폴더 하위에는 FolderA 폴더 하위에 있는 File1, File2, FolderB 폴더 하위에 있는 File1, File3이 있다. 파일의 종류는 File1, File2, File3 총 3가지이고, 파일의 총 개수는 File1, File2, File1, File3 총 4개이다. mai www.acmicpc.net 그냥 트리 구조 만들어서 했다. 노드는 이름, 종류, 파일 리스트, 폴더 리스트 4가지로 구성했다. 그리고 folders라는 딕셔너리에 입력으로 주어지는 폴더 정보의 상위 폴더 노드를 저장했다. main FolderA 1 FolderA File1 0 위의 두개 입..

문제 링크 : https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 평범한 BFS 문제이다. N이 최대 1000이므로 그래프 좌표를 인접 리스트로 하자. from sys import stdin from collections import deque input = stdin.readline s,e = map(int, input().split()) n,m = map(int, input().split()) adj..

문제 링크 : https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 역이랑 하이퍼튜브를 어떻게 표현할까를 고민했던 문제이다. 나는 각 역에 연결된 하이퍼튜브의 번호 배열, 각 하이퍼튜브가 연결한 역의 번호 두가지를 사용했으며 각각은 인접리스트로 했다. 입력 순서대로 하이퍼 튜브에 0번부터 번호를 매겨서 저장했다. 설명하면 아래와 같다. 하이퍼 튜브가 1 2 3 1 4 5 라고 들어 왔다고 해보자. 각 역에 연결된 하이퍼튜브..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 구현문제이다. 문자열 처리만 잘 해준다면 크게 어렵지 않다. 악보나 기억한 멜로디를 전처리를 해주어야한다. C,C# 이처럼 #이 붙은 문자열을 처리해줘야한다. 왜냐면 기억한 멜로디가 CC 이고 악보가 CC#이라면 판별하기 까다롭기 때문에 다 다른 문자로 바꿔주자. 나는 그냥 모든 음 다른 문자열로 매칭시켜줬다. 주의할 점은 문제에 사용..

문제 링크 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net BFS로 풀었다. 처음에는 숫자는 최대 값이 1백만이고 k는 10이어서 1백만x11개의 배열을 만들어서 BFS로 풀이 했다. 큐에 쌓이는 것과 2천만크기의 배열때문에 메모리 초과가 난 것 같다. 그래서 방문 체크를 set을 사용했다. 대충 횟수 따져보자 입력이 123456이 들어오면 경우의 수는 6! 이므로 충분히 작다. 따라서 set으로 방문체크해도 충분히 통과할 수 있을 것 이다. 입력 숫자부터 각 숫자를 바꿔가면서 BFS를 진행하자. 방문 체크는 ..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 구현, 시뮬레이션 문제이다. 각 칸에 명령에 따라 진행방향을 정하고 다음 칸으로 이동한다. 이때 이동하다가 처음 시작점, 시작방향이 똑같은 점으로 오면 한 사이클이 생성된 것이다. 이때 사이클의 길이를 구하는 문제이다. 나는 각 점에서 나가는 방향을 기준으로 사이클을 판별했다. 만약 같은 칸에 다른 방향으로 빛이 나아가..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 정확도는 범위가 적기 때문에 어렵지 않게 통과할 수 있다. 그냥 리스트로 insert, del만 해줘도 쉽게 통과할 수 있다. 하지만 효율성의 경우 시간초과가 많이 날 것이다. 나도 복구하는 것 때문에 시간초과가 계속 났다. 중간중간 insert과 delete가 많이 일어나기 때문에 연결리스트로 구..

문제 링크 : https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 처음에 문제 조건을 잘못이해해서 틀렸었다. 나는 a-b, b-c라면 a-c도 친구라고 이해하고 풀었더니 63%였나 그쯤에서 틀렸다고 나왔다. 그래서 예제를 찾아보고 돌려보니 a-b, b-c라면 a-c라는 관계도 있어야한다. 즉 모든 친구가 서로서로 모두 친구사이어야한다. 건너서 친구면 친구가 아닌 것이다. 우선 나는 BFS로 풀었다. 사용하는 자료구조는 우선순위큐와 인접행렬, 인접리스트를..