1069 집으로

2차원 그래프에서 0,0으로 다음의 두 조건을 통해 가려 할때의 최솟값을 찾는 문제이다.
1. 1초에 1의 속도로 걷는다.
2. t초에 d 만큼 점프한다. (직선으로만 도중에 멈추기 안됨)

이 문제는 두 점을 잇는 직선으로만 생각하면 안된다. 왜냐하면 각도를 조금 틀어서 한 번 더 점프하는것이 이득인 경우가 있기 때문이다.
내가 본 가장 효과적인 방법은
점프 가능한 거리만큼은 점프를 하고 나머지 1번을 여러 케이스로 나눠서 최솟값을 찾는것이다. 보면 구현은 쉽지만 각 케이스가 실제 그런지에 대한 고민이 필요하다.

나는 결국 생각하지 못하고 다른 사람이 올린 소스를 중심으로 풀었다.
반성이 필요한 순간이다..

소스

2417 정수 제곱근

정수의 제곱근을 찾아 올림하는 문제이다.

간단하게 sqrt 함수와 ceil 함수를 이용했다. 이렇게 하지 않고 반복문을 통해 하는 방법도 가능하다.

소스

Pollard's Rho

어떤 수의 인수(factor)를 찾아내는 알고리즘이다.
특히 큰 수의 인수를 찾을 때 유용하고, 메모리를 거의 차지하지 않으며 O(n^(1/4))의 시간복잡도를 보인다고 한다.

gcd 와 x^2+-a (1,-1) 을 이용하는데, 정확한 수학적 원리는 모르겠다.
실제 테스트를 해봤는데, 약수를 전부 찾아내는건 아니지만 큰 수인데 인수가 2~3개 밖에 안되는 경우도 빠르게 찾아냈다.

참고

소스

modular exponentiation

a^b mod c 를 구하는 알고리즘이다.
단순하게 a^b를 하고 c로 나머지를 하면 프로그래밍에서 오버플로우가 발생하기 때문에,
중간과정에 modular 연산을 해줌으로써 오버플로우를 방지한다.
물론 이렇게 해도 결과가 달라지는 일은 없다고 한다.

b승을 단순히 a를 b번 곱하는 식으로 하게 되면 O(b)의 시간복잡도가 생기는데,
이것은 빠른 방법이 아니다.
이에 관련된 알고리즘엔 여러가지가 있는데,
이 중 하나의 방법으로 2씩 나눠가는 방법이 있다.
a^b = (a^2)^(b/2) 라는것을 이용하여 O(log2(b)) 의 시간복잡도 안에 해결 가능하다.

소스

2986 파스칼

파스칼 코드로 되어있는 프로그램의 결과를 출력하는 문제이다.
파스칼 코드의 의미는 N-1부터 1까지 반복하면서, N과 나누어떨어지는 수가 발견되면 그 숫자가 나올때까지의 반복횟수를 출력하는것이다.

사실 이 소스를 그대로 C로 구현해도 정답이 맞아야 하지만, 얄밉게도 TLE가 발생하는 구조로 되어있다.

따라서 이 문제는 N보다 작으면서 N과 나누어떨어지는 수의 최댓값을 찾아야 하는데,
이는 N을 N의 가장 작은 약수로 나눈값과 같다.

따라서 N의 가장 작은 약수를 찾으면 되는데, 이것은 O(root(N))의 시간복잡도를 가지게 찾을 수 있다.

소스

5054 주차의 신

가게가 일렬로 되어 있을 때, 모든 가게를 들른다고 가정하면 차까지 돌아오는 거리가 가장 짧은 경우를 출력하는 문제이다.

얼핏보면 주차의 위치를 선정해야하는 것처럼 보인다. 하지만 사실은 어느곳에 주차를 하던 상관이 없다. 왜냐하면 차까지 돌아오는 거리가 가장 짧으려면, 주차된 위치에서 오른쪽 끝 가게 까지 일직선으로 들렀다가 돌아오고, 다시 왼쪽 끝 가게 까지 일직선으로 들렀다가 돌아와야 하는데, 그 거리는 왼쪽 끝에서 오른쪽 끝까지의 거리의 2배가 되기 때문이다. 따라서 어디다 주차를 하던, 왼쪽 끝과 오른쪽 끝 사이의 거리는 일정하기 때문에, 답은 이 값의 2배를 한 것이다.

소스

2607 비슷한 단어

첫번째 단어와 비슷한 단어의 갯수를 구하는 문제이다.
비슷한 단어란, 처음단어와 주어진 단어가 사용된 문자, 문자의 갯수가 같거나, 문자를 하나 더하거나 빼주거나 한 문자를 다른 문자로 바꿔 주는 작업을 통해 앞의 조건을 만족한다면 비슷한 단어라고 한다.

이 문제를 푸는 방법은, 처음 단어의 사용된 문자와 횟수를 담는 배열을 만들어 주고, 주어지는 단어의 배열도 만들어 준 다음, 둘을 서로 비교하여 횟수가 다른것을 찾아야 한다. 횟수가 다른것에 여러 패턴이 있는데, 그것들을 이용해서 둘이 같은단어인지, 한번의 작업을 통해야 하는지, 둘이 다른단어 인지를 밝혀내면 된다.

소스

2563 색종이

도화지에 색종이를 겹쳐 쌓았을 때, 색종이가 이루고있는 면적을 구하는 문제이다.

간단하게 좌표마다 색종이가 쌓였다는 표시를 해주면서 덧붙여주고, 마지막에 한번 싹 훑으면서 쌓아가면 답이 나온다.

소스

9081 단어 맞추기

주어지는 단어에서, 단어안의 알파벳으로만 이루어진 단어를 사전순으로 나타낸다고 할 때, 주어진 단어의 다음번에 나오는 단어를 출력하는 문제이다.

이 문제를 풀기 위해선 단어를 정렬하는 과정이 필요한데, 문제는 어떤단어를 얼마나 정렬하는가 이다. 내가 푼 방법은 단어의 끝부터 시작하여 알파벳을 고르고, 그 알파벳을 앞의 알파벳과 비교하면서 위치를 바꿨을 때 사전순으로 뒷서는지를 검사한다. 그런 알파벳이 여러개 존재할 때는, 바꾸는 위치가 가장 뒤로가 있는것(변화가 가장 작은것)을 택한다.

만약 그런 알파벳이 존재하지 않으면 그대로 뿌리면 되고, 존재해서 찾았다면 고른 알파벳을 찾아낸 위치에 끼워 넣는다. 그리고 그 뒤의 문자열을 오름차순으로 정렬해주면 된다.

소스

4773 로마 숫자 계산기

로마 숫자로 사칙연산을 수행하는 프로그램을 만드는 문제이다.
단, 숫자를 스택구조로 저장하여, 한번에 여러 숫자를 저장할 수도 있고, 연산한 결과를 계속 이어갈 수도 있다.

이 문제를 풀기위해선 우선 스택구조를 만들어야 한다. 나의 경우는 data_structure 태그에 있는 소스를 이용했다. 스택을 구성했으면 입력을 받아온 것이 로마숫자일 경우, 10진법으로 바꿔서(rome2dim) 스택에 push 하고, 연산자일 경우 연산을 해준다.
연산을 해줄땐 단순히 10진법으로 계산을 하고 출력할때만 다시 로마숫자로 바꿔주면 된다.(dim2rome)
여기서 연산은, 두 숫자를 pop 하고, 연산한 하나의 값을 다시 push 해주는것을 말한다.
단, = 연산자는 pop하지않고 뿌려주기만 한다.

여기서 주의해야 할 것은 예외인데, 그 상황은 아래와 같다.
1. = 연산자가 들어왔을때, 스택에 아무것도 없으면 stack underflow
2. = 연산자인데 가장 첫값이 1보다 작거나 4999보다 크면 out of range exception
3. 연산자인데 = 가 아닐때, 스택에 데이터가 두개보다 적으면 stack underflow
4. / 연산자일 때 나누어 주는수가 0이면 division by zero exception

1,2,3번 상황이 발생하면 오류메세지만 뿌려주고 연산을 수행하지 않고, pop도 하지 않는다.
4번 상황이 발생하면 0이 아닌 다른값만 push 해준다.

p.s. 나누기 연산은 int형의 나눗셈만 하면 된다. (소숫점이면 맨붕..)

소스

2608 로마 숫자

두 로마숫자의 합을 물어보는 문제이다. 로마숫자는 아래와 같다.

합을 구하기 위해서 로마숫자를 10진법으로 바꾸고, 10진법을 로마숫자로 바꾸는 방법을 이용했다.

로마숫자를 10진법으로 바꾸는 방법은, 앞자리 부터 시작해서 기호에 맞는 문자를 찾아 그 숫자를 더해주면 된다. 이 때 CM(900) 과 같은 경우만 고려해주면 된다.

10진법을 로마숫자로 바꾸는 방법은 1000부터 시작하여 10씩 나눠가면서 비교한다. 이 값일 m이라고 할 때, 해당 숫자가 m 이상이면  각 숫자에 맞는 문자를 추가해준다.
이 땐 900, 500, 400의 경우까지 합쳐 총 4번을 검사해주면 된다.

소스

1914 하노이 탑

하노이 탑에 원판이 n개 쌓여있을때, 옮기는데 드는 총 횟수와 옮기는 과정을 출력하는 문제이다.

하노이 탑이란
3개의 기둥이 있고, 처음 기둥에 n개의 원판이 크기가 큰 순서대로 쌓여있다.
이 원판들을 3번째 원판에 모두 옮겨야 하는데,
한번에 1개의 원판만 옮길 수 있고, 작은 원판위에 큰 원판을 올릴 수 없다는것이 규칙이다.

