2580\. 스도쿠스도쿠를 입력받을 때 blank도 같이 입력 받는다. back tracking 할때 blank list에서 하나씩 뽑아서 하도록 한다. \- blank list를 따로 안하고, row와 col을 돌아가는 방식으로 했더니 꼬임back tracking
9576\. 책 나눠주기처음에는 Backtracking 으로 풀어보려고 했다.넣을수 있는 최소 번호부터, 넣을수 있는 최대 번호까지 다 넣어보기 + 안넣는 경우 너무 많은 경우의 수가 발생해서 recursion error 발생 두번째 방식은 abs 즉 min book
링크텍스트조합을 물어보는 문제여서 combination 씀itertool을 안쓸 경우 combination 구현 필요
2250\. 트리의 높이와 너비 예시에는 root node가 1번부터 시작하고 맨 위에 존재하지만, 문제 case에는 root node부터 시작하지 않을 수도, node의 순서대로 들어오지 않을 수 있다. level을 2\*\*level - 1 방식으로 해보려고 했는데
2206\. 벽 부수고 이동하기 기초적인 그래프 탐색처럼 상하좌우 이동을 넣고, break_checker가 0이면 1인경우에도 이동할수 있도록 처음에 구현 bfs로 구현하고 visited가 단일일 경우에 해결 못하는 case 발생0000011110000000111100
11497\. 통나무 건너뛰기주어진 숫자 리스트를 우선 정렬한다. 정렬한 순서대로 번갈아가면서 결과리스트의 앞과 뒤에 하나씩 넣는다. 결과 리스트의 인접값중 최대값이 결과가 된다.
11055\. 가장 큰 증가 부분 수열본인보다 작은 값들을 찾아 가면서 tmp에 더해서 저장한다. 다 찾아보면서 가장 큰 값을 now에 저장한다. 최종적으로 now의 maximum 값을 저장한다. 1001개의 배열을 미리 생성 arr의 index는 num_list의 값
1103\. 게임기존의 그래프 문제와 다르게, visited와 cycle 두개의 확인 지표가 필요하다. 처음에는 기존의 maze 문제처럼 BFS로 풀려고했다. 왔던 타일을 다시 오는 경우가 발생할 수 있기 때문에 BFS로 풀 수 없다는 것을 알게되었다. DFS로 변경했
1700\. 멀티탭 스케쥴링 추가할 전자제품이 이미 멀티탭에 꽂혀 있으면 continue안 꽂혀 있지만 멀티탭이 남으면 멀티탭에 추가해주고 패스안 꽂혀 있고 남은 멀티탭도 없으면 앞으로 더 꽂아줘야할 전자 제품 리스트를 확인 더 꽂아줘야할 전자 제품 리스트에서 지금 멀
b1080. 행렬처음에는 matrix1 i:i+3 != matrix2i:i+3 이 다를 경우 바꿔주도록 했다. 000111 000000000111 000000000111 000000두개의 매트릭스 결과값은 1이어야 하나 이상하게 바꿔주는 것을 확인두번째는 각각의
13460\. 구슬 탈출2첫번째 시도 다음번 레드 구슬이 갈곳이 '.'이면 이동하도록함레드의 이동이 끝나고 블루가 이동하도록 함 블루가 이동하다가 구멍을 만나면 종료하도록 함 레드의 다음번 가야할곳이 ' - 레드의 다음번 가야할곳이 'O'이면 red의 현재위치를
2810\. 컵홀더규칙을 발견하다보니 전체 사람수에서 copule의 개수 -2 //2 만큼 빼주면 된다는 것을 확인couple_count 가 0 일 경우 copule의 개수 -2 //2를 하면 -1이 되므로 커플석이 없을때는 그냥 사람수만큼 출력
2239\. 스도쿠스도쿠를 입력하면서 blank들을 찾아서 list에 보관 backtracking은 blank_list 순서대로 promising 한 값들을 넣어가면서 sudoku를 채움 숫자가 작은 순서대로 넣기때문에, 첫번째 나오는 스도쿠가 반드시 가장 작은 스도쿠
12852\. 1로 만들기2ai = max(ai-1+1 , ai//2+1 , ai//3+1) 이라는 간단한 점화식으로 풀수 있는 문제 숫자가 지나간 루트를 기록할 필요가 있으므로 before list를 만들어서 가장 min일때의 바로 앞 경로를 저장하도록 함
2178\. 미로 탐색기본적인 BFS 문제 4방향으로 가고 visited 0, maze 1이면 방문하도록
1976\. 여행 가자 해당 문제에서는 가고자하는 노드가 연결만 되어 있으면 ok따라서 가고자하는 노드 하나를 우선 등록하고, 해당 노드에 연결되있는 모든 노드를 can_go_list에 추가한다. tmp_list를 만들어서 연결돼있는 모든 노드를 찾도록 한다. can_
2212\. 센서 처음에는 정수마다 sensor까지의 값의 합을 구하려고 했다. 같은 방향일 경우 더 큰 길이가 작은 길이를 무시하는것을 확인했다. 두번째에는 max와 min을 구해서 중간 값으로 자르려고했다.예제는 맞지만 931 2 4 5 6 7 8 9 10해당 예제
불!불을 먼저 퍼트려서 불이 지나가는 위치의 시간대를 먼저 기록해 두었다. 지훈이가 움직일때는 불이 지나간 시간대보다 먼저 지나가야 한다. 처음에는 fire를 0으로 두고 했는데, 불이 아예 막히는 경우의 수도 고려해야한다. 따라서 inf로 초기값을 설정 4 4 JF
15664\. N과 M(10)숫자를 받아와서 combination 수행순서대로 보여주기 위해서 result 정렬num_list도 정렬해야 combination이 순서대로 생성됨
11725\. 트리의 부모 찾기 처음에는 그래프 n\*n 을 만들어서 BFS 방식으로 풀려고했다. 이 방식은 메모리를 너무 많이 잡아 먹음 두번째로는 엣지를 넣으면서 1인게 있으면 parent를 1로 설정해주고 아닌거를 que에 넣도록 했다. 시간이 너무 많이 걸리는
1260\. DFS와 BFSDFS와 BFS를 구현해서 푸는 간단한 문제DFS를 큐를 이용해 보려했으나 꼬임DFS는 백트래킹으로 하자
13305\. 주유소현재까지 가장 가격이 저렴한 기름값으로 계속 간다. 새로운 노드에 갈때마다 가격 비교해서 업데이트
문제 링크 17163. 색종이 붙이기 문제 풀이 처음 시도 5*5짜리 종이를 붙이고 붙인 부분을 0으로 만들어서 몇개 붙이는지 확인해봄 5개가 넘는 종이를 붙이면 -1 출력 시도 2 예시 1번을 넣었을때 답이 4가 나와야 하나, 5*5부터 붙이므로 -1을
1449\. 수리공 항승 어차피 모든 구멍은 막아야한다. 가장 작은 구멍에서 부터 시작해서 -0.5인 위치에 테이프를 붙인다.다음 구멍+0.5의 위치보다 테이프의 길이가 더 길면, 해당 구멍은 막힌거라고 생각할 수 있다. 다음 구멍이 안막히면 그 구멍의 -0.5의 위치
1525\. 퍼즐처음에는 3\*3 이차원배열로 풀려고 했다. visited 비교하는데에 너무나 많은 시간이 걸림문자열로 바꿔서 수행하고, 3 <->4 , 6<->7 swap 안하도록 조건 걸어줌 que에 리스트 형태로 넣는것보다 set으로 넣는게 훨씬 시간
2751\. 수 정렬하기2단순히 int(input()), print() 로 하니 시간 초과할께 많을땐 sys를 쓰자
순열을 물어보는 문제
현재값보다 낮은 값이 많은 것들을 찾아나가는 간단한 문제
R,G,B 3개의 값 순서대로 가장 처음 나오는 곳을 찾는다. 가장 처음 나온곳을 기준으로 4방향 이동하며 같은 값을 찾는다. visited를 갱신하면서 가다가, 더이상 que가 없으면 count를 하나 증가시키고 다시 처음부터 그래프를 찾아서 다음 R,G,B 값을 찾
주어진 도시의 개수가 충분히 적어 브루트포스가 가능할것으로 판단도시의 순열을 구해서 길이값을 더하고 가장 길이가 작은것을 넣도록 함 처음 제출시 시간초과 문제 발생 -> Count를 계산할때 이미 max보다 큰경우는 프루닝 하도록함 예시에서는 도시간 거리가 없는것이 0
마을에서 내릴 박스의 양을 들고다니는 배열 선언 다음 마을에 갔을때 내릴께 있으면 내리고 count 증가더 실을께 있는데 size를 넘으면 마을이 가까운 것부터 실음이미 size를 초과했는데 마을이 더 가까운게 있으면 버리고 가까운거 실음
1931\. 회의실 배정첫번째 시도끝나는 시간을 기준으로 정렬하고 전체 회의 리스트를 순회전타임 끝나는 시간 뒤에 시작하는 회의부터 다시 시작하도록 함 반례 1번을 풀지 못하는 경우 발생 두번째 시도끝나는 시간으로 정렬하고, 시작하는 시간으로 한번더 정렬두가지 조건으로
9205\. 맥주 마시면서 걸어가기처음 위치를 큐에 넣음end 위치도 conv_list에 같이 넣음현재 위치에서 아직 방문하지 않았거나, 거리가 1000이하인 편의점들을 큐에 넣음end위치에 도착하면 break하고 출력
11053\. 가장 긴 증가하는 부분 수열num_list의 새로운 값은 기존 arr의 값중에서 가장 큰 값보다 +1만큼 length 증가 max(arr)의 값이 가장 긴 증가 부분 수열
17135\. 캐슬 디펜스첫번째 시도예제는 다 맞았으나 제출하자마자 틀림반례 1번에서 답이 6이 나옴Kill list를 초기화하지않아서 발생하는 문제임을 파악해당 부분 해결하니 합격2 4 21 1 1 10 1 1 0answer :5
3184\. 양영역을 나누면 되는 문제영역을 먼저 나누고, 해당 영역의 wolf와 lamb 숫자를 센다.lamb가 많으면 wolf가 죽고 , 반대면 lamb가 죽음죽은만큼 처음 센 갯수에서 빼준다.