whatisworth 님의 블로그 whatisworth 님의 블로그

https://www.acmicpc.net/problem/2529일단 이 문제는 처음 보자마자 bruteforce 일것 같다라는 생각이 들었었다. 그런데 조금 더 생각해 보니 모두 다 탐색할 필요 없이 중간에 부등호에 맞지 않는 숫자배열이 나온다면 멈추는 알고리즘, 즉 백트래킹을 사용해야할 것 같다는 생각이 들었다..! 먼저 문자 부등호를 입력받아서 값을 비교하는 로직을 하나 짜고, 백트래킹 알고리즘을 활용하였다..!최댓값, 최솟값만 구하면 되기 때문에 부등호에 맞는 가장 처음과 가장 마지막 숫자 배열을 프린트 해주기 위하여 함수를 두개 짰다.주의할 점은, visited 와 global 변수 found를 max값 구하는 함수와 min값 구하는 함수에 각각 초깃값을 다르게 해주어야한다는 점이다. impor..

테스트 크기를 보고 딱 브루트포스알고리즘이겠다~ 해서 전부 다 탐색하는걸로 풀었는데 좀 오래걸렸다... 더 예쁘고 효율적인 풀이도 공부해야겠다 풀이 순서는 8*8 윈도우 모두 구하기 정답 체스판 2가지 구현해놓기 3중 for문으로 모든 윈도우에 대하여 정답과 다른 문자 카운트하기최솟값 구하기 인데, 조금 더 예쁜 풀이도 찾아보았다..내풀이 import sys read = sys.stdin.readline N, M = map(int,read().split())chess_map = []for _ in range(N):    chess_map.append(read().rstrip())windows = []for i in range(N-7):    window_xs = chess_map[i:i+8]    for..

https://www.acmicpc.net/problem/17144이문제,, 너무 어려웠다 ㅠㅠ 정말 거의 반나절 걸려서 간신히 풀었는데,, ㅠㅠ 자괴감이... 난 언제 이런 문제 술술 잘 풀려나,,, 여튼 나의 패착은 두 가지였다. 미세먼지 확산을 bfs로 해결하려고 했던 것간신히 정신줄 잡고 그냥 시뮬레이션으로 확산 돌렸는데 기존 graph값을 계속 변화시키는 방향으로 함수를 짜는 바람에 계속 답이 안나옴 공기청정기 방향 아이디어는 잘 잡았는데 테스트케이스 반복문으로 돌리는 과정에서 공기청정기 위치를 초기화 안해줘서... 느낀점은,, 진짜 시뮬레이션은 엄청엄청 꼼꼼해야하구나,,, ㅠㅠㅠ 후... 전체 코드는 다음과 같다.! 헷갈리는 부분은 주석을 달아두었다..import sys from collect..

https://www.acmicpc.net/problem/9012스택 문제 중에 가장 유명한 괄호 문제이다! 내 기억에는 프로그래머스에서도 비슷한 문제를 봤던 것 같다... 스택이란 자료구조는 LIFO 구조로, Last In First Out 구조이다. 파이썬에서는 리스트라고 보면된다. 만약에 코테에 스택 문제가 나온다? 하면 거의 무조건 append, pop만 쓰면 된다..! 다른 내장 함수 쓰는거는 거의 본적이 없다.여튼, 이 문제는 짝이 맞는지 확인해주는 빈 스택을 따로 정해주는 문제이다. 코테 식 문제풀이는 뭔가를 판단할 때 이런식으로 딕셔너리든, 리스트든 새로운 자료구조를 정의해서 판단용으로 사용하는 문제가 많은것 같다... 전체 코드는 다음과 같다. import sysdef is_vps(str..

https://www.acmicpc.net/problem/1913이 문제는 나선형으로 숫자를 배열하는 문제인데, 하우상좌로 이동하는것은 파악했는데 이동방식을 어떻게 조건문을 줘야할 지 몰라서 헤맸던 문제다.. ㅠㅠ 특히 계속 중앙인 1에서부터 시작하려고 했어서 막혔던 문제이다... ㅠㅠ 전체 코드는 다음과 같다. 이동시 조건은 그냥 범위를 벗어나지 않는지, 0이 아닌지만 주면 되는.. 싱거운 문제였다 ㅠㅠimport sys read = sys.stdin.readline N = int(read())M = int(read())arr = [[0 for _ in range(N)] for _ in range(N)]# 하우상좌dx = [1,0,-1,0]dy = [0,1,0,-1]dir = 0num = N ** 2x..

https://www.acmicpc.net/problem/16236이 문제는 기본 BFS에 여러가지 조건이 붙은 문제여서 구현하기가 좀 까다로웠다.문제의 특징을 몇가지 말해보자면, 아기상어의 위치를 구하고 그 자리를 0으로 초기화 해주기 아기상어의 이동(BFS)와 물고기를 먹으면서 크기를 성장하는 로직을 따로 작성해주기 BFS에서 먹은 물고기의 위치, 거리를 리스트로 저장해서 정렬하기 가 있다. 특히 세번째의 경우 굉장히 중요한 포인트인데, 나는 처음에 BFS로 이동하면 자동으로 제일 위에 있는 물고기, 제일 왼쪽에 있는 물고기부터 먹을줄 알았다. "거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다."이 부분을 어떻게 구현하느냐를 생..

https://www.acmicpc.net/problem/2573이 문제는 그래프 탐색 문제로, 문제에서 설명하는대로 착실하게 구현만 하면 되는?(그게 어렵지만,,)문제라고 할 수 있다. 빙산이 분리가 되는지 탐색하는 것은 bfs를 통해 구현하였고, 1년 후 빙산의 상태는 이중 for문으로 구현하였다. 중요한 점은 방문 그래프가 반복문을 실행할 때마다 초기화 되어야 한다는 것이다. import sys from collections import dequeread = sys.stdin.readline N, M = map(int, read().split())graph = []for _ in range(N):    graph.append(list(map(int, read().split())))# 상하좌우 dx ..

https://www.acmicpc.net/problem/14891빡구현으로 유명한 삼성 기출문제이다. 꼼꼼하지 못한 나는 언제 이런 문제를 빠르게 풀 수 있을까,, 한숨이 나왔지만 어쨌든 정진하기로...ㅠㅜㅠ이 문제의 특징은 톱니바퀴의 회전을 양옆으로 전파 시켜야 한다는 것이다. 나는 처음에 각 톱니바퀴의 순서에 따라 회전하는 방향을 모두 지정하려고 했었는데, 굳이 그럴 필요가 없었다. import sys read = sys.stdin.readline cogwheel_state = []for _ in range(4):    cogwheel_state.append(list(map(int,read().rstrip())))K = int(input())turns = []for _ in range(K):    ..