스페셜 저지 문제가 아니기 때문에 항상 최적의 경우를 구해야만 하는데,
최적의 해의 횟수는 2^n - 1 번이다.
머리를 짜보았지만 도저히 알고리즘이 떠오르질 않아서 검색을 했는데,
재귀를 이용해서 문제를 푸는 것이었다.

답은 맞았지만 알고리즘을 봐도 원리가 정확히 이해가 되지 않아서 푼거같지가 않다..

소스

1065 한수

1부터 N까지 각자리의 수가 등차수열인 숫자의 갯수를 구하는 문제이다.
무언가 공식이 있을법 하지만 범위도 적기때문에
직접 구해주었다.
1의자리와 10의자리의 공차를 구한 다음, 각자리마다 전부 같은가 비교해주면 된다.

소스

2072 오목

두 플레이어가 오목게임을 한다고 했을때, 몇수에서 승부가 나는가를 판단하는 문제이다.

오목에서 승부가 난다는것은 한쪽이 연속으로 5개의 돌을 놨다는 말이다.
따라서 돌을 놓을때마다 가로,세로 , 두 대각선을 중심으로 돌이 5개 놓여져있는가를 판단해주면 된다. 이때, 돌이 5개 이상일 경우에는 승리가 아니므로 주의해야 한다.
3,3같은 금지룰이 없어서 다행이다.

소스

4880 다음수

세 수가 등비수열인지, 등차수열인지를 판단하는 문제이다.

세 수를 a,b,c라고 하면, b-a와 c-b가 같으면 등차, b/a와 c/b가 같으면 등비이다.
이를 이용해서 답을 출력하면 된다.

소스

1252 이진수 덧셈

두 이진수를 덧셈하는 문제다.
파이썬같은 언어로는 바로 덧샘해주면 그만이지만, C에서는 생각보다 쉽지 않다.

우선 길이가 80이기때문에 문자열로 받아주어야 한다.
그리고 두 이진수를 첫자리부터 계산해주기 위해 reverse를 한다.
첫자리부터 계산을 하는데, 범위는 가장 큰 문자열로 한다.
각 자리의 숫자는 '1'과 '0'의 문자로 되어있기 때문에, 그 자리의 문자가 '1'이면 1, 아니면 0으로 바꾸어주고, 덧셈을 한다.
덧셈을 할때 해당자리는 2로 나눈 나머지 값을 놓으면되고, 만약 각 자리가 1,1이라 자리올림이 생기면 처리해주는 변수를 따로 둔다.
이때 바로 출력하지말고 출력할 버퍼에 하나씩 쌓는다.
반복이 끝나면 맨마지막 자리에 올림이 발생했는가를 판단해서 추가해주고,
출력버퍼를 reverse 해준다.
그 후 시작부터 끝까지 보면서 0으로 시작하는 경우엔 잘라내준다.

첨엔 간단해 보였으나 생각보다 어려운 문제였다.

소스

1922 네트워크 연결

N개의 컴퓨터를 전부 하나의 네트워크로 묶으려고 할 때,
가장 작은 비용이 드는 경우를 고르는 문제이다.

딱봐도 간선문제인것이 그래프 문제라는 생각이 들었고,
그래프 알고리즘 중에서 프림알고리즘이 이 문제와 알맞는 알고리즘이라고 생각했다.
프림알고리즘은 자신의 영역과 이어진 간선중에서 가장 최소가 되는 간선을 골라서 자신의 영역을 늘려가는 방식이다. greedy 알고리즘의 일종인데, 보통 greedy 알고리즘은 최적의 결과를 낳지는 않는것으로 알려져 있으나, 이 알고리즘은 특이하게도 greedy 알고리즘이면서 최적의 결과를 낳는 알고리즘이다.

그래서 prim알고리즘을 적용하여 정답을 맞았으나..
TLE에 아주 아슬아슬하게 걸쳐있었다. 다른 사람의 소스는 매우 짧은 시간이 소요된것에 비해 내 방법은 매우 느린 결과를 보였다.
그래서 다른 사람의 소스를 살펴보니, 간선정보들을 오름차순으로 정렬하고 거기서부터 하나씩 뽑아서 연결하는 방법이었다.

그래프 알고리즘에 정렬을 사용한다는 생각은 못하고 있엇는데 역시 실력차이인것 같다.

소스

Queue

Queue 구조는 Stack 구조와 같은 연결리스트(Linked List) 방식이다. 다만, pop하는 과정에서 Stack 처럼 LIFO 가 아닌 FIFO(First In First Out) 방식을 사용한다.
다른 설명은 Stack과 같으니 생략한다.

소스

Stack

Stack 구조는 연결리스트(linked list)의 한 갈래이다. 연결리스트는 자신이 자신의 다음 위치(pointer)를 담고있는 자료구조이다.

연결리스트 함수의 구성은 push와 pop 으로 되어있다. push 는 새로운 데이터를 연결리스트를 이용해 추가하는 함수이다. 배열의 다음 index에 값을 넣는과정과 비슷하다. 단, 여기선 동적 할당을 이용하여 새로운 데이터를 넣는다.
pop 은 넣은 데이터를 빼내는 함수이다. pop 함수의 데이터를 빼내는방법은 여러가지가 있다.

Stack 구조의 특성은, 가장 나중에 넣은 데이터가 가장 먼저 나온다는 점이다. (LIFO -> Last In First Out) 즉, pop 함수는 새로 넣은 값을 뽑아 내도록 해야 한다.

소스에는 이 두 함수 외에도 init, destroy 등등 여러 함수가 들어있고, 점차 추가시킬 계획이다.

소스

1592 영식이와 친구들

원형 큐에서의 왼쪽,오른쪽 이동을 물어보는 문제이다.
일반 배열로도 문제를 해결할 수 있는데,
왼쪽으로 갈 때는, 현재위치에서 왼쪽으로 가는만큼을 뺀다.
만약 그 수가 음수가 되면, 거기에서 큐의 크기만큼을 더해준다.
오른쪽으로 갈 때는 현재위치에서 오른쪽으로 가는만큼을 더한다.
만약 그 수가 큐의 크기를 벗어나면, 큐의 크기만큼을 빼준다.

소스

9084 동전

2293 동전 1 의 문제와 똑같은데, 테스트 케이스가 추가된 문제이다.
별 어려울것 없이 2293의 소스에 입력을 맞춰주면 된다.

소스

2684 동전 게임

동전의 앞뒷면의 결과를 가지고 연속된 3개의 결과를 나타내는 문제이다.
처음부터 마지막결과-2 까지 슬라이딩 하면서
알맞은 수열의 index에 추가해주면 된다.

소스

2293 동전 1

n개의 동전을 조합하여 k원을 만들 때 만들 수 있는 모든 경우의 수를 구하는 문제이다.
이 문제는 TLE가 중요하게 작용한다.
내가 처음에 생각한 방법은 재귀로,각 동전으로 만들 수 있는 돈의 모든 경우로 분기하여
K원이 될때 표시해주는 방식이었는데, 답은 정확했으나 쉽게 TLE가 발생했다.

그 다음으로 생각한것이 dp인데, 동전으로 만든 각 원에 대한 index 배열을 생성하고,
해당 동전을 0개~m개 사용할 때의 경우를 가정하여 계산했다.
정답은 맞았으나 다른 사람의 소스에 비해 시간이 많이 느렸다.

그래서 다른 사람의 소스를 살펴본 결과,
각 동전의 값어치 부터 k원까지 증가시키면서, 그 값에 원래의 값어치를 감소 시켰을 때의 배열값을 덧붙여 나가는 방법으로 해서, 소스도 시간도 줄이는 멋진 코드가 되었다.

역시 다른사람들의 소스를 보는것은 중요한 것 같다.

소스

2949 45도

문자열을 45도의 배수만큼 회전시키는 문제이다.
회전 알고리즘은 특정 좌표를 직접 회전시켜서 나온 좌표와 비교하면 편한데,
문제는 45도로 여러번 회전시킬 때이다.
결과적으로는 회전이 되긴하는데, 제자리 회전이 아니라 간격이 계속 벌어지게 된다.
이럴때 좋은 방법은 90도 회전을 따로 구현하는 방법이다.
90도 회전은 간격이 벌어지지않고 가로,세로 길이만 바뀌기 때문에,
45도가 넘어갈땐 90도로 연산을 처리 한 후, 그 나머지가 45도이면 45도 회전을 수행하면 된다.

소스

2784 가로 세로 퍼즐

주어진 6개의 단어로 3*3 가로세로퍼즐이 성립하도록 배치하는 문제이다.
알고리즘으로 생각하려면 매우 복잡해지지만, 퍼즐이 3*3밖에 안된다는 점을 이용해서
가능한 모든 케이스를 넣고, 이 케이스가 퍼즐이 성립하는지를 판단하면 된다.

정답이 복수인 경우는 사전순으로 출력해야 하므로 우선 정렬을 해주고,
3중 반복으로 각 라인에 단어를 넣은 후, 퍼즐이 성립하는지 보면 된다.

퍼즐이 성립하는지의 여부는 6개의 단어가 퍼즐의 가로, 세로에 모두 배치되어있는지를 보면 된다.

소스

5211 가단조와 다장조

주어진 음계가 가단조인가 다장조인가를 찾는 문제이다.
각 마디의 첫 음이 A,D,E로 시작하는게 많으면 가단조, C,F,G로 시작하는게 많으면 다장조 이다. 둘이 같으면 가장 마지막 음으로 구분한다.

strtok함수를 써서 |로 마디를 구분하여 첫음을 찾으면 된다.

소스

5692 팩토리얼 진법

각 자리의 수를 팩토리얼로 나타낸 수가 팩토리얼 진법이다. 이를 10진수로 나타냈을때의 수를 구하는 문제이다.

팩토리얼은 원래 엄청나게 큰 수가 되기 때문에 어려운 문제인 줄 알았으나, 다행히도 최대 5자리 밖에 입력이 주어지지 않는다. 따라서 10진수를 구할때 10씩 곱해주듯이, 팩토리얼도 마찬가지로 다음숫자를 곱해주면 된다.

