문제

https://www.acmicpc.net/problem/1747

import sys, math
input=sys.stdin.readline

visited=[False,False]+ [True]*(1005000)
for i in range(2,int(math.sqrt(1005001))+1):
    if visited[i]==True:
        for j in range(2*i,1005001, i):
            visited[j]=False

def check(n):
    tmp=str(n)
    tmp1=tmp[::-1]
    if tmp==tmp1: return 1
    else: return 0

n=int(input())

for i in range(n,1005001):
    if check(i)==1 and visited[i]==True:
        print(i)
        break

에라토스테네스의 체와 문자열 일치를 섞은 문제이다. 다만 이문제에서 주의 해야할 점은 1 ≤ N ≤ 1,000,000이다.

문제 조건은 N보다 크거나 같고, 소수이면서 팰린드롬인 수를 찾는 것이기 때문에 에라토스테네스의 체를 구할때 1000000보다 큰 수까지 체크해 줘야한다.(1003001가 다음 소수이면서 팰린드롬인수)

문제

https://www.acmicpc.net/problem/1744

코드

import sys

n=int(input())
pos=[] # 양수를 저장할 리스트
neg=[] # 0과 음수를 저장할 리스트 (0을 음수취급)
total=0

for i in range(n):
    num=int(sys.stdin.readline())
    if num>1:
        pos.append(num)
    elif num==1: # 1은 양수와 음수모두 만나도 더하기만 진행
        total+=1
    else:
        neg.append(num)
        
pos.sort(reverse=True)
neg.sort()

if len(pos)%2==0:
    for i in range(0, len(pos), 2):
        total+=pos[i]*pos[i+1]
else:
    for i in range(0, len(pos)-1, 2):
        total+=pos[i]*pos[i+1]
    total+=pos[len(pos)-1]

if len(neg)%2==0:
    for i in range(0, len(neg), 2):
        total+=neg[i]*neg[i+1]
else:
    for i in range(0, len(neg)-1, 2):
        total+=neg[i]*neg[i+1]
    total+=neg[len(neg)-1]

print(total)

문제 해결

이 문제의 핵심은 양수와 양수가 아닌 수를 저장하는 리스트 두개를 만들어서 저장하는 것이다.

그리고 양수 중에서 1은 특수한 특징을 가지고 있고, 양수임에도 1은 곱셈을 해도 그 자체로 출력되므로 1은 양수를 만났을 때 더해야한다. 그리고 1과 음수가 접해있을때 곱셈을 해도 그 자체로 출력되므로 음수를 만났을 때도 더해야만 한다.이를 활용하여 주어진 조건대로 풀이를 하면 코드를 작성할 수 있다. 

문제

https://www.acmicpc.net/problem/1725

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

출력

코드

n = int(input())
result = 0
s = []
data = []

for i in range(n):
    data.append(int(input()))

#왼쪽부터 검사
for i in range(n):
    while s and data[s[-1]] > data[i]:
        height = data[s[-1]]
        s.pop()
        width = i
        #4 5 1 같은 경우 5 pop 후 4 -> 너비 2만들기 위해
        if s:
            width = (i - s[-1] - 1)
        result = max(result, width * height)
    s.append(i)

#스택에서 오른쪽 높이부터 검사
while s:
    height = data[s[-1]]
    s.pop()
    width = n
    if s:
        width = (n - s[-1] - 1)
    result = max(result, width * height)

print(result)

문제 해결

백준 블로그 에 해설이 상세하게 되어있다.

문제

https://www.acmicpc.net/problem/1707

코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def dfs(start,group):
    visited[start]=group
    for i in graph[start]:
        if visited[i]==0:
            if not dfs(i,-group):
                return False
        elif visited[i]==visited[start]:
            return False
    return True


K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V+1)] 
    visited = [0] * (V+1) 
    result = True 

    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    for i in range(1, V+1):
        if visited[i] == 0: # 방문하지 않은 정점이면 dfs 수행
            result= dfs(i,1) # 이분 그래프가 아니라면 탐색 중단
            if result == False:
                break
    print('YES' if result else 'NO')

from collections import deque
import sys
input = sys.stdin.readline

def bfs(start):
    queue = deque([start])
    visited[start] = 1 

    while queue:
        v = queue.popleft()
        for i in graph[v]: 
            if visited[i] == 0:
                queue.append(i)
                visited[i] = -visited[v]
            elif visited[i] == visited[v]: # 이미 방문한 정점이 같은 그룹이라면 False
                return False
    return True

K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V+1)] 
    visited = [0] * (V+1) 
    result = True 

    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    for i in range(1, V+1):
        if visited[i] == 0: # 방문하지 않은 정점이면 bfs 수행
            if not bfs(i): # 이분 그래프가 아니라면 탐색 중단
                result = False
                break
    print('YES' if result else 'NO')

문제 해결

주어진 이분그래프 문제를 BFS와 DFS방식으로 모두 풀어봤습니다.

추가적으로 이분그래프의 개념을 참고하면 좋을 것 같습니다.

• 이분 그래프(Bipartite Graph)란?

  

  • 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다.
• 탐색을 진행하며, 현재 노드와 이웃한 노드의 색을 확인하고, 동일한 색으로 칠해져있다면, 이분 그래프가 아닌 것으로 판단합니다.

문제

https://www.acmicpc.net/problem/1699

import sys
input=sys.stdin.readline

n=int(input())
dp=[i for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,i):
        if j*j>i:
            break
        if dp[i]>dp[i-j*j]+1:
            dp[i]=dp[i-j*j]+1

print(dp[n])

문제 해결

DP를 활용하여 풀이하는 문제였다.

dp[N] = min(dp[N], dp[N - 제곱수] + 1)

이를 이용해서 풀거나 주어진 조건을 일일히 계산하여 min함수를 사용하지 않고 주어진 코드처럼 풀이해도 된다.