소스

5623 수열의 합

수열에서 두 수를 뽑아 그 합으로 만든 행렬으로 원래의 수열을 판별하는 문제이다.

이 문제를 푸는 방법은 행렬 각각의 숫자의 합,차를 이용하는것인데,
예를들면
A[2] = S(0,2) + S(1,2) - S(0,1)
A[3] = S(0,3) + S(1,3) + S(2,3) - S(0,1) - A[2]
이런 방법으로 A[2]를 구하면 다음 수를 밝혀낼 수 있다.
문제는 A[0]과 A[1]인데,
이것은 A[2] 를 구해내면 A[0]= S(0,2) - A[2] , A[1]= S(1,2) - A[2] 의 방법으로 구할 수 있다. 이 방법을 통해 A[0],A[1]의 값을 측정해낸 후,
A[3] = S(0,3) - A[0]
A[4] = S(0,4) - A[0]
이렇게 A[0]만 가지고도 값을 구할수도 있다.
생각 여하에 따라 시간차이가 많이 나는 문제이다.

소스

2669 직사각형 네개의 합집합의 면적 구하기

직사각형의 4개의 좌표를 입력받고, 겹쳐진 직사각형들이 이루는 면적을 구하는 문제이다.
이 문제는 주어진 좌표만큼 그래프에 점을 찍고, 다 찍은 다음에 점의 갯수를 구해서 출력해주면 된다.

소스

3054 피터팬 프레임

단어를 꾸며서 나오는데, 3의 배수인 단어만 특별한 문자로 꾸미는 문제이다.

단어마다 한칸씩 달라붙어 있어서, 특별한 문자가 일반 문자를 덮는 꼴이 되어야 한다.

각 줄마다 공식을 잡아서 바로바로 출력해줘도 되지만,

내가 한 방법은 출력하기 전에 배열을 잡아서 거기다가 넣고 나중에 한번에 출력하는 방법이다. 이 방법의 장점은 달라붙어있는 단어 때문에 생기는 복잡한 점을 해결해 준다는대에 있다. 또한 출력은 가로방향으로 밖에 할 수 없어서 여러 조건을 붙이게 되는데, 그것을 해결해 준 것이기도 하다.

소스

2816 디지털 티비

티비 채널 중에 KBS1을 첫번째로, KBS2를 두번째로 옮기는 방법을 묻는 문제이다.
최대 100개의 채널이 주어지고, 500번의 기회안으로 옮겨야 되는데, 옮기는 방법은 다음과 같다.

1. 화살표를 한 칸 아래로 내린다. (채널 i에서 i+1로)
2. 화살표를 위로 한 칸 올린다. (채널 i에서 i-1로)
3. 현재 선택한 채널을 한 칸 아래로 내린다. (채널 i와 i+1의 위치를 바꾼다. 화살표는 i+1을 가리키고 있는다)
4. 현재 선택한 채널을 위로 한 칸 올린다. (채널 i와 i-1의 위치를 바꾼다. 화살표는 i-1을 가리키고 있다)

이 문제를 푸는 간단한 방법은 KBS1을 찾을 때 까지 1번으로 채널을 내리고, KBS1을 처음 까지 4번으로 채널을 올린다. KBS2도 마찬가지로 1번으로 내려가고, 두번째 까지로 4번으로 올리면 된다.
채널 수가 총 100개이기 때문에 각 채널을 1,4번으로 옮기는 최악의 경우는 200번. 채널이 2개이기 때문에 최대 400번의 기회로 옮기는것이 가능하다.

소스

9469 폰 노이만

서로 반대편에서 달려오는 두 기차사이에 파리가 왔다갔다 하고 있다.
두 기차가 부딪힐 때 까지 파리가 움직이는 거리는 얼마인지를 구하는 문제이다.
처음엔 반복문을통해 실제 움직인 거리를 계산하려 했으나..
소숫점 연산의 복잡함을 깨닫고 공식으로 풀게 되었다.

처음 거리가 D이고 두 기차의 속도가 각각 A,B이고, 파리의 속도가 F라면
두 기차가 부딪힐때 까지의 시간은 D/(A+B)가 되고 파리는 그 시간동안 왔다갔다 하기 때문에 결과적으로 D/(A+B)*F가 파리의 이동거리가 된다.

역시 수학은 잘하고 봐야해..

소스

7513 준살 프로그래밍 대회

단어 목록에서 단어를 찾아 이어붙여 출력하는 문제이다.
단순히 배열에 단어를 집어넣고 주어지는 인덱스대로 단어를 출력해주면 된다.

소스

9610 사분면

해당 좌표가 몇사분면에 있는지 혹은 축에 있는지를 판별하는 문제이다.
간단하게 x,y좌표의 부호와 0의 여부만 밝히면 된다.

소스

1764 듣보잡

듣도못한 사람과, 보도못한 사람에 둘 다 포함되면 듣도보도못한 사람이 된다.
이 듣도보도 못한 사람의 숫자와, 정렬되어있는 리스트를 뿌려주는 문제이다.

처음엔 듣도못한 사람, 보도못한사람을 정렬시켜주고, 거기서 듣도보도못한 사람을 추출해주는 방법으로 문제를 풀었다. TLE가 나기 쉬우므로 qsort와 bsearch를 이용했다.
그런데 다른사람의 소스를 보니, 굳이 둘 모두의 배열을 선언할 필요는 없었다.
따라서 듣도못한 사람을 배열에 저장하고, 보도못한사람을 한명씩 받아서 search한다.
있으면 듣도보도 못한 사람에 넣고, 모든 작업이 끝나면 듣도보도못한 사람을 정렬하여
처음부터 뿌려주면된다.

소스

1074 Z

2^N * 2^N 의 배열을  z모양으로 탐색하려고 할 때, 몇번째의 이동에 r,c 좌표에 도착하는 지를 구하는 문제이다.

이 문제는 복잡하게 보이지만, 전체의 사각형을 4분할 하면서 사이를 좁히면 된다.
2차원 그래프로 말하자면 사분면이라고 생각하면 된다. 1사분면을 넘어가면 그 넘어간 갯수만큼을 더해주고, 2사분면을 넘어가면 또 그 만큼 더해주고 를 반복한다.
그런 작업이 끝나면  현재 위치에서 다시 4분할 하여 위 방법을 반복해주면된다.

소스

2290 LCD TEST

모니터에 숫자모양의 그림을 뿌리는 문제이다.

원래같으면 문자열 배열로 하나하나 만들면되는데, 크기까지 입력받기 때문에 그렇게는 할 수 없다.

이 문제는 숫자그림의 성질을 이용하면 된다.

      --   --          --   --   --   --   --    --  

   |     |    | |   | |    |        | |  | |   | |  | 

   |     |    | |   | |    |        | |  | |   | |  | 

      --   --    --   --   --         --   --       

   | |        |     |     | |  |    | |  |     |  |  | 

   | |        |     |     | |  |    | |  |     |  |  | 

      --   --          --   --         --   --    -- 

이것이 크기 2일때의 그림인데(여기다 옮기면서 간격이 약간 다르다) 성질은 아래와 같다.

1. 가로 문자 '-' 는 첫줄과 중간줄, 끝줄에만 나오며, 첫칸과 끝칸은 공백, 중간은 크기만큼 출력한다.

2. 세로 문자 '|' 는 1번에 해당하지 않은 줄에서 나오며, 첫칸과 끝칸에만 존재한다.

이 두가지 사실을 이용해서 '-'는 각 숫자마다 첫줄,중간줄,끝줄의 어디에 나오는지를 bit masking 한 배열을 만든다.

'|'는 각 숫자를 세로로 반절 나눠서 첫칸,끝칸 어디에 나오는지를 bit masking 한 배열을 만든다.

위 배열을 이용해서 공백을 섞어 출력해주면 된다.

소스

9417 최대 GCD

숫자 쌍의 GCD 값이 최대 인것을 찾는 문제이다.

아래 문제와 거의 비슷한 구조에서 합대신 최댓값을 찾도록 해주면 된다.

소스

9613 GCD합

주어지는 숫자 쌍의 GCD의 합을 구하는 문제이다.
GCD는 최대공약수를 뜻한다.
이중 for문을 통해 두 수를 뽑아내고, 그 수들의 GCD값을 구해서 더해주면된다.

소스

9322 철벽 보안 알고리즘

2개의 공개키의 순서를 이용해서 암호문을 만들 때, 이를 평문으로 고치는 문제이다.
암호문은 평문을 공개키의 순서를 반대로 해서 넣은것인데,
이는 반대로 암호문을 공개키 순서대로 재배치하면 평문이 나온다는 의미가 된다.
따라서 첫번째 공개키의 단어 중  두번째 공개키에 속해있는 곳의 위치를 찾고,
그 둘의 위치를 암호문에 적용해서 배치 해주면 평문이 나오게 된다.

소스

1759 암호 만들기

주어진 문자들을 오름차순으로 길이 K의 순열을 만드는 문제이다.
단, 모든 순열은 모음1개이상, 자음2개이상으로 이루어져야 한다.

개인적으로 순열을 만들때는 재귀가 가장 편하다.
우선 문자들을 오름차순으로 정렬 한 후, 처음부터 시작하여 문자들을 하나 씩 뽑으며 재귀한다. 뽑을 때는 뽑은 단어들을 저장할 배열을 하나 만들어준 후, 거기에 쌓아가면 된다.

길이 K개 까지 뽑았다면, 모음과 자음의 수를 추출하여 조건을 만족할 때만 출력해주면 된다.

소스

1181 단어정렬

주어진 단어들을 오름차순으로 정렬하는 문제이다. 단, 여기서의 단어의 대소는, 약간 다르게 길이가 짧으면 무조건 작다고 판단한다.

이 문제는 구조체를 이용해서 풀었다. 길이를 저장하는 int형 변수와, 단어를 저장하는 char형 배열을 구조체로 담고, 데이터를 받아오면서 길이를 strlen 함수로 즉각즉각 담아준다.

정렬 할 때엔 c언어 레퍼런스 함수인 qsort 를 이용하여 정렬. 이 때 qsort에 들어가는 cmp 함수는, 길이를 먼저 비교하고, 길이가 같을 때에만 strcmp 함수로 비교를 해주는 함수이다.

이제 출력하면 되는데, 같은 단어가 있으면 한번만 출력해야 한다. 데이터를 받아올 때 같은 문장은 저장을 안하도록 할 수 도 있지만, 그냥 다 받아와서 정렬을 하고 나면, 같은 단어는 연속으로 저장되기 때문에, 쉽게 거를 수 있다. temp변수를 하나 둬서 현재 위치의 단어와 temp 의 단어가 다를 때에만 temp의 단어를 출력 해주고, temp의 값을 현재 위치로 바꾸어 주는 작업을 반복하면 된다.

소스

7575 바이러스

N개의 숫자열 중에서 길이가 K개 이상이면서, 모든 숫자열에 포함되어있는 숫자열이 존재하면 바이러스가 있다고 한다. 단, 이 숫자열을 거꾸로 뒤집었을 때 포함되어 있어도 존재한다고 판단한다. 바이러스가 있으면 YES, 없으면 NO를 출력하는 문제이다.

이 문제는 TLE가 촉박한 문제이다.
원래 같으면 한 줄을 잡아서,  길이 K의 윈도우를 슬라이딩 해가면서 다른 줄과 비교하기만 하면 끝이지만, 이 비교하는 과정에서 최악으로 O(n^2)의 시간복잡도를 가지게 된다. 시간제한은 1초 밖에 안되기 때문에 알고리즘을 따로 만들어줘야 한다.

이 문제는 사실 범위가 1~10000이라 그렇지 문자열 매칭과 똑같은 방법으로 풀 수 있다.
따라서 문자열 매칭에 유명한 알고리즘인 kmp 를 사용하여 비교해주었다. kmp 알고리즘은 시간복잡도가 O(nk)를 보여서, 선형시간에 비교를 마칠 수 있다.

거꾸로 해야 포함되는것은, 슬라이딩 하는 한 줄을 거꾸로 돌려서 다시 비교해도되고, 비교하는 다른 줄을 거꾸로 돌려서 비교해도 된다.

p.s. 한 줄에서 길이를 K만 잡는 이유는 K보다 높은 길이에서 바이러스가 존재하면, K개에서도 바이러스가 존재하기 때문이다.

소스

1919 애너그램 만들기

두 문장으로 각각 애너그램을 만든 다고 할 때, 두 문장에서 한글자 씩 없에서 서로 일치한 애너그램을 만든다고 하자. 이 때 최소 몇글자를 지우면 만들 수 있는지 출력하는 문제이다.

어떤 애너그램이든 일치하기만 하면 된다는 것은 문자의 순서는 상관 없고, 각 문자가 몇개씩 있는지가 중요하다. 따라서 두 문장의 각 문자마다 갯수를 알 수 있는 index 배열을 선언하고 조사하여, 둘을 비교하면 된다.

소스

2161 카드1

카드를 위에서부터 한장은 버리고 한장은 맨 밑으로 집어넣으면서 버린 카드의 번호를 출력하는 문제이다.
큐 라고 생각하고 풀면 쉬운데,
나는 값이 바뀔때마다 스왑하는 방식을 취하지 않고
배열크기를 늘려 뒤에 계속 쌓이도록 구현했다.
케이스가 많아지면 스왑해주면 TLE가, 배열크기를 늘리면 메모리초과가 날것 같은데
어떻게 해야 할까..?

소스

3076 상근이의 체스판

r*a 행 c*b 열 의 체스판을 출력하는 문제이다.
검정과 흰색이 번갈아가며 나와야 하는데,
이것은 r/a+c/b 가 홀수이면 흰색, 짝수면 검정색으로 구분 하면 된다.

소스

2840 행운의 바퀴

룰렛을 시계방향으로 돌려서 나온 문자들을 가지고 원래의 문자들을 알아내는 문제이다.
해당 정보로 알아내지 못하는 문자는 ? 로, 문자자체에 에러가 있으면 !를 출력한다.

일단 원래의 문자를 알아내는 방법은 현재의 상태에서, 직전에 회전시킨 횟수만큼 회전시켰을 때의 상태를 구하고, 그 상태를 index로 삼아서 직전에 나온 문자를 기록한다.
모든 문자를 기록하고 나면 차례대로 출력하는데, 해당 상태에 문자 정보가 없으면 그자리에 ? 를 출력한다.

문제는 !가 되는 경우인데, 이것은 해당상태에 이미 기록되어있는데 다른 문자로 덧씌워질 경우에 !를 출력한다. 또, 같은 문자가 여러번 사용되도 !를 출력한다.

소스

2935 소음

10의 제곱 형태의 두 큰수의 덧셈과 곱셈한 값을 출력하는 문제이다.
큰 수이기 때문에 일단 문자열 형태로 받아온 후,
두 문자열의 길이를 구한다.
곱셈은 두 문자열의 길이의 합 - 1 만큼이 결과값의 길이가 된다.
처음 숫자만 1로 출력해주면 답이 나온다.
덧셈은 두 문자열의 길이 중 큰수 만큼만 반복하면서, 해당 위치가 큰수와 작은수의 길이의 차이와 같으면 1을 추가로 더해주면 된다.

소스

2987 사과나무

삼각형의 세 좌표가 주어졌을 때, 삼각형의 넓이와 그 다음에 주어지는 좌표가 삼각형 내부에 있는지 없는지를 알아내는 문제이다.

세 좌표로 삼각형의 넓이를 구하는 공식은 다음과 같다.
|xA(yB-yC)+xB(yC-yA)+xC(yA-yB)| / 2

내가 푼 방법은 넓이는 저 공식대로 구하고, 내부 외부 판별은, 삼각형을 세 직선으로 구분해서 삼각형의 무게중심의 좌표를 각 직선에 대입해본다.
그러면 그 값의 부호를 알 수 있는데, 음수이면 그 직선보다 아래, 양수이면 그 직선보다 위에 있다는 뜻이다. 무게중심과 세 직선과의 부호 관계를 알아낸 후, 나중에 받아온 좌표를 똑같은 방법으로 비교했을 때 부호관계가 무게중심때와 같았다면 내부, 아니면 외부로 판단해 주었다.
단, 직선의 경계에 있어도 내부이기 때문에 값이 0일 때도 따로 처리해 주어야 한다.

이렇게 하면 답을 구할수는 있지만, 사실 직선을 구성할 때 기울기의 분모가 0이 되는 경우가 있다. 이것도 따로 처리해주어야 되는데 혹시나 해서 그냥 제출해 보았더니 정답이 떴다.
테스트 케이스가 적어서 그런가해서 따로 분모가 0이 되게끔 좌표를 넣어줘 봤는데
분명 런타임 에러가 뜰것으로 예상했으나 에러는 커녕 결과까지 제대로 나왔다... 이유는 잘 모르겠다. double형이라 그런거 같은데, 부동 소숫점에 대해 제대로 알아봐야 할 것 같다.

사실 이것보다 훨씬 편한 방법이있는데, 다른 사람의 소스를 보고나서야 알았다.
그 방법은 따로 받아온 점과 삼각형의 두개의 점을 고른 세 삼각형의 넓이의 합이 원래 삼각형의 넓이와 같으면 내부, 다르면 외부인 것이다.

역시 수학은 잘하고 봐야 한다..

소스

2810 컵홀더

영화관에 컵홀더가 있는데, 커플석에는 중간에 컵홀더가 없다고 한다. 이때, 컵홀더를 사용할 수 있는 사람의 수를 구하는 문제이다.
생각보다 풀기 까다로운데, 규칙을 잘 생각해보면
커플의 수 만큼 컵홀더를 사용하지 못하는 사람이 생긴다.
단, 양끝에 하나씩 주어지기 때문에,
커플이 있을경우엔 커플 수 - 1로 계산해주어야 한다.

소스

2702 초6 수학

최대공약수와 최소공배수를 구하는 문제이다.
최대공약수는 두 수를 번갈아가면서 나머지 연산을 해서, 한쪽이 0이 될때까지 반복하면 남은 수가 최대공약수가 된다.
최소공배수는 두 수를 곱한 후, 최대공약수로 나누면 최소공배수가 된다.

소스

2435 기상청 인턴 신현수

숫자들을 연속 k개를 합쳤을 때, 가장 큰 수를 구하는 문제이다.
단순히 배열 첫번째부터 끝까지 반복하면서 k개의 합을 구하고, 그중에 가장 큰 수를 구하면 된다.

소스

1475 방 번호

0~9의 숫자가 한번씩 적힌 세트로 주어진 숫자를 채우려고 할 때, 세트를 최소한 사용할때의 갯수를 구하는 문제이다.
단 6과 9는 뒤집어서 같이 사용할 수 있다.

이 문제는 우선 0000도 입력으로 들어오기 때문에 숫자가 아닌 문자로 받아야 한다.
각 숫자의 index 배열을 선언해서 받아온 다음, 가장 많이 사용된 숫자를 고르면 필요한 세트를 구할 수 있다.
단, 6과 9는 같이 계산해야 하므로 받아올때도 6과 9를 같은 6으로 판단해서 넣고,
고를때는 6을 2로 나누고 반올림한 값으로 판단하면 된다.

소스

4504 배수 찾기

n의 배수를 찾는 문제이다.
k%n==0 으로 간단하게 찾을 수 있다.

소스

2798 블랙잭

숫자 3개를 뽑아 특정 숫자보다 크지 않으면서 최대한 가까운 수를 고르는 문제이다.

숫자의 갯수가 최대 100개 밖에 되지 않기 때문에
그냥 O(n^3)의 시간복잡도로 3개를 뽑아서 비교하면 된다.

소스

5567 결혼식

자신의 친구와, 그 친구의 친구의 수를 구하는 문제이다.
2차원 배열로 간선을 만들고 자신의 친구가 있으면, 그 친구의 친구목록을 찾아서 구하면 된다.
여기서 친구의 친구를 찾자마자 답을 구해버리면 중복된 친구가 생길 수 있다.
예를들어 1이 자신이고 나머지가 친구의 번호라고 하면,
1 - 2
1 - 3
2 - 3
의 친구관계가 있을 때, 2,3이 친구가 되는데 2-3 에서 한번 더 추가가 되기 때문에
2여야할 답이 3이 나와버린다.
따라서 구한 친구의 리스트들을 저장하여 중복을 없에주면 된다.

소스

1769 3의 배수

3의 배수를 각 자리의 숫자의 합으로 바꾸는 작업으로 판별하는 문제이다.
자리수가 10^100만 자리 까지기 때문에 문자열로 취급해서 받아야 한다.
처음에는 어떻게 해야하나 고민했는데
생각해보니 처음 숫자가 10^100만 자리여도 각 숫자를 전부 더해봐야
최댓값은 9000000 즉 10^7 자리 밖에 되지 않는다.

따라서 처음 한번만 계산하면 나머지는 int 형 범위안에서 충분히 계산 가능하다.
나는 각 자리 수를 int형 변수에 더해서 sprintf 로 다시 문자열로 바꿔주는 방법을 이용했다.

소스

5622 다이얼

다이얼을 이용하여 알파벳을 입력하려 할 때 걸리는 비용을 계산하는 문제이다.
간단하게 알파벳 26자리에 대해 필요한 비용을 배열로 입력하여
한글자씩 비교하면서 더해주면 된다.

소스

5176 대회 자리

사람들이 자신이 원하는 자리만 앉으려고 할 때, 자리에 못앉게 되는 사람의 수를 구하는 문제이다.

단순하게 배열에 index를 이용해서 앉으려는 번호의 자리에 표시를 하고

사람의 수와 표시가 된 자리의 갯수를 빼주면 못앉는 사람의 수가 나오게 된다.

소스

2846 오르막길

오르막길의 최장 거리를 구하는 문제이다.
여기서 주의할점은 중간에 한번이라도 같은 높이가 나오면 오르막길이 끊키게 된다.
또한 처음 높이를 시작으로 치기 때문에 0~처음높이를 오르막길로 치지 않는다.

이 문제를 푸는 방법은
일단 높이를 받아올 변수(n)와, 오르막길이 시작하는 높이를 저장하는 변수(i), 점점 높아질 수록 그 높이를 저장하는 변수(k), 가장 높았던 길이를 저장할 변수(s)가 필요하다.
가장 처음과 오르막길이 끊키게 될 경우는 i와 k를 n으로 초기화 하고 오르막길이 이어질 경우는 k의 값을 점점 증가시키면서 s를 항상 체크해서 저장하면 된다.

소스

5613 계산기 프로그램

+-*/를 계산 할 수 있는 프로그램을 만드는 문제이다.
간단하게 처음 숫자를 저장한 다음, 연산자와 숫자를 입력받아서 처리해주면 된다.

소스

2865 나는 위대한 슈퍼스타K

N명의 참가자가 M개의 장르에 하나만 도전해서 K명이 선출된다 할 때, 선출된 참가자들의 점수 합이 가장 큰 경우를 구하는 문제이다.

이 문제는 최댓값을 두번 구해야 하는데, 한번은 참가자 개인이 M개의 장르중에 가장 높은 점수를 받을 수 있는것을 골라야 하고, 다음은 그 점수들중에 가장 높은 순으로 K개를 골라야 한다.

문제가 실수형임에 유의하자

소스

3062 수 뒤집기

어떤 숫자와, 그 숫자를 뒤집은 숫자의 합이 대칭인지를 판단하는 문제이다.
어떤 숫자를 n이라 할 때, 뒤집은 숫자는 n을 1의 자리부터 더 하면서 10씩 곱해주면 된다.
그 뒤집은 숫자의 합이 대칭임을 판단하는 방법은 여러가지가 있는데,

내가 사용한 방법은
sprintf 함수를 이용해 숫자를 문자열로 만든 다음, 중앙부터 시작해서 한칸씩 벌어지면서
두 수가 같은지 아닌지를 판단하는 방법이다.

풀고나서 다른사람의 풀이를 봤는데,
그냥 대칭인 숫자도 똑같이 뒤집어서 처음수와 같은가 비교하면 되는 것이었다..

역시 알고리즘 실력의 차이는 이런 곳에서 나오는듯 하다.

소스

2659 십자카드 문제

1~9 의 숫자가 4개 적힌 십자카드를 시계 방향으로 읽었을 때, 가장 작은 수를 십자수 라고 한다. 이 때 주어진 숫자가 가장 작은 십자수로 부터 몇번째 숫자인지 판단하는 문제이다.

일단 가장 작은 십자수는 1111, 가장 큰 십자수는 9999임을 알 수 있다.
여기서 1111~9999까지의 모든 십자수를 구해도 TLE가 나지 않음을 알 수 있다.
십자수를 구하는 방법은 숫자 4개를 a b c d 라고 할 때,
abcd(a*1000+b*100+c*10+d)
bcda
cdab
dabc
의 4개의 숫자중에서 가장 작은걸 고르도록 하면 된다.
이것을 가능한 모든 숫자로 골라서 index 배열에 넣고,
주어진 숫자의 십자수를 index의 위치에서 찾아내면 된다.

소스

1244 스위치 켜고 끄기

스위치를 두가지 패턴에 의해 변경한 후의 결과를 출력하는 문제이다.

첫번째 패턴은 n의 배수에 해당하는 스위치를 반전시키고,
두번째 패턴은 n주변에 대칭을 이루는 스위치를 반전시킨다.

둘 다 적당히 반복문을 이용하여 풀 수 있다.

소스

2504 괄호의 값

괄호열이 나타내는 숫자를 출력하는 문제이다.
조건은 아래와 같다.

한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

‘()’ 인 괄호열의 값은 2이다.
‘[]’ 인 괄호열의 값은 3이다.
‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

이 문제를 풀기 위해선 잘못된 괄호열의 처리와 점수계산을 해야한다.
잘못된 괄호열은 스택구조를 통해 (가 마지막에 들어있다면 ) 가 들어와야만 하는 식으로 구현하면 된다.
점수계산은 레벨 개념을 사용한다.
레벨은 괄호열 안에 괄호열이 들어갈 수록 높아진다고 가정한다.
높은 레벨의 괄호가 닫히면, 한 단계 낮은 레벨의 점수를 수치에 맞게 더해준다.

글은 쉽게 쓰지만 상당히 어려운 문제이다.

소스

3613 Java vs C++

java식 변수선언(첫글자는 소문자로,다음에 나오는 단어는 첫글자만 대문자로,구분자x) 과
c++식 변수선언(모두 소문자, 구분은 _로) 을 서로 바꿔주는 문제이다.
바꿔주는것은 쉽지만, 예외가 은근히 많다.

다음은 error가 발생하는 조건이다.
1. 첫글자와 끝글자가 _ 이다.
2. 첫글자가 대문자이다.
3. 대문자와 _가 섞여있다.
4. _가 연속으로 사용된다.

c++에서 java 로 바꿔줄때는 _가 나타날 때마다 다음 글자를 대문자로 바꿔주면 된다.
반대로 java에서 c++로 바꿔줄때는 앞에 _를 붙이고 소문자로 바꿔주면 된다.

개인적으로 c++을 선호한다 ㅎㅎ

소스

9455 박스

테트리스같이 공중에 떠있는 조각들을 전부 지면에 쌓을 때 움직이는 총 비용을 계산하는 문제이다.

간단하게 각 라인마다 몇층이 쌓여있는지를 판단하는 배열을 잡고,
가장 밑바닥 부터 시작해서 조각이 있으면 층을 하나씩 쌓으면서,
비용을 조각의 높이 - 쌓인 층 수 만큼 증가 시키면 된다.

테트리스에서 스페이스 바 를 누르면 맨 밑으로 점프시킬때와 비슷한 느낌?

소스

3077 임진왜란

여러 단어들을 정답이 되는 순서와, 제출한 순서를 놓고 비교를 하려고 한다.

이 때, 임의의 서로 다른 두 답을 뽑아서, 그 순서와 제출한 순서가 맞은 경우의 수를 찾는 문제이다.

내가 푼 방법의 핵심은 아래와 같다.

단순하게 정답에서 두 단어를 뽑고, 그것과 같은 단어를 제출한 답에서 찾는다.

그리고 뽑은 각각의 두 단어의 순서가 서로 같은지를 비교해서 점수를 증가시킨다.

단순히 이렇게만 작성해서 제출했는데 TLE가 떴다.

시간 복잡도가 대략 O(n^3)이 었으니 TLE가 나올 만도 하다..

그 다음엔 qsort와 bsearch 를 이용하여 제출했는데 마지막 케이스에서 TLE가 떴다.

이 때의 시간 복잡도는 O(n^2*log2(n))이다.

마지막 방법은 위 두가지에 index 를 이용한 것이다. 한번 검사한 단어는 index를 따로 저장해서 상수시간에 바로 찾을 수 있게끔 한 방법이다.

따라서 시간 복잡도는 O(n^2)이 된다.

알고리즘 자체는 간단했지만, 시간복잡도가 중요하게 작용하는 문제였다.

소스

2730 오늘은 OS 숙제 제출일

주어지는 두 날짜의 간격이 7일을 넘는지 안넘는지를 판단하는 문제이다.
단순한 날짜 계산 문제인데, 주의해야 할 점은
12월 말이나 1월 초에는 내년,작년 의 경우가 있다는 것과,
2월말에는 윤년이 낀다는 점이다.

내가 푼 방법은 time.h 헤더를 이용해서 타임스탬프를 구하여 푸는것이었는데,
이상하게 자꾸 틀렸다고 떴다.
나중에 알아낸 바로는 윈도우에선 time_t 자료형이 64비트 정수형인데, 리눅스에선 32비트를 사용해서 2038년이 지나가면 에러가 떠서 틀리는 것이었다.
그래서 꼼수로 윤년일 경우는 2000년, 아니면 2002 년을 기준으로 계산을 시켜서 풀었다.

역시 꼼수를 쓰는것은 그다지 바람직하지 못한것 같다..

소스

2828 사과 담기 게임

화면에 떨어지는 사과를 바구니로 담는 게임에서 이동하는 횟수의 최솟값을 구하는 문제이다.
바구니의 넓이에 맞춰서 끝자락에만 닿도록 해주면 최솟값을 구할 수 있다.

소스

5212 지구 온난화

지구 온난화로 인해 해수면이 증가해 육지가 잠기게 된다.
삼면이 바다로 둘러쌓이는 땅은 잠기게 되는데, 잠긴 후의 지도를 출력하는 문제이다.
간단하게 문자열로 입력받아서, 점 한개씩 검사해서 삼면이 바다이면  바다가 되게끔 해주면 된다.
그에 따라 지도의 크기도 줄여야 되는데, 이것은 가로세로 맨처음과 맨끝부터 검사해서 그 부분이 모두 바다이면 크기를 줄여나가면 된다. 단, 하나라도 땅이 있으면 줄이는것은 그 전까지로 만 해야 하는것에 주의하자.

소스

2480 주사위 세개

주사위 세개를 굴려서 조건에 맞춰 상금을 출력하는 문제이다.
사실 예전에 풀은 문제와 거의 같아서 소스를 가져다 썼다.
특별히 어려운 점은 없을 듯 하다.

소스

2818 숙제하기 싫을 때

주사위가 오른쪽, 왼쪽, 아래로 굴러갈 때, 맨 위에 표시된 숫자들의 합을 구하는 문제이다.
이것을 구현하기 위해선 주사위의 숫자가 변동되는 규칙이나 패턴을 알아내야 한다.
원래는 그렇게 풀어야 하는거지만.. 나는 주사위를 앞에서 봤을 때 보이는 세 숫자들의 조합을 전부 배열로 나타내서 일일히 하나하나 점프를 하는 방식의 자료구조를 작성했다..
정답을 맞을 땐 기분이 좋았으나 다른 사람들이 짠 간단한 코드를 보고 좌절감이..

참고로 무조건 한번씩 다 굴리면 TLE가 뜨기 때문에 한 방향으로 4칸을 굴렸을 시 합이 무조건 14 인것을 이용해서 연산을 줄이면 된다.

소스

링크 걸기도 창피한 소스이다..

4779 칸토어 집합

선을 계속 3등분해서 모든 선의 길이가 1일 때 까지 반복하여 결과를 출력하는 문제이다.
문자열로 가상의 선을 만들고, 길이를 3등분해서 가운데것은 지우고 나머지 2등분을 각 각 재귀시키는 함수를 실행한다.
함수가 끝나면 문자열을 출력하면 된다.

소스

9987 포켓몬 마스터

포켓몬 번호를 입력하면 포켓몬의 이름과 타입을 출력하는 문제이다.
http://pokemondb.net/pokedex/national 
이곳의 데이터를 이용하여 문제를 풀면 된다.
데이터를 형식에 맞춰주는것이 중요하고
669번 같이 포켓몬 이름이 이상한 경우도 신경을 써주어야 한다.

소스

1083 소트

정말 미친듯이 틀린 문제이다..
내 acm 문제풀이 역사상  이렇게 많이 틀린 문제는 없을것이다.
그만큼 어렵다기보단 불친절한 문제라는 의미이다.
이 문제를 욕하는것은 아니고, 그것을 캐치해내지 못한 내 불찰이라고 생각한다.

각설하고 문제에 대해 설명해보자면,
숫자의 목록들이 있고, 이 숫자를 내림차순으로 정렬하려고 한다.
단, 정렬 할 땐 가장 인접한 숫자들끼리의 swap 만 가능하고, 횟수에도 제한이 있다.
이 때 정렬한 결과가 사전순으로 가장 뒷서는 경우의 숫자를 출력하는 문제이다.

여기서 사전순이라는 것이 함정인데, 실제 사전순으로 보면
9 > 10 이어야 맞다.
하지만 여기서의 사전순은 단순히 숫자의 크기를 의미한다. 즉,
10 > 9

단순한 내림차순 문제가 아니라,
숫자가 1 2 3 4 5 에 기회가 4번 이면,
답은 5 1 2 3 4 가 나와야 한다.

이 문제를 푸는 방법은 우선 현재 남은 기회로 임의의 숫자를 맨 앞으로 보낼 수 있는
범위내에서의 최댓값을 고른다.
그 최댓값을 맨앞으로 보내면서 기회를 감소시킨다.
기회가 0이 되거나 정렬이 완성될때까지 반복한다.

이 사전순이라는 의미에 낚여서 엄청 고생하고
케이스가 여러번이라는것에도 낚여서 고생했다.
보통은 케이스의 횟수를 주거나 마지막케이스를 나타내는 입력을 주는데,
이 문제엔 그것이 없어서 한번만 출력하는 문제인줄 알았다.
앞으로는 이런것에 주의해야 겠다..

소스

1463 1로 만들기

1. N이 3으로 나누어 떨어지면, 3으로 나눈다.
2. N이 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
의 3가지 과정중에 아무거나 써서 숫자를 1로만든다. 이때 최소한의 과정을 사용할때의 횟수를 구하는 문제이다.
첨엔 공식으로 한번에 답을 유추하려했지만, 도저히 풀리질 않았다.
어쩔 수 없이 재귀를 통해 답을 풀었다.
재귀로 사용한 방법은
1,2번을 동시에 만족할때는 1,2번으로 재귀.
1번만 만족 할 때는 1번으로 재귀.
2번만 만족 할 때는 2번과 3번으로 재귀.
둘 다 만족하지 않을 때는 3번으로 재귀.
재귀를 할때는 항상 횟수를 1씩 늘려주는 변수를 가지고 있어야 한다.
그리고 n이 1이 됬을때, 최소가 되는 값으로 걸러주면된다.

나름 고생한 문제..

소스에는 다른사람이 푼 소스가 주석으로 걸려 있다.

소스

2485 가로수

임의의 간격으로 세워진 가로수를 더 심어서, 모두 일정한 간격으로 맞추려고 할 때, 심어야 하는 최소한의 갯수를 찾는 문제이다.
간단하게 생각해보면 모든 가로수를 1칸 간격으로 심으면, 두 가로수의 간격 - 1 개의 합으로 계산이 가능하다.
처음에 떠올린것은 가로수의 간격중 최솟값을 찾고, 그 최솟값과 나누어떨어지지 않는 간격이 있으면, 무조건 1개씩 심도록 했는데 오류가 났다.
이유는 최솟값이 4이고 다른 나무의 간격이 6이면 2개씩 심으면 되기 때문이다.
저 케이스를 보고 번뜩 생각난것은 최대공약수였다.
모든 간격과의 최대공약수를 구해서 그 값에 맞게 심으면 된다.

소스

1991 트리순회

이진 트리를 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 한 결과를 출력하는 문제이다.
이 문제를 풀기위해선 트리구조를 구현해야 하는데,
처음엔 귀차니즘으로 인해 단순히 배열로 인덱스를 2배씩 늘려가는 형식의 트리구조를 만들었다. 정답은 맞았지만, 이것은 틀린 소스이다.
그 이유는 26개의 노드를 전부 한쪽으로 쏠리게 입력하면, 내가 처음 짠 소스로 돌렸을 경우, 인덱스가 최대 2^26-1 까지 가게 되어 메모리제한이 걸리게 된다.
빨리 깨달았어야 했는데 다른 분의 소스를 보고나서야 깨닫고 말았다.. 완전히 내 불찰이다.
바뀐 트리구조는, 노드 마다 인덱스가 아닌 이름으로 정의 되어 있어서 A-Z까지 26개의 배열을 선언하기만 하면 된다. 단, int 형 배열이 아닌 left와 right 변수를 가진 struct 구조이다.
트리구조를 완성 시켰으면 세가지 순회를 해야하는데, 이 알고리즘은 간단하다.

재귀를 이용하여
//전위 순회일때 여기서 출력
f(node->left);
//중위 순회일때 여기서 출력
f(node->right);
//후위 순회일때 여기서 출력

위와 같은 위치로 출력을 해주면 된다.
반성에 반성을 거듭하는 문제였다..

소스

3449 해밍 거리

두 이진수의 해밍 거리를 구하는 문제이다.
해밍 거리는 각 자리수의 값이 서로 다른것들의 갯수이다.
이진수라고 했지만 그냥 문자열 두개를 받고 서로 같은지 다른지 검사하면 된다.
여기서 사용할만한 연산자는 ^(xor) 이다. 서로 다를때만 true를 리턴하기 때문에 간단하게 비교가 가능하다.

소스

3059 등장하지 않는 문자의 합

알파벳 대문자로만 이루어진 문자열에서 한번도 나타나지 않는 알파벳의 합을 구하는 문제이다. 단순한 마킹문제로, 알파벳 갯수만큼의 배열을 잡고, 문자열에 들어 있는 문자를 알파벳을 가리키는 인덱스에 표시를 해주고, 표시가 되지 않은 인덱스들의 합을 구하면 된다.
테스트 케이스가 있는 문제이므로 각 테스트마다 초기화나 구분을 지어주는것을 잊지말자.

소스

1978 소수 찾기

주어진 숫자중에 소수인 숫자의 갯수를 구하는 문제이다.
이런문제는 원래 케이스가 크면 클수록 시간이 촉박해지기 때문에 최소시간으로 소수를 찾을 수 있는 알고리즘을 사용해야 하는데, 이번문제는 케이스도 숫자의 크기도 작기 때문에 단순히 2부터 n-1 까지 나누어 떨어지지 않는 경우로 소수를 판별했다.
원래는 2부터 루트n 까지 찾는게 내가 아는것중에선 가장 빠르다.

소스

1453 피시방 알바

피시방에 해당 자리가 비어있는지 아닌지 검사하는 문제이다.
간단하게 배열을 선언해서 해당 자리가 있는지 없는지 검사하고 자리를 채우면 된다.

소스

3460 이진수

10진수 숫자를 2진수로 변환하였을때, 1의 위치를 출력하는 문제이다.
간단하게 shift 연산자(>>)와 비트연산자(&)를 통해 값이 1일경우 위치를 출력해주면 된다.

소스

2870 수학숙제

문자열 중에 숫자들을 추출하여 오름차순으로 출력하는 프로그램이다.
처음에는 단순히 atoi, atol 함수를 이용해 숫자를 추출해내려 했었는데, 오답이 났다.
이유는 문자열의 길이가 최대 100이라 숫자의 길이 또한 100자리가 될 수 있었던 것이다.
숫자가 100자리 라는것은 long long 형도 뛰어 넘는다는 의미이다.

그래서 두번째 방법으로 숫자를 문자열의 형태로 뽑이내기로 했다.
해당 번지의 문자가 숫자인 경우, 다음에 알파벳이나 개행이 나타날때 까지 배열에 삽입한다. 이때 맨앞이 0으로 시작하면 제외시킨다. 만약 시작도 끝도 0이면 0으로 삽입해야 한다.

그렇게 삽입을 마치면 정렬을 해야 하는데, 문자열을 숫자처럼 취급하여 정렬을 하려면 먼저 두 문자열의 길이를 비교해서 긴 쪽을 크다고 판단한다. 만약 길이가 같으면 strcmp함수로 평범하게 문자열 비교를 하면된다.

이때 c언어 레퍼런스 함수의 qsort 함수를 이용하였는데, qsort 함수의 형식은 다음과 같다.
void qsort(void *arr,size_t num,size_t size,int (*cmp)(void *x,void *y));

arr은 말그대로 데이터를 담은 배열을 의미한다.
len은 정렬할 데이터의 숫자이다.
size는 정렬할 조각 하나의 크기이다. 여기선 문자열의 길이 101(널문자 포함)을 넣어준다.
cmp 는 두 조각을 비교할 함수의 포인터를 의미한다. 두개의 포인터 변수를 입력받아 int 를 리턴해야 한다.


참고 사이트

소스

1629 곱셈

a의 b 승을 c로 나눈 나머지를 구하는 문제이다.
a,b,c의 범위가 0 ~ 2^31-1 까지라서 O(n)으로 코드를 짜도 TLE(Time Limit Exceeded)가 나와버리고 만다. 간단해 보이지만 생각보다 고생한 문제였다.

내가 처음에 생각한 방법은,
곱셈의 패턴들을 저장해서 패턴이 발견되면 바로 정답을 출력하는 방식이었다.
그러나 c의 범위가 int 범위 이다보니 배열또한 그정도 크기를 줘야해서 무리가 있었고, 크기가 무한정 있었다고해도 패턴의 갯수가 최악의 경우 O(2^31) 이 되버려서 TLE가 나고만다..
그 다음으론 log와 modular의 관계를 이용해서 상수 시간으로 풀어보려고했지만, 도저히 방법이 떠오르지가 않았다.

결국 a^b mod c 에 대해 검색을 하면서 깨닫게 되었는데,
요는 c보다도 b를 빠르게 처리하는것이 관건 이었다.
즉, a의 b승을 최대한 빠르게 구해야 하는것이다.

단, a^b 는 변수로 담아 둘 수 없기 때문에 a=a*a%c 의 연산을 계속 해주어야 한다.
이것은 (a*a*a)%c = (((a%c)*a)%c)*a)%c 와 같다는걸 이용한 것이다.

a의 b승을 빠르게 구하는 방법으로 내가 사용한 알고리즘은,
a^2000 = (a^2)^1000 = (a^4)^500 ... = (a^2000)^1
이렇게 a자체를 증가시키면서 b를 2로 나누는 방법이다.
단순히 a^b를 하게되면 O(b)의 시간복잡도를 갖지만,
위 방법대로하면 O(log2(b))의 시간복잡도를 갖게 되어 문제 해결이 가능하다.
b가 홀수인 경우엔 a를 따로 한번 곱해줘서 짝수로 만들고 2로 나누면 된다.

물론 곱하면서 c로 mod 연산을 계속 해주는것을 잊지말자.

참고 문서

소스

7894 큰 숫자

n 팩토리얼의 자리수를 구하는 문제이다.
팩토리얼은 수가 기하급수적으로 커지기 때문에, 실제로 계산해서 변수로 집어넣는 것은 무리다. 따라서 자리수를 알아내는 방법으로 log 를 사용한다.
임의의 숫자 n 의 자리수는 ceil(log10(n))으로 결정된다.
따라서 n 팩토리얼의 자리수는 ceil(log10(n!)) 으로 알 수 있다.
우리는 실제 n!을 구할 수는 없기 때문에,
log의 성질을 이용하여 ceil(log10(n)+log10(n-1)...+log10(1)) 의 방법으로 답을 구하면 된다.

소스

5532 방학숙제

국어숙제와 수학숙제중 어떤것이 더 오래걸리나를 판단하는 문제이다.
숙제를 하루에 10장 할 수 있어도 1장을 풀기위해선 하루가 걸린다는 것만 유의하면 된다.

소스

6996 애너그램

두 단어가 서로 애너그램인지 아닌지를 판별하는 문제이다.
애너그램은 어떤 단어에서 알파벳 순서를 이리저리 바꿔서 나온 단어를 말한다.
내가 이 문제를 풀기 위해 사용한 방법은 (편의상 단어 A B라고 가정)
1. A의 알파벳 하나를 잡고 B의 알파벳들과 비교한다.
2. 만약 둘이 같은것이 있다면 A의 다음 알파벳으로 넘긴다.
3. 이때 매칭된 B의 알파벳을 소거한다. 이유는 A의 같은 알파벳이 두개이면, B도 두개여야 하기 때문. 소거하지않으면, B가 1개의 알파벳을 가지고 있어도 전부 만족할 것이다.
4. A의 모든 알파벳이 매칭되고, A와 B의 길이가 같으면 애너그램이다.

소스

p.s. 생각해보니 두 단어를 전부 정렬하고 같은지 비교하면 더 쉬울것 같다.

1159 농구 경기

성의 맨 첫글자가 같은 사람이 5명 이상 있는 경우 출력하는 문제이다.
간단하게 문자열을 하나씩 받아오고 첫글자만 비교하면 된다.

소스

9414 프로그래밍 대회 전용 부지

매해 n승으로 불어나는 땅의 가격을 가장 싸게 살 때의 가격을 구하는 문제이다.
매년 n승으로 불어나기때문에 비싼 땅을 먼저 사둬야 가장 싸게 살 수 있다.
그러기 위해 내림차순으로 정렬을 한 후, n승에 맞게 가격을 누적해주면 된다.

n승을 구하는 방법으로 powl 함수를 이용했다.

소스

1977 완전제곱수

m 이상 n 이하의 완전 제곱수를 찾는 문제이다.
반복문으로 i를 증가시켜주며 계속 확인해주면 된다.

소스

9461 파도반 수열

n번째 파도반 수열을 구하는 문제이다.
파도반 수열은 나선의 가장 긴 선분을 한 변으로 정삼각형을 계속 그렸을 때, n번째 삼각형의 변의 길이를 나열한 것이다.
그러나 말로해도 잘 와닿지 않기 때문에 직접 세어보면 아래와 같다.
1 1 1 2 2 3 4 5 7 9 ...
대충보니 피보나치가 연상되는데, 숫자가 약간씩 다르다.
피보나치 수열은 f(n) = f(n-1) + f(n-2) 구조를 띠는데 반해
파도반 수열은 f(n) = f(n-2) + f(n-3) 의 구조를 띠는것을 볼 수 있다.
따라서 f(n) 을 담을 변수와 f(n-2),f(n-3) 을 담을 변수, 둘을 교환할 임시 변수 까지 4개의 변수가 필요하다. 그리고 상황에 맞게 swap 을 해주면 된다.

단, n>3 일 경우에만 위 점화식이 성립하는것에 유의하자.

 소스

2495 연속구간

8자리 숫자의 가장 긴 연속구간을 찾는 문제이다.
숫자지만 문자열로 인식해서 받으면 편하다.
반복을 하면서 해당 문자가 다음 문자랑 같으면 카운트를 올린다.
다를경우는 최댓값을 저장하는 변수와 카운트를 비교해서 새로운 최댓값을 정한다.
이 때, 카운트는 처음으로 초기화 해준다.

소스

2644 촌수계산

x와 y의 촌수를 계산하는 문제이다.
나는 이런 문제를 풀때 재귀적인 방법밖에는 써보지 않았다..
어찌됬든 내가 푼 방법을 말해보자면,

우선 2차원 배열인 a를 선언하고 여기에 가족관계를 담는다.(왼쪽이 부모, 오른쪽이 자식)
그리고 재귀 함수를 호출하여 x부터 시작한다.
이 함수는 해당 좌표와 부모나 자식관계에 있는 모든 사람에게 depth 를 1씩 증가시키고 재귀를 한다.
그러다 해당 좌표가 y가 되면 depth를 출력하고 프로그램을 종료시킨다.(exit)
참고로 재귀를 시키기 전에 자신이 찾아낸 관계를 지워야 한다.
그렇지 않으면 무한루프가 발생하기 때문이다.

이 방법으로 정답은 나왔지만, 스택을 전부 종료하기 위해 exit함수를 사용하는것이 영 꺼림직하다..

소스

1614 영식이의 손가락

손가락으로 숫자를 셀때, n번째 손가락에 셀 수 있는 갯수가 제한(m)되 있는 경우,최대 몇개까지 셀 수 있는가를 묻는 문제이다.
경우의 수를 제대로 생각하지 못해서 여러번 틀렸다.

내가 생각한 기본적인 알고리즘은
m+1번 까지 완주 했을때의 갯수에서 더 나아간 횟수를 빼주는 방식이다.
이때 생각해야 할 것은, n이 엄지나 새끼 손가락일 경우 와 그렇지 않을 경우의 처리 방식이 다르다는 것이다.
다른 손가락은 왔다갔다 할때 횟수가 2번 감소하지만, 엄지와 새끼는 1번 감소한다.
따라서 다른손가락보다 2배 더 갈 수 있다.
즉, 엄지와 새끼일 경우 m=m*2.

m번 완주 했을때 셀 수 있는 수는
p(m) = 1 + 4*m

m+1번 완주 했을때, 원래 멈춰야 될 위치에서 더 나아간 횟수는
m이 짝수일 경우 (손가락의 번호가 점점 증가) 6-n,
m이 홀수일 경우 (손가락의 번호가 점점 감소) n 이다.
즉,
q(n,m) = m%2?n:6-n

우리가 구하려는 답은
f(n,m) = p(m+1) - q(n,m)
이 된다.

ps1. 여기서 엄지와 새끼일 경우는 m이 무조건 짝수가 됨을 알 수 있다..
ps2. 조건에서 m의 범위로 인해 int 형은 오버플로우가 발생 할 수 있음에도 유의하자.
ps3. 이렇게 풀어서 써도 역시 이해하기 어렵다..

소스

3058 짝수를 찾아라

주어지는 수중에서 짝수를 찾고 그 합과 최솟값을 구하는 문제이다.
배열을 쓸것도 없이 받아오는 즉시 검사하여 처리하면 된다.

소스

3943 헤일스톤 수

n 의 헤일스톤 수열중 최댓값을 구하는 문제이다.

헤일스톤 수열은

n이 짝수일때 n/2,

n이 홀수일때 3*n+1 로 바꿔서 n이 1이 될때까지 계속하는 수열이다.

알고리즘은 위에 설명한대로 진행하면서 최댓값을 걸러내면된다.

소스

2783 삼각 김밥

김밥을 1000g 살때의 최저가를 찾는 문제이다.

y 그램당 x 원이므로
1 그램당 가격을 비교해서 최솟값을 찾고 거기에 1000을 곱해준 값을 출력하면 된다.
최솟값을 담은 변수가 float 여도 x,y변수가 int 형이면 형변환 문제가 발생하는것에 유의하자.

소스

4458 첫글자를 대문자로

가장 처음 글자를 대문자로 바꿔서 출력하는 문제이다.
거저먹기 문제라서 별다른 알고리즘은 설명하지 않아도 될 듯 하다.

소스

2799 블라인드

각 집이 블라인드를 얼마나 닫고있는가를 계산하는 문제이다.
계산에 필요없는 라인도 있고 데이터를 세로가 아닌 가로로 받아오기 때문에
풀이 방식에 따라 가로*세로 만큼의 배열을 사용하게 될 수도 있다.
나는 가로 한줄의 배열을 사용하여 풀이 하기로 했다.

알고리즘은
1. 각 층에 대해서 5번의 반복을 한다.
2. 반복을 할때마다 각 호의 블라인드 상태를 점검한다. 4*4 블라인드이므로 5k+1 번째의 문자 하나만 검사해도 블라인드의 여부를 알 수 있다.
3. 발견된 상태들을 index 로 하는 배열에 적재한다.

소스

2921 도미노

크기가 n인 도미노세트에 찍힌 점의 총 갯수를 구하는 문제이다.
이 문제는 케이스를 살펴보면 공식을 유추할 수 있다.
n    답
0 -  0
1 -  3
2 -  12
3 -  30
4 -  60

여기서 크기가 n 인 도미노의 점은 n-1 일때의 점의 갯수를 포함하기 때문에  점화식의 형태를 떠올릴 수 있다.
f(n) = f(n-1) + ~

이식에 2를 대입해보면
f(2) = f(1) + 9 = 12

이 된다. 이 9의 값은 어떻게 나왔는지를 유추해보자.

f(1)에서 이미 점이 1개만 찍힌 경우가 나왔으므로 나머지는 한쪽에 점이 2개 찍힌경우이다.
즉, (2,0), (2,1), (2,2) 의 돌이 남게된다.
이것들을 나눠서 계산해보면
2 * 3 + (0+1+2) = 9 가 된다.

이제 f(n) 으로 생각해보면
f(n) = f(n-1) + n*(n+1) + n*(n+1)/2 = f(n-1) + n*(n+1)*3/2
의 점화식이 완성된다.

따라서 f(1)부터시작해서 쌓아 올라가면 f(n)을 구할 수 있다.

물론 이 점화식을 f(n) = ~ 꼴로 바꿀 수 도 있다.
이걸 구하는 공식은 잊어버렸으나(..)
대충 테스트하니까 다음과 같은 공식임을 발견했다.
f(n) = n*(n+1)*(n+2)/2

역시 수학은 잘하고 봐야한다..

소스

2852 NBA 농구

두 팀의 이기고 있던 시간을 측정하는 문제이다.
간단한 문제지만 두 팀이 동점일 경우도 계산에 넣어야 한다.

이 문제를 풀기위해선
두 팀의 점수(score) 및 시간(time)을 기록하는 변수와
현재 시간을 기록하는 변수가 필요하다.
여기서 시간은  분*60+초 sec 의 공식으로 저장한다.

알고리즘은
1. 새로운 득점 상황을 적용하기 전에 두 팀의 점수를 비교한다.
2. 점수가 높은팀에 새로운 득점 시간에서 현재시간을 뺀시간을 누적한다.
3. 현재시간을 새로운 득점 시간으로 바꾸고, 점수를 갱신한다.
4. 모든 득점이 끝나면 경기종료 시간인 48분으로 2번을 수행한다.

소스

2877 4와 7

4와 7로 이루어진 k번째 작은 수를 구하는 문제이다.

4와 7을 0과 1로 바꿔서 생각하면 2진수가 떠오를 것이다.
즉
0 - 4
1 - 7
로 바꿔서 생각하면 되는데,
여기서 주의해야 할것은 2자리수를 넘어가면 앞이 무조건 7이 된다는것이다.
ex)
0 - 4
1 - 7
10 - 74(정답은 44)
11 - 77(정답은 47)

이럴땐 맨앞에 1이 있다고 가정한 후, 맨앞은 계산하지 않으면 된다.
ex)
10 - 4
11 - 7
100 - 44
101 - 47
110 - 74
~

이 문제에선 K에 1을 더해주면 저 조건이 완성된다.
그 후엔 비트연산자를 통해 K의 자리수를 알아내고 높은 자리수부터 낮춰가면서 출력하면 된다.

소스

2789 유학 금지

받아온 문장에서 CAMBRIDGE 에 속해있는 알파벳이 있을경우 제외 하는 문제이다.

알고리즘
1. 문자를 하나씩 받아온다.
2. 그 문자가 CAMBRIDGE에 속하지 않으면 그대로 출력한다.

소스

2822 점수계산

8개의 점수중 가장 높은 점수 5개를 고르는 문제이다.
점수의 범위는 0~150
이렇게 정렬이 필요하고  범위가 작을때는 해쉬 방식으로 입력하면 편하다.

알고리즘은
0. 크기 151의 배열 a, 크기 9의 배열 b, i번 문제의 점수 n 으로 가정.
1. a[n]=i 의 형식으로 점수를 저장한다.
2. n를 150 부터 0까지 a[n] 이 있는지 살핀다. 있다면 b[a[n]] 에 마킹 하고 점수를 합산
3. 합산한 점수를 뿌려주고 b를 0에서 8까지 살펴서 있으면 출력.

소스

3014 N-퍼즐

현재의 퍼즐이 정답퍼즐과 얼마나 다른가를 물어보는 문제이다.
여기서는 다른 정도를 맨해튼 거리로 표시하는데
맨해튼 거리는 순수 좌표끼리의 차이를 더한것을 거리로 삼는다.
예를들어
 (0,0) , (1,1) 의 유클리드적 거리는 루트2 지만,
맨해튼 거리는 |1-0| + |1-0| = 2  이다.
내가 이 문제를 푸는데 사용한 방법은

1. 정답퍼즐이 알파벳순서로 되어있다는것을 이용.
2. 현재 x,y 위치에 있는 알파벳과 그 알파벳의 정답 x,y좌표를 구한다.
3. 두 좌표의 맨해튼 거리를 구한다.
4. 구한 거리를 누적시킨다.

소스

이 문제를 풀면서 알아낸 신기한것.
for(;~scanf(" %c",&c);)c-='A';
알파벳의 순서를 이용하기위해 이런 방법을 사용했는데,
'.' 을 입력받는 순간부터 계산이 망가졌다.
그 이유는 c가 음수가 되면서 비트가 달라져버렸기 때문이다.
원래 char c 로 선언해서 해야했는데,
int c 로 하는 바람에 음수가 32비트에 박혀서 초기화가 되지 않았다.
역시 형변환에는 주의를 해야겠다.

블로그시작

주로 acmicpc.net 문제풀이나
전공관련 지식을 포스팅 할 예정